可持久化线段树与 01Trie 的一些例题。
可持久化线段树
概述
对于单点修改,只需要考虑从根到这个点的路径上的
对于区间修改,采用标记永久化:
标记永久化有两种写法:
第一种写法,标记维护覆盖该区间的修改的贡献,其余不完全覆盖直接在修改时计算贡献即可。
例如区间加:
struct node { int ls, rs; ll data, add; } t[MAX_NODE_CNT];
void build(int& cur, int l, int r) {
cur = ++node_cnt, t[cur].add = 0;
if (l == r) { t[cur].data = arr[l]; return ; }
build(lq(cur)), build(rq(cur));
t[cur].data = t[ls(cur)].data + t[rs(cur)].data;
}
void modify(int pre, int& cur, int l, int r, int ql, int qr, ll val) {
cur = ++node_cnt; t[cur] = t[pre];
if (ql <= l && r <= qr) { t[cur].add += val; return ; }
t[cur].data += 1ll * (min(qr, r) - max(ql, l) + 1) * val;
if (ql <= mid) modify(ls(pre), lq(cur), ql, qr, val);
if (qr > mid) modify(rs(pre), rq(cur), ql, qr, val);
}
ll query(int cur, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return t[cur].data + 1ll * (r - l + 1) * t[cur].add;
ll val = 1ll * (min(qr, r) - max(ql, l) + 1) * t[cur].add;
if (ql <= mid) val += query(lq(cur), ql, qr);
if (qr > mid) val += query(rq(cur), ql, qr);
return val;
}
区间加等差数列:
void build(int& cur, int l, int r) {
cur = ++node_cnt;
if (l == r) return ;
build(lq(cur)), build(rq(cur));
}
void modify(int pre, int& cur, int l, int r, int ql, int qr, ll num, ll delta) {
cur = ++node_cnt; t[cur] = t[pre];
if (ql <= l && r <= qr) { t[cur].num += num, t[cur].delta += delta; return ; }
int sl = max(l, ql), sr = min(r, qr);
t[cur].sum += (num + 1ll * (sl - ql) * delta + num + 1ll * (sr - ql) * delta) * (sr - sl + 1) / 2;
if (ql <= mid) modify(ls(pre), lq(cur), ql, min(qr, mid), num, delta);
if (qr > mid) modify(rs(pre), rq(cur), max(mid + 1, ql), qr, num + 1ll * (max(mid + 1, ql) - ql) * delta, delta);
}
ll query(int cur, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) { return t[cur].sum + (t[cur].num + t[cur].num + 1ll * (r - l) * t[cur].delta) * (r - l + 1) / 2; }
int sl = max(l, ql), sr = min(r, qr);
ll val = (t[cur].num + 1ll * (sl - l) * t[cur].delta + t[cur].num + 1ll * (sr - l) * t[cur].delta) * (sr - sl + 1) / 2;
if (ql <= mid) val += query(lq(cur), ql, min(mid, qr));
if (qr > mid) val += query(rq(cur), max(mid + 1, ql), qr);
return val;
}
第二种写法,标记只维护自己这个区间的贡献,修改的时候一路累计下来就好,维护的值则要一路向上传贡献。
可以知道,一个修改以完全覆盖的节点为起始,向上是全部传递的了,只有向下没有传递,所以询问的时候累计一下标记。
例如区间加,区间求和 (source:SJX):
void pushup(int o, int len) { tr[o] = tr[o<<1] + tr[o<<1|1] + tag[o] * len; }
void bld(int l, int r, int o) {
if(l == r) { tr[o] = b[l]; return; }
int mid = (l + r) >> 1;
bld(lch); bld(rch);
pushup(o, r - l + 1);
}
void upd(int L, int R, int k, int l, int r, int o) {
if(L <= l && r <= R) {
tag[o] += k, tr[o] += (ll)k * (r - l + 1);
return;
}
int mid = (l + r) >> 1;
if(L <= mid) upd(L, R, k, lch);
if(R > mid) upd(L, R, k, rch);
pushup(o, r - l + 1);
}
ll qry(int L, int R, ll sum, int l, int r, int o) {
if(L <= l && r <= R) return sum * (r - l + 1) + tr[o];
sum += tag[o];
int mid = (l + r) >> 1; ll ret = 0;
if(L <= mid) ret += qry(L, R, sum, lch);
if(R > mid) ret += qry(L, R, sum, rch);
return ret;
}
还可以实现可持久化数组。
本质上就是对数组建一个可持久化线段树。
有了可持久化数组,就可以实现更多可持久化数组,比如可持久化并查集。
struct Persistent_Segment_Tree {
#define mid ((l + r) >> 1)
#define ls(_) t[_].ls
#define rs(_) t[_].rs
#define lq(_) t[_].ls, l, mid
#define rq(_) t[_].rs, mid + 1, r
int node_cnt, rt[MAXN];
int& operator [](int x) { return rt[x]; }
struct node { int ls, rs, data; } t[MAX_NODE_CNT];
int build(int l, int r, int* arr) {
int cur = ++node_cnt;
if (l == r) { t[cur].data = arr[l]; return cur; };
ls(cur) = build(l, mid, arr), rs(cur) = build(mid + 1, r, arr);
return cur;
}
int modify(int pre, int l, int r, int pos, int val) {
int cur = ++node_cnt; t[cur] = t[pre];
if (l == r) { t[cur].data = val; return cur; }
if (pos <= mid) ls(cur) = modify(ls(pre), l, mid, pos, val);
else rs(cur) = modify(rs(pre), mid + 1, r, pos, val);
return cur;
}
int query(int cur, int l, int r, int pos) {
if (l == r) return t[cur].data;
if (pos <= mid) return query(ls(cur), l, mid, pos);
else return query(rs(cur), mid + 1, r, pos);
}
} t;
【HUD 2665】第K小数
询问区间第
做主席树题先想如何用
考虑建出
由于所有权值线段树形态都相同,询问
然后用主席树的替换权值线段树即可。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 5e6 + 10;
#define ls(_) (t[_].ls)
#define rs(_) (t[_].rs)
#define mid ((l + r) >> 1)
struct node { int ls, rs, val; } t[MAXN];
int tot, rt[MAXN];
int n, q, arr[MAXN], cpy[MAXN], a[MAXN];
int build(int l, int r) {
int k = ++tot;
if (l == r) { return k; }
ls(k) = build(l, mid), rs(k) = build(mid + 1, r);
return k;
}
int modify(int pre, int l, int r, int pos, int val) {
int k = ++tot;
t[k] = t[pre]; t[k].val += val;
if (l == r) { return k; }
if (pos <= mid) ls(k) = modify(ls(pre), l, mid, pos, val);
else rs(k) = modify(rs(pre), mid + 1, r, pos, val);
return k;
}
int query(int p, int q, int l, int r, int sz) {
if (l == r) return l;
int _cnt = t[ls(p)].val - t[ls(q)].val;
if (sz <= _cnt) return query(ls(p), ls(q), l, mid, sz);
else return query(rs(p), rs(q), mid + 1, r, sz - _cnt);
}
int main() {
scanf("%d %d", &n, &q);
for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]), cpy[i] = arr[i];
sort(arr + 1, arr + n + 1);
int N = unique(arr + 1, arr + n + 1) - arr - 1;
rt[0] = build(1, N);
for (int i = 1; i <= n; ++i) a[i] = lower_bound(arr + 1, arr + N + 1, cpy[i]) - arr, rt[i] = modify(rt[i - 1], 1, N, a[i], 1);
for (int i = 1, l, r, k; i <= q; ++i) {
scanf("%d %d %d", &l, &r, &k);
printf("%d\n", arr[query(rt[r], rt[l - 1], 1, N, k)]);
}
return 0;
}
【HDU 4417】超级马里奥
询问区间小于等于
同样,建出
同样,由于形态相同,对于询问
时间复杂度
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100000;
const int MAX_NODE_CNT = 5e6 + 10;
int n, m, arr[MAXN << 1], cpy[MAXN << 1];
struct Persistent_Segmenttree {
#define mid ((l + r) >> 1)
#define ls(_) t[_].ls
#define rs(_) t[_].rs
int node_cnt, rt[MAXN];
int& operator [](const int& x) { return rt[x]; }
struct node { int ls, rs, data; } t[MAX_NODE_CNT];
int build(int l, int r) {
int cur = ++node_cnt;
if (l == r) return cur;
ls(cur) = build(l, mid), rs(cur) = build(mid + 1, r);
return cur;
}
int modify(int pre, int l, int r, int pos, int val) {
int cur = ++node_cnt; t[cur] = t[pre], t[cur].data += val;
if (l == r) return cur;
if (pos <= mid) ls(cur) = modify(ls(pre), l, mid, pos, val);
else rs(cur) = modify(rs(pre), mid + 1, r, pos, val);
return cur;
}
int query(int cur, int l, int r, int pos) {
if (r <= pos) return t[cur].data;
int ret = query(ls(cur), l, mid, pos);
if (pos > mid) ret += query(rs(cur), mid + 1, r, pos);
return ret;
}
} t;
struct query { int l, r, val; } q[MAXN];
int main() {
scanf("%d %d", &n, &m);
int _n = 0;
for (int i = 1; i <= n; ++i) scanf("%d", &arr[i]), cpy[++_n] = arr[i];
for (int i = 1, l, r, val; i <= m; ++i) scanf("%d %d %d", &l, &r, &val), q[i].l = l + 1, q[i].r = r + 1, q[i].val = val, cpy[++_n] = val;
sort(cpy + 1, cpy + _n + 1); int __n = unique(cpy + 1, cpy + _n + 1) - cpy - 1;
t[0] = t.build(1, __n);
for (int i = 1; i <= n; ++i) arr[i] = lower_bound(cpy + 1, cpy + __n + 1, arr[i]) - cpy, t[i] = t.modify(t[i - 1], 1, __n, arr[i], 1);
for (int i = 1; i <= m; ++i) q[i].val = lower_bound(cpy + 1, cpy + __n + 1, q[i].val) - cpy;
for (int i = 1; i <= m; ++i) printf("%d\n", t.query(t[q[i].r], 1, __n, q[i].val) - t.query(t[q[i].l - 1], 1, __n, q[i].val));
return 0;
}
SCOI2015 情报传递
给出一棵树,初始点权都为
- 给出
x ,代表从下一时刻起,x 的点权会变为1 ,并每个时刻+1 。 - 给出
u, v, k ,求该时刻时,u 到v 的路径上有多少个点的权值大于k 。
保证一个点至多被修改
对于询问操作
那么我们离线后,将每个节点的权值记为被修改的时刻,询问只需要询问
看起来只能树剖+权值线段树(主席树),不过这并不是唯一的解法。
对于第
答案即为
时间复杂度
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
const int MAX_NODE_CNT = 5e6 + 10;
int n, graph_root;
vector<int> G[MAXN];
struct query {
int l, r, val, ver, opt;
} q[MAXN];
struct Vertix { int fa, val, dfn, sz, son, top, dep; } vertix[MAXN];
struct Persistent_Segmenttree {
#define mid ((l + r) >> 1)
#define ls(_) t[_].ls
#define rs(_) t[_].rs
int node_cnt, rt[MAXN];
int& operator [](const int& x) { return rt[x]; }
struct node { int ls, rs, data; } t[MAX_NODE_CNT];
int build(int l, int r) {
int cur = ++node_cnt;
if (l == r) return cur;
ls(cur) = build(l, mid), rs(cur) = build(mid + 1, r);
return cur;
}
int modify(int pre, int l, int r, int pos, int val) {
int cur = ++node_cnt; t[cur] = t[pre], t[cur].data += val;
if (l == r) return cur;
if (pos <= mid) ls(cur) = modify(ls(pre), l, mid, pos, val);
else rs(cur) = modify(rs(pre), mid + 1, r, pos, val);
return cur;
}
int query(int cur, int l, int r, int pos) {
if (r <= pos) return t[cur].data;
int ret = query(ls(cur), l, mid, pos);
if (pos > mid) ret += query(rs(cur), mid + 1, r, pos);
return ret;
}
} t;
int dfs_clock = 0;
void dfs1(int u) {
vertix[u].dep = vertix[vertix[u].fa].dep + 1;
int max_size = 0; vertix[u].sz = 1;
for (auto v : G[u]) if (v != vertix[u].fa) {
dfs1(v);
vertix[u].sz += vertix[v].sz;
if (vertix[v].sz > max_size) max_size = vertix[v].sz, vertix[u].son = v;
}
}
int dtp[MAXN];
void dfs2(int u, int top) {
vertix[u].top = top; vertix[u].dfn = ++dfs_clock, dtp[dfs_clock] = u;
if (vertix[u].son) dfs2(vertix[u].son, top);
for (auto v : G[u]) if (v != vertix[u].fa && v != vertix[u].son) dfs2(v, v);
}
int lca(int u, int v) {
while (1) {
if (vertix[u].top == vertix[v].top) return vertix[u].dep < vertix[v].dep ? u : v;
if (vertix[vertix[u].top].dep > vertix[vertix[v].top].dep) swap(u, v);
v = vertix[vertix[v].top].fa;
}
}
bool bwt[MAXN];
int main() {
scanf("%d", &n);
for (int i = 1, fff; i <= n; ++i) {
scanf("%d", &fff); if (fff == 0) graph_root = i;
G[fff].push_back(i), G[i].push_back(fff); vertix[i].fa = fff;
}
int _;
scanf("%d", &_);
for (int i = 1; i <= n; ++i) vertix[i].val = _ + 1;
for (int i = 1, opt; i <= _; ++i) {
scanf("%d", &opt);
if (opt == 1) {
int u, v, val;
scanf("%d %d %d", &u, &v, &val); q[i].l = u, q[i].r = v, q[i].val = i - val - 1, q[i].ver = i, q[i].opt = 1;
} else {
int pos;
scanf("%d", &pos);
assert(!bwt[pos]); bwt[pos] = true;
q[i].l = pos, q[i].ver = i, vertix[pos].val = i;
}
}
dfs1(graph_root), dfs2(graph_root, graph_root);
t[0] = t.build(1, n);
for (int i = 1; i <= dfs_clock; ++i) t[i] = t.modify(t[vertix[vertix[dtp[i]].fa].dfn], 1, n, vertix[dtp[i]].val, 1);
for (int i = 1; i <= _; ++i) {
if (q[i].opt == 0) continue;
int u = q[i].l, v = q[i].r, val = q[i].val, _lca = lca(u, v);
int ans1 = vertix[u].dep + vertix[v].dep - vertix[_lca].dep - vertix[_lca].dep + 1;
if (val <= 0) { printf("%d 0\n", ans1); continue; }
int a1 = t.query(t[vertix[u].dfn], 1, n, val);
int a2 = t.query(t[vertix[v].dfn], 1, n, val);
int a3 = t.query(t[vertix[_lca].dfn], 1, n, val);
printf("%d %d\n", ans1, a1 + a2 - a3 - a3 + (vertix[_lca].val <= val));
}
return 0;
}
【BZOJ 3932】任务查询系统
维护
- 给出
l, r, x ,代表将x 插入到[l, r] 的集合。 - 给出
p, k ,求出第p 个集合小于等于k 的数的和。
通过差分,将区间加,单点求和变成单点加,前缀求和。然后主席树上二分即可。
时间复杂度
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 100000 + 10;
const int MAX_NODE_CNT = MAXN << 7;
int n, m, cpy[MAXN];
vector<int> st[MAXN], ed[MAXN];
struct Chairman_Tree {
#define mid ((l + r) >> 1)
#define ls(_) t[_].ls
#define rs(_) t[_].rs
#define lq(_) t[_].ls, l, mid
#define rq(_) t[_].rs, mid + 1, r
int node_cnt, rt[MAXN];
int& operator [](const int& x) { return rt[x]; }
struct node { int ls, rs, data; ll sum; } t[MAX_NODE_CNT];
int build(int l, int r) {
int cur = ++node_cnt;
if (l == r) return cur;
ls(cur) = build(l, mid), rs(cur) = build(mid + 1, r);
return cur;
}
int modify(int pre, int l, int r, int pos, int val) {
int cur = ++node_cnt; t[cur] = t[pre]; t[cur].data += val, t[cur].sum += 1ll * val * cpy[pos];
if (l == r) return cur;
if (pos <= mid) ls(cur) = modify(lq(pre), pos, val);
else rs(cur) = modify(rq(pre), pos, val);
return cur;
}
int query(int cur, int l, int r, int pos) {
if (l == r) return t[cur].sum / (1ll * t[cur].data) * 1ll * pos;
if (pos <= t[ls(cur)].data) return query(lq(cur), pos);
else return query(rq(cur), pos - t[ls(cur)].data) + t[ls(cur)].sum;
}
} t;
int main() {
scanf("%d %d", &n, &m);
for (int i = 1, l, r, k; i <= n; ++i) {
scanf("%d %d %d", &l, &r, &k);
cpy[i] = k;
st[l].push_back(k), ed[r + 1].push_back(k);
}
sort(cpy + 1, cpy + n + 1); int _n = unique(cpy + 1, cpy + n + 1) - cpy - 1;
for (int i = 1; i <= m; ++i) {
t[i] = t[i - 1];
for (auto val : st[i]) {
val = lower_bound(cpy + 1, cpy + _n + 1, val) - cpy;
t[i] = t.modify(t[i], 1, _n, val, 1);
}
for (auto val : ed[i]) {
val = lower_bound(cpy + 1, cpy + _n + 1, val) - cpy;
t[i] = t.modify(t[i], 1, _n, val, -1);
}
}
int pre_ans = 1, k = 0;
for (int i = 1, x, a, b, c; i <= m; ++i) {
scanf("%d %d %d %d", &x, &a, &b, &c);
k = 1 + (1ll * a * pre_ans + 1ll * b) % c;
if (k > t.t[t[x]].data) pre_ans = t.t[t[x]].sum;
else pre_ans = t.query(t[x], 1, _n, k);
printf("%d\n", pre_ans);
}
return 0;
}
HZOI 2015 疯狂的颜色序列
静态区间数颜色。
对于颜色
考虑主席树,对下标建树,第
如何建树?建树的同时维护
区间数颜色,维护一下区间和就行。
具体而言,对于询问
时间复杂度
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1000000 + 10;
const int MAX_NODE_CNT = MAXN << 5;
int n, m, lst[MAXN];
struct Persistent_Segment_Tree {
#define mid ((l + r) >> 1)
#define ls(_) t[_].ls
#define rs(_) t[_].rs
#define lq(_) t[_].ls, l, mid
#define rq(_) t[_].rs, mid + 1, r
int node_cnt, rt[MAXN];
int& operator [](const int& x) { return rt[x]; }
struct node { int ls, rs, data; } t[MAX_NODE_CNT];
int build(int l, int r) {
int cur = ++node_cnt;
if (l == r) return cur;
ls(cur) = build(l, mid), rs(cur) = build(mid + 1, r);
return cur;
}
int modify(int pre, int l, int r, int pos, int val) {
int cur = ++node_cnt; t[cur] = t[pre], t[cur].data += val;
if (l == r) { return cur; }
if (pos <= mid) ls(cur) = modify(ls(pre), l, mid, pos, val);
else rs(cur) = modify(rs(pre), mid + 1, r, pos, val);
return cur;
}
int query(int cur, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return t[cur].data;
int ret = 0;
if (ql <= mid) ret += query(lq(cur), ql, qr);
if (qr > mid) ret += query(rq(cur), ql, qr);
return ret;
}
} t;
int main() {
scanf("%d %d", &n, &m);
t[0] = t.build(1, n);
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x); t[i] = t.modify(t[i - 1], 1, n, i, 1);
if (lst[x]) t[i] = t.modify(t[i], 1, n, lst[x], -1);
lst[x] = i;
}
int pre_ans = 0;
for (int i = 1, u, v; i <= m; ++i) {
scanf("%d %d", &u, &v);
u = (u + pre_ans) % n + 1, v = (v + pre_ans) % n + 1;
if (u > v) swap(u, v);
printf("%d\n", (pre_ans = t.query(t[v], 1, n, u, v)));
}
return 0;
}
【BZOJ 4771】七彩树
给出一棵树,点有颜色,每次询问给出
考虑第
具体而言,对于节点
查
时间复杂度
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 10;
int n, m;
typedef long long ll;
namespace FastIO {
char buf[MAXN << 5], *p1 = buf, *p2 = buf;
extern __inline__ __attribute__ ((always_inline)) char nc() {
return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXN << 5, stdin), p1 == p2) ? EOF : *p1++;
}
template <class T>
inline void read(T& x) {
x = 0;
register bool flag = 0;
register char ch = nc();
for (; ch < 48 || ch > 57; flag |= ch == '-', ch = nc());
for (; ch > 47 && ch < 58; x = (x << 3) + (x << 1) + (ch ^ 48), ch = nc());
if (flag) x = -x;
}
inline void out(const ll& x) {
if (x > 9) out(x / 10);
putchar(x % 10 + 48);
}
extern __inline__ __attribute__ ((always_inline)) void write(const ll& x) {
out(x < 0 ? -x : x), putchar('\n');
}
} using namespace FastIO;
struct Persistent_Segment_Tree {
#define mid ((l + r) >> 1)
#define ls(_) t[_].ls
#define rs(_) t[_].rs
#define lq(_) t[_].ls, l, mid
#define rq(_) t[_].rs, mid + 1, r
int node_cnt, rt[MAXN];
int& operator [](const int& x) { return rt[x]; }
struct node { int ls, rs, data; } t[7123620 + 10];
int build(int l, int r) {
int cur = ++node_cnt; t[cur].data = 0;
if (l == r) return cur;
ls(cur) = build(l, mid), rs(cur) = build(mid + 1, r);
return cur;
}
int modify(int pre, int l, int r, int pos, int val) {
int cur = ++node_cnt; t[cur] = t[pre], t[cur].data += val;
if (l == r) { return cur; }
if (pos <= mid) ls(cur) = modify(ls(pre), l, mid, pos, val);
else rs(cur) = modify(rs(pre), mid + 1, r, pos, val);
return cur;
}
int query(int cur, int l, int r, int ql, int qr, bool flg = true) {
if (ql <= l && r <= qr) return t[cur].data;
int ret = 0;
if (ql <= mid) ret += query(lq(cur), ql, qr, false);
if (qr > mid) ret += query(rq(cur), ql, qr, false);
return ret;
}
} t;
int head[MAXN], e_cnt;
struct Edge { int to, nxt; } e[MAXN << 1];
void add(int u, int v) { e[++e_cnt].to = v, e[e_cnt].nxt = head[u], head[u] = e_cnt; }
struct Vertix { int dfn, slf, fa, dep, col, sz, son, top; bool operator <(const Vertix& _) const { return dep < _.dep; } } vtx[MAXN];
int dtp[MAXN];
vector<int> vv[MAXN];
int dfs_clock;
void dfs(int u, int fr) {
vtx[u].dep = vtx[fr].dep + 1, vtx[u].sz = 1, vtx[u].slf = u;
vv[vtx[u].dep].push_back(u);
int max_size = 0;
for (int _ = head[u], v; _; _ = e[_].nxt) {
v = e[_].to;
dfs(v, u);
vtx[u].sz += vtx[v].sz;
if (vtx[v].sz > max_size) max_size = vtx[v].sz, vtx[u].son = v;
}
}
void dfs2(int u, int top) {
vtx[u].top = top;
vtx[u].dfn = ++dfs_clock, dtp[dfs_clock] = u;
if (vtx[u].son) dfs2(vtx[u].son, top);
for (int _ = head[u], v; _; _ = e[_].nxt) {
v = e[_].to;
if (v != vtx[u].son) dfs2(v, v);
}
}
int lca(int u, int v) {
while (1) {
if (vtx[u].top == vtx[v].top) return vtx[u].dep < vtx[v].dep ? u : v;
if (vtx[vtx[u].top].dep > vtx[vtx[v].top].dep) swap(u, v);
v = vtx[vtx[v].top].fa;
}
}
set<int> col[MAXN];
void init() {
dfs_clock = 0; e_cnt = 0; memset(head, 0, sizeof head);
for (int i = 1; i <= n; ++i) vv[i].clear(), col[i].clear();
memset(vtx, 0, sizeof vtx), memset(dtp, 0, sizeof dtp);
t.node_cnt = 0;
}
void solve() {
read(n), read(m);
init();
for (int i = 1; i <= n; ++i) read(vtx[i].col);
for (int i = 2, anc; i <= n; ++i) {
read(anc);
add(anc, i);
vtx[i].fa = anc;
}
dfs(1, 0); dfs2(1, 1);
t[0] = t.build(1, n);
for (int cur_dep = 1; cur_dep <= n; ++cur_dep) {
t[cur_dep] = t[cur_dep - 1];
for (auto _cur : vv[cur_dep]) {
Vertix cur = vtx[_cur];
t[cur_dep] = t.modify(t[cur_dep], 1, n, cur.dfn, 1);
auto it = col[cur.col].lower_bound(cur.dfn);
int pre = 0, nxt = 0;
if (it != col[cur.col].end()) nxt = dtp[(*it)];
if (it != col[cur.col].begin()) pre = dtp[(*--it)];
if (pre) t[cur_dep] = t.modify(t[cur_dep], 1, n, vtx[lca(pre, cur.slf)].dfn, -1);
if (nxt) t[cur_dep] = t.modify(t[cur_dep], 1, n, vtx[lca(nxt, cur.slf)].dfn, -1);
if (nxt && pre) t[cur_dep] = t.modify(t[cur_dep], 1, n, vtx[lca(nxt, pre)].dfn, 1);
col[cur.col].insert(cur.dfn);
}
}
int pre_ans = 0;
for (int i = 1, x, d; i <= m; ++i) {
read(x), read(d);
x ^= pre_ans, d ^= pre_ans;
pre_ans = t.query(t[min(vtx[x].dep + d, n)], 1, n, vtx[x].dfn, vtx[x].dfn + vtx[x].sz - 1);
write(pre_ans);
}
}
int main() {
int t; read(t);
while (t --) solve();
return 0;
}
Zju2112 Dynamic Rankings
单点修改,询问区间第
原来的静态区间第
现在还有单点修改,仍使用前缀和则单次修改会达到
单点修改,区间求和,考虑树状数组,第
复杂度
代码咕了