跳转至

线段树分治

线段树分治通过将操作离线，并增加 \(O(\log m)\) 的时间复杂度，使得既有插入又有删除的问题转化为只有插入和撤销的子问题。

某些数据结构容易实现插入操作，但是不易或无法实现删除操作。使用线段树分治就可以将删除操作转化为撤销操作，用栈存储数组的变化即可。

使用线段树分治需要满足以下条件：

  • 题目中有插入和删除两种操作；
  • 数据结构容易实现插入，但不易实现删除；
  • 数据结构是非均摊的，因此撤销的时间复杂度有保障。

我们先对每一个元素求出其出现的时间 \([l,r]\)，即该元素在 \(l\) 时刻插入，\(r+1\) 时刻删除。我们在 \(T+1\) 时刻将所有未删除的元素全部删除，保证 \(r\) 有效。

然后将 \([l,r]\) 拍到线段树上，分解为 \(O(m\log m)\) 个区间，将元素的信息添加到对应的区间上。线段树的性质保证这些区间要么包含要么无交。

接着，对线段树进行 dfs，每遍历到一个节点（区间），就将该节点记录的所有元素都插入到数据结构中，然后向子节点递归。如果当前已经是叶子节点，则直接在数据结构上进行查询即可。子节点递归结束后，撤销该节点产生的所有插入操作。

正确性显然：当位于叶节点 \([l,l]\) 时，只有包含 \(l\) 的区间才有贡献。

例题

P5787 二分图 /【模板】线段树分治

题意

有加边和删边两种操作，你需要在每次操作后判定原图是不是二分图。

动态判定二分图可以使用并查集（带权或扩展域）解决。但是并查集只能维护加边的操作，而无法删除其中的某条边。

考虑线段树分治。我们只需要使用启发式合并的并查集，即可实现非均摊 \(O(\log n)\) 合并，用栈维护即可。

模板代码 
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<vector>
using namespace std;
const int N = 1e5 + 10;
const int LOGN = 18;

struct Edge {
    int u, v;
};

int n, m, k;

namespace unf {
    int fa[2 * N], sz[2 * N];
    int sta[2 * N * LOGN][2], top;
    void init() {
        for(int i = 1; i <= n * 2; i++) {
            fa[i] = i;
            sz[i] = 1;
        }
    }
    int find(int x) {
        if(fa[x] == x) return x;
        return find(fa[x]);
    }
    void merge(int x, int y) {
        x = find(x), y = find(y);
        if(sz[x] < sz[y]) swap(x, y);
        sta[++top][0] = x;
        sta[top][1] = y;
        sz[x] += sz[y];
        fa[y] = x;
    }
    void roll_back() {
        int x = sta[top][0];
        int y = sta[top--][1];
        sz[x] -= sz[y];
        fa[y] = y;
    }
}

namespace SegT {
    vector<Edge> tr[4 * N];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    void modify(int p, int l, int r, int ql, int qr, const Edge& v) {
        if(ql <= l && r <= qr) {
            tr[p].push_back(v);
            return;
        }
        int mid = (l + r) >> 1;
        if(ql <= mid) modify(lc(p), l, mid, ql, qr, v);
        if(mid < qr) modify(rc(p), mid + 1, r, ql, qr, v);
    }
    void solve(int p, int l, int r, bool ans) {
        int pre = unf::top;
        if(ans) {
            for(Edge e : tr[p]) {
                if(unf::find(e.u) == unf::find(e.v)) { ans = false; break; }
                unf::merge(e.u, e.v + n);
                unf::merge(e.v, e.u + n);
            }
        }
        if(l == r) {
            cout << (ans ? "Yes\n" : "No\n");
        } else {
            int mid = (l + r) >> 1;
            solve(lc(p), l, mid, ans);
            solve(rc(p), mid + 1, r, ans);
        }
        while(unf::top != pre) unf::roll_back();
    }
}

