可持久化线段树 可持久化 01Trie 简述与做题记录

可持久化线段树与 01Trie 的一些例题。

可持久化线段树

概述

对于单点修改，只需要考虑从根到这个点的路径上的 \log n 个被影响的节点即可。

对于区间修改，采用标记永久化：

标记永久化有两种写法：

第一种写法，标记维护覆盖该区间的修改的贡献，其余不完全覆盖直接在修改时计算贡献即可。

例如区间加：

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小数

询问区间第 k 小。

做主席树题先想如何用 n 棵线段树做。

考虑建出 n 棵权值线段树，第 i 棵代表下标在 [1, i] 中的所有数建出的权值线段树。

由于所有权值线段树形态都相同，询问 [l, r] 中的第 k 小，直接在树上二分即可。

然后用主席树的替换权值线段树即可。

时间复杂度 O(n \log n).

#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】超级马里奥

询问区间小于等于 k 的数的个数。

同样，建出 n 个权值线段树，i 棵表示前缀的权值线段树。

同样，由于形态相同，对于询问 (l, r, k)，求出第 r 棵线段树小于等于 k 的个数减去 l - 1 棵的即可。

时间复杂度 O(n \log n)。

#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 情报传递

给出一棵树，初始点权都为 0。两种操作，每次操作都会使时刻 +1：

• 给出 x，代表从下一时刻起，x 的点权会变为 1，并每个时刻 +1。
• 给出 u, v, k，求该时刻时，u 到 v 的路径上有多少个点的权值大于 k。

保证一个点至多被修改 1 次。

n, Q \leq 2\times 10^5。

对于询问操作 i，等价与在 u 到 v 的路径上，有多少个点被修改的时刻 d_i - d_x > k，即 d_x < d_i - k。

那么我们离线后，将每个节点的权值记为被修改的时刻，询问只需要询问 u 到 v 的路径上小于 d_i - k 的点的个数即可。

看起来只能树剖+权值线段树（主席树），不过这并不是唯一的解法。

对于第 u 号节点，其上的权值线段树是基于其父亲版本的，加入了自己的权值的线段树。由于小于等于某个数的个数具有可减性，只需要类似求 LCA 那样。

答案即为 ans(u) + ans(v) - ans(\operatorname{lca}(u, v)) * 2 + [val(\operatorname{lca}(u, v)) < d_i - k]，其中 ans(u) 代表 u 上的权值线段树的小于 d_i - k 的个数，val(u) 代表 u 的权值。

时间复杂度 O(n \log n)。

#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】任务查询系统

维护 n 个可重集合，两种操作：

• 给出 l, r, x，代表将 x 插入到 [l, r] 的集合。
• 给出 p, k，求出第 p 个集合小于等于 k 的数的和。

n, q \leq 100000。

通过差分，将区间加，单点求和变成单点加，前缀求和。然后主席树上二分即可。

时间复杂度 O(n \log n)。

#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 疯狂的颜色序列

静态区间数颜色。

n \leq 5 \times 10^5。

对于颜色 c 对区间 [l, r] 的颜色数的贡献，至多只有 1。如果我们只计算 c 在 [l, r] 中的最后一次出现也是正确的。

考虑主席树，对下标建树，第 i 棵基于第 i - 1 棵，表示下标为 i 对答案的贡献，且每个颜色只会在最后一次出现作出贡献。

如何建树？建树的同时维护 lst(c) 表示当前颜色 c 的最后一次出现在哪里，建第 i 棵时将 lst(col(i)) 减去 1，i 加上 1 即可。

区间数颜色，维护一下区间和就行。

具体而言，对于询问 (l, r)，求出第 r 棵上的 [l, r] 的和。

时间复杂度 O(n \log n)。

#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】七彩树

给出一棵树，点有颜色，每次询问给出 x, d，求在 x 的子树中，深度不超过 d 的点的颜色数。

n \leq 5 \times 10^5。

考虑第 i 棵线段树代表所有深度小于等于 i 的点的颜色的贡献（每个点的点权就是贡献）。先不管深度的限制，倘若我们要使一棵树的子树权值和（当然是在线段树上）就是这棵数的答案，那么我们必须保证同样的颜色的重复贡献必须被消除。

具体而言，对于节点 v，以及在 dfs 序上相邻的两个同色点 u, w，当我们加入 v 时，要将 \operatorname{LCA}(u, v), \operatorname{LCA}(v, w) 的点权 -1。但考虑容斥，还得将 \operatorname{LCA}(u, w) 的点权 +1。

查 x 子树深度不超过 d 的时候，查询第 \operatorname{dep}(x) + d 棵子树中 x 的权值和即可。

时间复杂度 O(n \log n)。瓶颈在于求 LCA。

#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

单点修改，询问区间第 k 小。

原来的静态区间第 k 小用的是前缀和的思想，O(n) 预处理 O(1) 询问（指调用主席树的次数，真实复杂度还要乘上 \log n）。

现在还有单点修改，仍使用前缀和则单次修改会达到 O(n) 的复杂度。

单点修改，区间求和，考虑树状数组，第 i 棵主席树基于 i - \operatorname{lowbit}(i) 棵，即按照树状数组的结构建出主席树，这样就是 O(\log n) 修改询问了。

复杂度 O(n \log ^ 2n)。

代码咕了