int main() {

    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m >> k;
    for(int i = 1; i <= m; i++) {
        int u, v, l, r;
        cin >> u >> v >> l >> r;
        if(++l > r) continue;
        SegT::modify(1, 1, k, l, r, (Edge){u, v});
    }

    unf::init();

    SegT::solve(1, 1, k, true);

    return 0;
}

P3733 [HAOI2017] 八纵八横

题意

给定一个无向连通图 \(G=(V,E)\)，边有边权。定义一个环（不要求为简单环）的权值为边权异或和。

有两种操作：

  • 向图中加入一条边；
  • 删除一条以前加入的边（不会删除初始图中的边）；

要求你在每次操作结束后，输出所有环的权值的最大值。

我们随便选择初始图 \(G\) 的一棵生成树，对于每一条非树边，它都能和树边形成一个环，这样的环称为基本环。能够证明，任意环都可以被表示为一些基本环的异或。

因此，我们只需要使用线性基维护所有基本环，就可以快速查询答案。

然而，普通的线性基无法实现删除操作。又因为没有强制在线，因此考虑线段树分治，将删除操作变为撤销操作。

线性基不是均摊的，因此我们只需要用栈记录数组的变化，即可实现撤销操作。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include<iostream>
#include<bitset>
#include<vector>
#define w_tp bitset<1005>
using namespace std;
const int N = 510;
const int M = 510;
const int LOGN = 1002;
const int Q = 1010;

char buf[LOGN];
int buf_top;
void print(w_tp x) {
    for(int i = 0; i < 1000; i++) {
        buf[++buf_top] = x[i] + '0';
    }
    while(buf[buf_top] == '0') --buf_top;
    if(!buf_top) ++buf_top;
    while(buf_top) putchar(buf[buf_top--]);
}

struct Edge {
    int u, v;
    w_tp w;
};

struct _Edge {
    int v;
    w_tp w;
    int next;
} pool[2 * M];
int ne = 1, head[N];

void addEdge(int u, int v, const w_tp &w) {
    pool[++ne] = {v, w, head[u]};
    head[u] = ne;
}

int n, m, t;

w_tp pw2[LOGN];
w_tp bs[LOGN];
w_tp c_ans;
int sta[Q * 11], top;
void insert(w_tp x) {
    for(int i = LOGN - 1; i >= 0; i--) {
        if(x[i]) {
            if(bs[i].any()) x ^= bs[i];
            else {
                bs[i] = x;
                sta[++top] = i;
                return;
            }
        }
    }
}

void roll_back() {
    bs[sta[top--]] = 0;
}

w_tp s[N];
int vis[N];
void dfs(int u, int ef) {
    vis[u] = 1;
    for(int i = head[u]; i; i = pool[i].next) {
        if(i == ef) continue;
        int v = pool[i].v;
        const w_tp &w = pool[i].w;
        if(vis[v]) {
            insert(s[u] ^ s[v] ^ w);
        } else {
            s[v] = s[u] ^ w;
            dfs(v, i ^ 1);
        }
    }
}

namespace SegT {
    vector<Edge> tr[4 * Q];
    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }
    void modify(int p, int l, int r, int ql, int qr, const Edge& v) {
        if(l > r) return;
        if(ql <= l && r <= qr) {
            tr[p].push_back(v);
            return;
        }
        int mid = (l + r) >> 1;
        if(ql <= mid) modify(lc(p), l, mid, ql, qr, v);
        if(mid < qr) modify(rc(p), mid + 1, r, ql, qr, v);
    }
    void solve(int p, int l, int r) {
        if(l > r) return;
        int pre = top;
        for(Edge &e : tr[p]) {
            insert(s[e.u] ^ s[e.v] ^ e.w);
        }
        if(l == r) {
            c_ans = 0;
            for(int i = LOGN - 1; i >= 0; i--) {
                if(!c_ans[i] && bs[i][i]) c_ans ^= bs[i];
            }

            print(c_ans);
            cout << '\n';
        } else {
            int mid = (l + r) >> 1;
            solve(lc(p), l, mid);
            solve(rc(p), mid + 1, r);
        }
        while(top > pre) roll_back();
    }
}

Edge edg[Q];
int app[Q], naq;

int main() {

    cin >> n >> m >> t;
    for(int i = 1; i <= m; i++) {
        int u, v;
        w_tp w;
        cin >> u >> v >> w;
        addEdge(u, v, w);
        addEdge(v, u, w);
    }

    dfs(1, 0);

    c_ans = 0;
    for(int i = LOGN - 1; i >= 0; i--) {
        if(!c_ans[i] && bs[i].any()) c_ans ^= bs[i];
    }

    print(c_ans);
    cout << '\n';

    for(int i = 1; i <= t; i++) {
        string op;
        cin >> op;
        if(op == "Add") {
            app[++naq] = i;
            cin >> edg[naq].u >> edg[naq].v >> edg[naq].w;
        } else if(op == "Cancel") {
            int id;
            cin >> id;
            SegT::modify(1, 1, t, app[id], i - 1, edg[id]);
            app[id] = -1;
        } else {
            int id;
            cin >> id;
            SegT::modify(1, 1, t, app[id], i - 1, edg[id]);
            app[id] = i;
            cin >> edg[id].w;
        }
    }

    for(int i = 1; i <= naq; i++) {
        if(~app[i]) SegT::modify(1, 1, t, app[i], t, edg[i]);
    }

    SegT::solve(1, 1, t);

    return 0;
}

P9168 [省选联考 2023] 人员调度

题意

有一棵 \(n\) 个节点的有根树，根节点是 \(1\) 号节点。每个节点对应一个可重集 \(S_i\)。你可以进行若干次操作，每次操作你可以选定一个节点 \(u\) 和 \(S_u\) 中的一个元素 \(x\)，然后选定一个 \(u\) 子树内的节点 \(v\)，将 \(x\) 从 \(S_u\) 移动到 \(S_v\) 中。最终，你会获得 \(\sum_{u}\max\{S_u\}\) 的价值。

初始时所有可重集为空，你需要维护两种操作，并在每次操作之后输出能够得到的最大价值：

  • 向 \(S_u\) 加入一个元素 \(x\)；
  • 从 \(S_u\) 中删除一个 \(x\)，保证 \(x\in S_u\)；

\(n,m\le 10^5\)

静态问题和简化模型

先考虑静态问题怎么做。显然，我们只关心那些产生贡献的元素。假设 \(u\) 的所有子树内部都已经分配完成，我们将子树内（不算 \(u\)）产生贡献的元素都放到一个可重集 \(A\) 中。考虑如何分配 \(u\) 节点中的元素。容易发现，\(S_u\) 内的每一个元素 \(x\) 都可以任意替换 \(A\) 中比 \(x\) 小的元素，或者直接加入 \(A\) 集合（即被指派到一个空节点），并且需要满足 \(|A|\le sz[u]\)。

显然，我们一定优先选择空节点进行指派，其次是 \(A\) 中的最小值，直到 \(S_u\) 中的任意一个元素都不能更优。这样，我们就得到了一个简化的模型：给每个子树维护一个有序序列，对于每个节点 \(u\)，我们将它的所有子节点的序列合并起来，再加入 \(S_u\) 中的元素，然后不断删除序列的最小值，直到序列长度不超过 \(sz[u]\)（下文称这个过程为“竞争”）。这样，根节点的序列元素之和就是答案。

可并堆可以解决这个静态问题，但是我不会可并堆。

带插入

考虑插入操作。我们观察插入的元素 \(x\) 何时会产生贡献。第一种情况是：从 \(u\) 到根，序列一直都没有满，可以直接插入；第二种情况：在所有满的位置上，\(x\) 都没有被淘汰。

考虑如何处理第二种情况。由于被淘汰的 \(x\) 不一定是在第一轮竞争中就被淘汰了；即使 \(x\) 能在后面的竞争中胜出，也不一定能撑过第一轮。我们尝试考察：是否存在一次决定性的竞争，即使只考虑这次竞争，只要 \(x\) 成功保留下来，就一定能产生贡献。

对于 \(u\) 的一个祖先 \(t\)（我们只考察存在竞争的节点），如果我们已知 \(t\) 序列中的所有元素 \(y_i\) 都在最终序列中产生贡献，并且 \(x\) 坚持到了 \(t\) 这一轮，那么只要 \(x\) 在 \(t\) 的竞争中胜过一个 \(y_i\)，就一定会产生贡献，否则一定不能。

我们现在考察 \(x\) 何时能坚持到这个 \(t\)。不妨考虑最深的一个 \(t\)，这样 \(x\) 更容易成功。记 \(t\) 序列中的最小值为 \(lim\)，显然需要满足 \(x> lim\)。依次考察 \(u\rightarrow t\) 中所有含有竞争的节点是否会把 \(x\) 淘汰。

假设在一个节点 \(p_0\) 处，\(x\) 被淘汰了，那么 \(p_0\) 的序列中一定不存在比 \(x\) 小的元素，因此也不存在比 \(lim+1\) 小的元素。因为 \(p_0\) 的序列中的元素不能全部进入 \(t\) 的序列（否则 \(p_0\) 是比 \(t\) 更深的合法节点），因此一定存在一个 \(p_0\rightarrow t\) 中间的节点 \(p_1\)，它将 \(p_0\) 的部分元素淘汰了，因此 \(p_1\) 也不存在比 \(lim+1\) 更小的元素。因为 \(t\) 中存在 \(lim\) 比 \(lim+1\) 更小，因此经过不断归纳，一定会导出矛盾。

由此，若 \(x> lim\)，则 \(x\) 一定能坚持到 \(t\)，淘汰 \(lim\)，对答案产生 \(x-lim\) 的贡献。

维护方式

如果没有合法的 \(t\) 存在，我们不妨向 \(1\) 号节点添加 \(+\infty\) 个值为 \(0\) 的元素。这样，\(1\) 号节点就成为了一个合法的 \(t\)。此时，加入 \(x\) 一定能直接产生 \(x\) 的贡献。通过这种处理，我们还能直接将第一种情况归为第二种。

我们现在需要查询 \(u\) 节点向上第一个将序列全部贡献到答案的祖先 \(t\)，并且实现修改。容易发现，每插入一个元素 \(x\) 最多只会有两种操作：向最优解中插入一个元素 \(x\)；从最优解中删除一个元素 \(lim\)。我们维护每个节点 \(u\) 对应的子树内有多少个节点没有参与最优解。那么这两个操作显然等价于链加。而查询等价于找到第一个权值 \(=0\) 的节点。用树剖+线段树上二分实现即可。

至于如何得到 \(lim\) 的大小和位置。我们发现这等价于一个子树最小值。如果一个节点有多个元素同时贡献，用 \(n\) 个 set 维护最小值，如果发现最小值变化，再更新到线段树上。

带删除

对于删除操作，发现操作都是非均摊的，线段树分治即可。

代码 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
#include<iostream>
#include<vector>
#include<set>
#define ll long long
#define int long long
using namespace std;
const int N = 1e5 + 10;
const int LOGN = 19;
const int INF = 0x3f3f3f3f3f3f3f3f;

struct Edge {
    int v, next;
} pool[N];
int ne, head[N];

void addEdge(int u, int v) {
    pool[++ne] = {v, head[u]};
    head[u] = ne;
}

int n, k, m, nq, nk;

int dep[N], sz[N], fa[N], son[N];
int top[N], dfn[N], id[N], dt;

void dfs1(int u, int a0) {
    dep[u] = dep[a0] + 1;
    sz[u] = 1;
    fa[u] = a0;
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[son[u]]) son[u] = v;
    }
}

void dfs2(int u, int tp) {
    dfn[u] = ++dt;
    id[dt] = u;
    top[u] = tp;
    if(!son[u]) return;
    dfs2(son[u], tp);
    for(int i = head[u]; i; i = pool[i].next) {
        int v = pool[i].v;
        if(v == son[u]) continue;
        dfs2(v, v);
    }
}

namespace SegT1 {

    struct Node {
        int val, dep, id;
        inline const Node& operator+(const Node &b) const {
            if(val != b.val) return val < b.val ? *this : b;
            return dep > b.dep ? *this : b;
        }
        inline const Node& operator+=(int x) {
            val += x;
            return *this;
        }
    } tr[4 * N];
    int tag[4 * N];

    inline int lc(int x) { return x << 1; }
    inline int rc(int x) { return x << 1 | 1; }

    inline void move_tag(int p, int tg) {
        tr[p] += tg;
        tag[p] += tg;
    }
    inline void push_down(int p) {
        if(!tag[p]) return;
        move_tag(lc(p), tag[p]);
        move_tag(rc(p), tag[p]);
        tag[p] = 0;
    }
    inline void push_up(int p) {
        tr[p] = tr[lc(p)] + tr[rc(p)];
    }
    void build(int p, int l, int r) {
        if(l == r) {
            tr[p] = {sz[id[l]], dep[id[l]], id[l]};
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p);
    }
    void add(int p, int l, int r, int ql, int qr, int v) {
        if(ql <= l && r <= qr) {
            move_tag(p, v);
            return;
        }
        push_down(p);
        int mid = (l + r) >> 1;
        if(ql <= mid) add(lc(p), l, mid, ql, qr, v);
        if(mid < qr) add(rc(p), mid + 1, r, ql, qr, v);
        push_up(p);
    }
    Node query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return tr[p];
        push_down(p);
        int mid = (l + r) >> 1;
        if(mid < ql) return query(rc(p), mid + 1, r, ql, qr);
        if(qr <= mid) return query(lc(p), l, mid, ql, qr);
        return query(lc(p), l, mid, ql, qr) + query(rc(p), mid + 1, r, ql, qr);
    }

}

multiset<int> f[N];
int fm[N];

namespace SegT2 {
    int mn[4 * N];
    using SegT1::lc;
    using SegT1::rc;
    void push_up(int p) {
        int l = lc(p), r = rc(p);
        if(fm[mn[l]] < fm[mn[r]]) mn[p] = mn[l];
        else mn[p] = mn[r];
    }
    void build(int p, int l, int r) {
        if(l == r) {
            mn[p] = id[l];
            return;
        }
        int mid = (l + r) >> 1;
        build(lc(p), l, mid);
        build(rc(p), mid + 1, r);
        push_up(p);
    }
    void update(int p, int l, int r, int q) {
        if(l == r) return;
        int mid = (l + r) >> 1;
        if(q <= mid) update(lc(p), l, mid, q);
        else update(rc(p), mid + 1, r, q);
        push_up(p);
    }
    int query(int p, int l, int r, int ql, int qr) {
        if(ql <= l && r <= qr) return mn[p];
        int mid = (l + r) >> 1;
        if(mid < ql) return query(rc(p), mid + 1, r, ql, qr);
        if(qr <= mid) return query(lc(p), l, mid, ql, qr);
        int rl = query(lc(p), l, mid, ql, qr), rr = query(rc(p), mid + 1, r, ql, qr);
        return fm[rl] < fm[rr] ? rl : rr;
    }
}

struct Node {
    int p, v;
};

// 路径加
void add_path(int p, int v) {
    while(p) {
        SegT1::add(1, 1, n, dfn[top[p]], dfn[p], v);
        p = fa[top[p]];
    }
}

// 查询第一个满的祖先
int query_path(int p) {
    while(p) {
        SegT1::Node res = SegT1::query(1, 1, n, dfn[top[p]], dfn[p]);
        if(res.val == 0) return res.id;
        p = fa[top[p]];
    }
    return 0;
}

struct Op {
    int op;
    Node v;
} sta[4 * N];
int tp;

ll ans;

// 将一个人插入最优解
void insert_people(int p, int v) {
    ans += v;
    f[p].insert(v);
    fm[p] = *f[p].begin();
    add_path(p, -1);
    SegT2::update(1, 1, n, dfn[p]);
}

// 表示将这个人从最优解中删去，被另一个人取代了
void del_people(int p, int v) {
    ans -= v;
    f[p].erase(f[p].find(v));
    fm[p] = *f[p].begin();
    add_path(p, 1);
    SegT2::update(1, 1, n, dfn[p]);
}

// 新加入一个员工
void add_people(Node x) {
    int y = query_path(x.p);
    if(!y) {
        sta[++tp] = {1, x.p, x.v};
        insert_people(x.p, x.v);
    } else {
        int z = SegT2::query(1, 1, n, dfn[y], dfn[y] + sz[y] - 1);
        if(fm[z] >= x.v) return;
        sta[++tp] = {-1, z, fm[z]};
        del_people(z, fm[z]);
        sta[++tp] = {1, x.p, x.v};
        insert_people(x.p, x.v);
    }
}

void roll_back() {
    if(sta[tp].op == 1) del_people(sta[tp].v.p, sta[tp].v.v);
    else insert_people(sta[tp].v.p, sta[tp].v.v);
    --tp;
}

namespace SegT_pt {
    vector<Node> tr[4 * N];
    using SegT1::lc;
    using SegT1::rc;
    void modify(int p, int l, int r, int ql, int qr, const Node& v) {
        if(ql <= l && r <= qr) {
            tr[p].push_back(v);
            return;
        }
        int mid = (l + r) >> 1;
        if(ql <= mid) modify(lc(p), l, mid, ql, qr, v);
        if(mid < qr) modify(rc(p), mid + 1, r, ql, qr, v);
    }
    void work(int p, int l, int r) {
        int pre = tp;
        for(Node &i : tr[p]) add_people(i);
        if(l == r) {
            cout << ans << ' ';
        } else {
            int mid = (l + r) >> 1;
            work(lc(p), l, mid);
            work(rc(p), mid + 1, r);
        }
        while(tp > pre) roll_back();
    }
}

Node a[2 * N];
int app[2 * N];
void add(int tm, int id, int p, int v) {
    app[id] = tm;
    a[id] = {p, v};
}
void del(int tm, int id) {
    if(!app[id]) return;
    SegT_pt::modify(1, 1, nq, app[id], tm - 1, a[id]);
    app[id] = 0;
}

signed main() {

    cin >> n >> n >> k >> m;
    nk = k;
    nq = m + 1;
    for(int i = 2; i <= n; i++) {
        int x;
        cin >> x;
        addEdge(x, i);
    }
    for(int i = 1; i <= k; i++) {
        int p, v;
        cin >> p >> v;
        add(1, i, p, v);
    }
    for(int i = 1; i <= m; i++) {
        int op, p, v, id;
        cin >> op;
        if(op == 1) {
            cin >> p >> v;
            add(i + 1, ++nk, p, v);
        } else {
            cin >> id;
            del(i + 1, id);
        }
    }

    for(int i = 1; i <= nk; i++) del(nq + 1, i);

    dfs1(1, 0);
    dfs2(1, 1);

    for(int i = 1; i <= n; i++) f[i].insert(INF);
    for(int i = 1; i <= n; i++) fm[i] = INF;

    SegT1::build(1, 1, n);
    SegT2::build(1, 1, n);

    SegT_pt::work(1, 1, nq);

    cout << endl;

    return 0;
}