可持久化与嵌套数据结构

可持久化数据结构可以保留每一个历史版本，嵌套则指的是“树套树”，将数据结构嵌套来实现更加强大的功能。

可持久化数据结构

大致意思上是可以保留数据结构的历史版本，不过还有更多的用处。

概念

所有版本都可以访问，但是只有最新版本可以修改，称之为部分可持久化。
所有版本都既可以访问又可以修改，称之为完全可持久化。
若支持将两个历史版本合并，则又称为汇合可持久化（Confluently Persistent）。

无论如何，基本思想是修改时要保留原来的内容。

可持久化线段树

毫无疑问，这是最重要的可持久化数据结构，因为它可以用来实现可持久化数组，进而实现更多内容。

概述

当我们进行修改的时候，最暴力的想法就是：我再建一棵线段树不就得了嘛！

但是你觉得可能吗？空间炸裂了……

对于点修改来说，一次修改至多会影响 $O(\log n)$ 个节点，所以我们只需要复制这 $O(\log n)$ 个节点即可。但是复制？这样的话就需要记录左右儿子的编号，实现的时候需要采用动态开点，这样可以将新建的节点的儿子编号拉到原线段树上。

struct Node {
    int lc, rc; // 左右节点编号
    int dat; // 当前维护的值
}T[SIZE * 2]; // 终于只需要二倍空间啦！
int root[MAXQ], tot; // 每次修改的根节点编号，节点个数

int build(int l, int r) {
    int o = ++tot;
    if (l == r) return T[o].dat = a[l], o;
    int mid = l + r >> 1;
    T[o].lc = build(l, mid); T[o].rc = build(mid + 1, r);
    T[o].dat = T[T[o].lc].dat + T[T[o].rc].dat;
    return o;
}

int main(void) {
    root[0] = build(1, n); // 建立初始的可持久化线段树
}

点修改

在修改的时候，变化的内容的节点编号要新建，而没有变化的直接复制原来的版本信息即可。

修改了位置 1 的值，只有节点 1248 的值会发生变化，需要新建

int main(void) {
    root[i] = update(root[i - 1], 1, n, x, k); // 在第 i - 1 个版本的基础上创建第 i 个版本
}

int update(int pre, int l, int r, int x, int k) { // 在 pre 号节点的基础上，x 加上 k
    int o = ++tot; // 先新建这个节点
    T[o] = T[pre]; // 先把原来的东西复制过来
    if (l == r) return T[o].dat += k, o; // 叶子节点直接修改
    int mid = l + r >> 1;
    if (x <= mid) T[o].lc = update(T[pre].lc, l, mid, x, k); // 修改的内容在左子区间，将左儿子的编号修改为新建节点的编号
    else T[o].rc = update(T[pre].rc, mid + 1, r, x, k); // 修改的内容在右子区间，修改右儿子的编号
    T[o].dat = T[T[o].lc].dat + T[T[o].rc].dat; // 维护当前节点的值
    return o; // 返回当前节点
}

这种实现可持久化的方式称为 Path Copy，在竞赛中功能是足够的，但问题是消耗的空间较大（但是一般没人卡）。

可持久化数组

模板。

可持久化线段树可以用来实现可持久化数组，而且非常简单，因为只需要做到单点修改和单点查询。

所以 maintain 之类的操作根本不需要，查询的时候几乎跟普通线段树一模一样。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

struct Node {
    int lc, rc;
    int dat;
} T[44000005];
int tot, root[1000005];

int n, m;
int a[1000005];

int build(int l, int r) {
    int o = ++tot;
    if (l == r) return T[o].dat = a[l], o;
    int mid = l + r >> 1;
    T[o].lc = build(l, mid); T[o].rc = build(mid + 1, r);
    return o;
}

int update(int pre, int l, int r, int x, int k) {
    int o = ++tot;
    T[o] = T[pre];
    if (l == r) return T[o].dat = k, o; 
    int mid = l + r >> 1;
    if (x <= mid) T[o].lc = update(T[pre].lc, l, mid, x, k);
    else T[o].rc = update(T[pre].rc, mid + 1, r, x, k);
    return o;
}

int query(int o, int l, int r, int x) {
    if (l == r) return T[o].dat;
    int mid = l + r >> 1;
    if (x <= mid) return query(T[o].lc, l, mid, x);
    return query(T[o].rc, mid + 1, r, x);
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    root[0] = build(1, n);
    for (int i = 1; i <= m; ++i) {
        int pre, op, x, k; scanf("%d%d%d", &pre, &op, &x);
        if (op == 1) {
            scanf("%d", &k);
            root[i] = update(root[pre], 1, n, x, k);
        } else printf("%d\n", query(root[i] = root[pre], 1, n, x));
    }
    return 0;
}

可持久化并查集

模板。基于可持久化数组可以实现可持久化并查集（将并查集的数组可持久化即可），但是注意路径压缩会使得树的形态改变而无法可持久化，因此只能使用按秩合并。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;
const int N = 100005; 

int n, m, ver; 

struct Node {
    int ls, rs; 
    int dat; 
};

struct SegmentTree {
    Node T[N * 40];
    int tot, root[200005], a[100005];

    int build(int l, int r) {
        int o = ++tot; if (l == r) return T[o].dat = a[l], o;
        int mid = l + r >> 1; 
        T[o].ls = build(l, mid); T[o].rs = build(mid + 1, r);
        return o;
    }
    int update(int pre, int l, int r, int x, int k) {
        int o = ++tot; T[o] = T[pre];
        if (l == r) return T[o].dat = k, o;
        int mid = l + r >> 1;
        if (x <= mid) T[o].ls = update(T[pre].ls, l, mid, x, k);
        else T[o].rs = update(T[pre].rs, mid + 1, r, x, k);
        return o;
    }
    int query(int o, int l, int r, int x) {
        if (l == r) return T[o].dat;
        int mid = l + r >> 1;
        if (x <= mid) return query(T[o].ls, l, mid, x);
        return query(T[o].rs, mid + 1, r, x);
    }
} fa, siz;

int find(int x) {
    int tmp = fa.query(fa.root[ver], 1, n, x);
    if (tmp == x) return x; 
    return find(tmp);
}
void merge(int x, int y) {
    x = find(x), y = find(y);
    if (x == y) return; 
    int sx = siz.query(siz.root[ver], 1, n, x), sy = siz.query(siz.root[ver], 1, n, y);
    if (sx > sy) swap(x, y), swap(sx, sy);
    fa.root[ver] = fa.update(fa.root[ver], 1, n, x, y);
    siz.root[ver] = siz.update(siz.root[ver], 1, n, y, sx + sy);
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) fa.a[i] = i, siz.a[i] = 1; 
    fa.root[0] = fa.build(1, n); siz.root[0] = siz.build(1, n); 
    for (ver = 1; ver <= m; ++ver) {
        int op, x, y; scanf("%d%d", &op, &x);
        fa.root[ver] = fa.root[ver - 1]; siz.root[ver] = siz.root[ver - 1];
        if (op == 1) {
            scanf("%d", &y);
            merge(x, y);
        } else if (op == 2) {
            fa.root[ver] = fa.root[x]; 
            siz.root[ver] = siz.root[x]; 
        } else {
            scanf("%d", &y);
            puts(find(x) == find(y) ? "1" : "0");
        }
    }
    return 0;
}

主席树

也就是可持久化权值线段树。

模板。

我们可以依次读入这些数后离散化，然后扫描每个数，建立主席树，第 $k$ 个版本维护 $[1,k]$ 各个数值。由于权值树是可以直接相加或相减的，所以整个过程类似于差分。

正常的方式是二分出答案，可以很方便的知道有多少个小于 $x$ 的数。这样就可以直接在主席树上二分，在离散化后，假设有 $m$ 个数，那么值域就变为了 $[1,m]$ 。 $dat$ 代表所对应的值域 $[L,R]$ 插入了多少个数。插入一个数后，就要在它离散化后的位置上加上 $1$ 。查询的时候，有 $T[r_i].dat - T[l_i-1].dat$ 的值就是 $[l_i,r_i]$ 中有多少个数落在值域 $[L,R]$ 上。

查看代码

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
const int MAXN = 200005;

struct Node
{
    int lc, rc;
    int dat;
}T[MAXN * 20];
int tot, root[200005];

int n, Q, m;
int a[200005];
int tmp[200005];

void init(void)
{
    for (int i = 1; i <= n; ++i)
        tmp[i] = a[i];
    sort(tmp + 1, tmp + n + 1);
    m = unique(tmp + 1, tmp + n + 1) - (tmp + 1);
    for (int i = 1; i <= n; ++i)
        a[i] = lower_bound(tmp + 1, tmp + m + 1, a[i]) - tmp;
}

int build(int l, int r) // 一开始只是新建节点，但是没有数值
{
    int o = ++tot;
    if (l == r) return o;
    int mid = l + r >> 1;
    T[o].lc = build(l, mid);
    T[o].rc = build(mid + 1, r);
    return o;
}

int update(int pre, int l, int r, int x, int k)
{
    int o = ++tot;
    T[o] = T[pre];
    if (l == r)
    {
        T[o].dat += k;
        return o;
    }
    int mid = l + r >> 1;
    if (x <= mid) T[o].lc = update(T[pre].lc, l, mid, x, k);
    else T[o].rc = update(T[pre].rc, mid + 1, r, x, k);
    T[o].dat = T[T[o].lc].dat + T[T[o].rc].dat;
    return o;
}

int query(int p, int q, int l, int r, int k) // 查询的时候同步进行查询
{
    if (l == r) return l; // 值域只有一个，直接返回
    int mid = l + r >> 1, res = T[T[q].lc].dat - T[T[p].lc].dat; // 落在 [L, mid] 的值域的数的个数
    if (k <= res) return query(T[p].lc, T[q].lc, l, mid, k); // 要查的比 res 小，在左子节点查
    return query(T[p].rc, T[q].rc, mid + 1, r, k - res); // 比 res 大，减去 res 在右子节点查
}

int main(void)
{
    scanf("%d%d", &n, &Q);
    for (int i = 1; i <= n; ++i)
        scanf("%d", a + i);
    init();
    root[0] = build(1, m);
    for (int i = 1; i <= n; ++i)
        root[i] = update(root[i - 1], 1, m, a[i], 1);
    while (Q--)
    {
        int l, r, k;
        scanf("%d%d%d", &l, &r, &k);
        printf("%d\n", tmp[query(root[l - 1], root[r], 1, m, k)]);
    }
    return 0;
}

至于空间到底开多大，要看修改次数，然后按照空间复杂度计算即可，如果内存限制允许可以稍微开大一点。本题中 $\lceil\log_2 2\times 10^5\rceil=18$ ，再加上一个初始版本的两倍空间，开到 $20$ 倍空间就足够了。

很显然这种问题如果不强制在线的话可以直接使用整体二分解决。

区间修改

如果正常使用永久化的话可以非常简单的支持区间修改，模板，代码如下：

#include <bits/stdc++.h>
using namespace std; 
typedef long long i64; 

int n, m; 
int a[100005]; 
struct Node {
    int ls, rs; 
    i64 v, tag; 
} T[40 * 100005]; 
int rt[100005], tot; 

int build(int l, int r) {
    int o = ++tot; 
    if (l == r) return T[o].v = a[l], o; 
    int mid = l + r >> 1; 
    T[o].ls = build(l, mid); T[o].rs = build(mid + 1, r); 
    T[o].v = T[T[o].ls].v + T[T[o].rs].v; 
    return o; 
}
int update(int pre, int l, int r, int x, int y, int k) {
    int o = ++tot; T[o] = T[pre]; 
    if (x <= l && r <= y) return T[o].tag += k, T[o].v += (r - l + 1) * k, o; 
    int mid = l + r >> 1; 
    if (x <= mid) T[o].ls = update(T[o].ls, l, mid, x, y, k); 
    if (mid < y) T[o].rs = update(T[o].rs, mid + 1, r, x, y, k); 
    T[o].v = T[T[o].ls].v + T[T[o].rs].v + T[o].tag * (r - l + 1); 
    return o; 
}
i64 query(int o, int l, int r, int x, int y, i64 tag) {
    if (x <= l && r <= y) return T[o].v + tag * (r - l + 1); 
    int mid = l + r >> 1; i64 ans = 0; tag += T[o].tag; 
    if (x <= mid) ans += query(T[o].ls, l, mid, x, y, tag); 
    if (mid < y) ans += query(T[o].rs, mid + 1, r, x, y, tag); 
    return ans; 
}

int main(void) {
    ios::sync_with_stdio(0); 
    cin >> n >> m; 
    for (int i = 1; i <= n; ++i) cin >> a[i]; 
    rt[0] = build(1, n); 
    for (int i = 1, t = 0; i <= m; ++i) {
        char op; int l, r, k; cin >> op; 
        if (op == 'C') {
            cin >> l >> r >> k; ++t; 
            rt[t] = update(rt[t - 1], 1, n, l, r, k); 
        } else if (op == 'Q') {
            cin >> l >> r; 
            cout << query(rt[t], 1, n, l, r, 0) << "\n"; 
        } else if (op == 'H') {
            cin >> l >> r >> k; 
            cout << query(rt[k], 1, n, l, r, 0) << "\n"; 
        } else cin >> t; 
    }
    return 0; 
}

可持久化 Trie

按照以下步骤可以在可持久化 Trie 中插入一个字符串：

设当前根节点为 $x$ ，基于 $pre$ 版本建立；
先将 $x$ 的儿子全部指向 $pre$ 的儿子，然后将要插入的数值指向一个新建节点；
同时让 $x,pre$ 往下走，并回到第 $2$ 步直到扫描完整个字符串。

实际上大部分需要使用可持久化 Trie 的题目中使用的都是可持久化 01 Trie。

[Luogu P4735] 最大异或和。利用差分的思想，求出前缀异或和，这样就是求 $x\oplus s[N]\oplus a[p](l-1\le p\le r-1)$ 。然后在 Trie 树插入时记录 $val$ 代表当前节点的出现次数，差分的时候就可以直接用两个版本相减得知当前节点是否出现。

查看代码

#include <iostream>
#include <cstdio>

using namespace std;

int n, m; 
int a[600005], s[600005]; 
int root[600005], tot, ch[18600005][2], val[18600005];

void insert(int x, int pre, int v) {
    for (int i = 28; i >= 0; --i) {
        val[x] = val[pre] + 1; int c = 1 << i & v ? 1 : 0;
        ch[x][!c] = ch[pre][!c]; 
        if (!ch[x][c]) ch[x][c] = ++tot; 
        x = ch[x][c]; pre = ch[pre][c]; 
    }
    val[x] = val[pre] + 1;
}
int query(int x, int y, int v) {
    int res = 0; 
    for (int i = 28; i >= 0; --i) {
        int c = 1 << i & v ? 1 : 0; 
        if (val[ch[x][!c]] - val[ch[y][!c]]) res |= 1 << i, x = ch[x][!c], y = ch[y][!c]; 
        else x = ch[x][c], y = ch[y][c]; 
    }
    return res; 
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i); s[i] = s[i - 1] ^ a[i];
        root[i] = ++tot; insert(root[i], root[i - 1], s[i]);
    }
    char op[5]; int l, r, x; 
    while (m--) {
        scanf("%s", op);
        if (op[0] == 'A') {
            ++n; scanf("%d", a + n); s[n] = s[n - 1] ^ a[n];
            root[n] = ++tot; insert(root[n], root[n - 1], s[n]);
        } else {
            scanf("%d%d%d", &l, &r, &x); 
            if (l == 1) printf("%d\n", max(s[n] ^ x, query(root[r - 1], 0, s[n] ^ x)));
            else printf("%d\n", query(root[r - 1], root[l - 2], s[n] ^ x));
        }
    }
    return 0;
}

可持久化平衡树

平衡树也是可以持久化的，而且大部分平衡树都可以可持久化。如果是插入删除的平衡树（Treap），只需要在修改的路径上和旋转的时候复制一下即可。对于维护父亲节点的平衡树如果可持久化后常数会爆炸，所以不常用。

对于分裂合并的平衡树，只需要在分裂合并时新建节点，这样非常方便。主要的作用是可以复制区间，其它方面意义不大。因为可持久化 Trie 也可以维护权值，而且跑的往往比平衡树快。

一般 OI 中能用到的只有可持久化 FHQ-Treap。模板，在 merge 的时候也应该复制节点，但是本题并没有单独需要调用 merge 的，merge 操作只是为了合并分裂后的序列，因此不需要复制新节点。代码如下：

查看代码

#include <bits/stdc++.h>
using namespace std;
const int N = 200005; 
typedef long long i64; 

mt19937 Rand(time(0));
struct Node {
    int siz, rnd; i64 sum, val; 
    int ls, rs; bool rev; 
} T[N * 105]; int tot, root[N];
int newNode(i64 v) {
    ++tot; T[tot].siz = 1; T[tot].rnd = Rand();
    T[tot].sum = T[tot].val = v; 
    return tot; 
}
int copyNode(int x) {
    T[++tot] = T[x];
    return tot; 
}
void pushup(int p) {
    T[p].siz = T[T[p].ls].siz + T[T[p].rs].siz + 1; 
    T[p].sum = T[T[p].ls].sum + T[T[p].rs].sum + T[p].val;
}
void pushdown(int p) {
    if (!T[p].rev) return;
    if (T[p].ls) T[T[p].ls = copyNode(T[p].ls)].rev ^= 1; 
    if (T[p].rs) T[T[p].rs = copyNode(T[p].rs)].rev ^= 1; 
    swap(T[p].ls, T[p].rs); T[p].rev = 0; 
}
void split(int p, int S, int &x, int &y) {
    if (!p) return x = y = 0, void();
    int o = copyNode(p); pushdown(o);
    if (T[T[o].ls].siz + 1 <= S) {
        x = o;
        split(T[o].rs, S - T[T[o].ls].siz - 1, T[o].rs, y);
    }
    else {
        y = o;
        split(T[o].ls, S, x, T[o].ls);
    } pushup(o);
}
int merge(int x, int y) {
    if (x == 0 || y == 0) return x + y; 
    if (T[x].rnd > T[y].rnd) {
        pushdown(x); T[x].rs = merge(T[x].rs, y); pushup(x);
        return x;
    } else {
        pushdown(y); T[y].ls = merge(x, T[y].ls); pushup(y);
        return y; 
    }
}

int main(void) {
    int m, v, op, p, l, r, a, b, c; scanf("%d", &m); i64 x, last = 0; 
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &v, &op); root[i] = root[v];
        if (op == 1) {
            scanf("%d%lld", &p, &x); p ^= last, x ^= last; 
            split(root[i], p, a, b);
            b = merge(newNode(x), b);
            root[i] = merge(a, b);
        } else if (op == 2) {
            scanf("%d", &p); p ^= last; 
            split(root[i], p - 1, a, b);
            split(b, 1, b, c);
            root[i] = merge(a, c);
        } else if (op == 3) {
            scanf("%d%d", &l, &r); l ^= last, r ^= last; 
            split(root[i], l - 1, a, b);
            split(b, r - l + 1, b, c);
            T[b].rev ^= 1; root[i] = merge(a, merge(b, c)); 
        } else {
            scanf("%d%d", &l, &r); l ^= last, r ^= last; 
            split(root[i], l - 1, a, b);
            split(b, r - l + 1, b, c);
            printf("%lld\n", last = T[b].sum);
            root[i] = merge(a, merge(b, c));
        }
    }
    return 0;
}

嵌套数据结构

当问题不是强制在线时，往往可以使用 CDQ 分治或整体二分来解决。下面介绍的嵌套都属于树套树，但也有不是树套树的嵌套数据结构，比如底层分块和树套 vector 之类的。应用非常灵活，面对不同的问题设计合适的数据结构即可。

概述

最简单的例子是树状数组套树，比如大家都写过的树状数组套树状数组：

for (int i = x; i <= n; i += lowbit(i))
    for (int j = y; j <= n; j += lowbit(j))
        C[i][j] += k;

实际上这是什么？一个树状数组里面保存的不是数，而是一个树状数组。比如说我现在要支持单点修改，查询区间中小于等于 $y$ 的数的个数，只需要像这样：

void update(int x, int k) {
    for (int i = x; i <= n; i += lowbit(i)) {
        remove(root[i], a[i]); // 平衡树操作
        insert(root[i], k); 
    }
}
int query(int x, int k) {
    int res = 0; 
    for (int i = x; i; i -= lowbit(i))
        res += rank(root[i], y);
    return res; 
}

由于只会访问到 $\log$ 棵平衡树，所以单次操作时间复杂度为 $O(\log^2 n)$ 。

这是搞什么的？普通的树状数组可以支持单点修改，区间查询值，可以使用一个数组来维护。树状数组套平衡树用到了一个可以插入删除查询排名的平衡树，还需要支持序列的单点修改和区间查询，因此可以使用一个平衡树数组来维护。于是就有了树状数组套平衡树。

线段树套平衡树

模板。

维护一个序列，支持单点修改，查询区间排名、区间 kth、区间前驱后继。

由于查询的东西不可以差分，因此无法使用树状数组套树求解，因此考虑线段树套树。

普通的线段树维护每一个区间的信息，每次修改更新 $\log n$ 个节点的和，每次查询用 $\log n$ 个不相交的线段来求出答案。而线段树套平衡树则每个节点用一棵平衡树来储存当前节点所代表的区间的信息，每次修改更新 $\log n$ 棵平衡树，每次查询用 $\log n$ 个不相交的节点的平衡树拼出答案。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;

mt19937 Rand(time(0)); 
struct TreapNode {
    int ch[2], siz, rnd, cnt;
    int val;     
} T[2000005];
int tot; 
void maintain(int p) { 
    T[p].siz = T[T[p].ch[0]].siz + T[T[p].ch[1]].siz + T[p].cnt; 
}
int newNode(int val) {
    ++tot; T[tot].rnd = Rand(); T[tot].val = val; 
    T[tot].cnt = T[tot].siz = 1; T[tot].ch[0] = T[tot].ch[1] = 0; 
    return tot; 
}
void rotate(int& p, int d) { // d = 0 左旋，d = 1 右旋
    int q = T[p].ch[d ^ 1];
    T[p].ch[d ^ 1] = T[q].ch[d]; T[q].ch[d] = p; p = q;
    maintain(T[p].ch[d]); maintain(p);
}
void insert(int &p, int val) {
    if (!p) p = newNode(val);
    else if (val == T[p].val) ++T[p].cnt;
    else {
        int d = (val < T[p].val ? 0 : 1); insert(T[p].ch[d], val);
        if (T[T[p].ch[d]].rnd > T[p].rnd) rotate(p, d ^ 1);
    } maintain(p);
}
void Remove(int &p, int val) {
    if (!p) return;
    if (val == T[p].val) {
        if (T[p].cnt > 1) --T[p].cnt;
        else {
            if (!T[p].ch[0] && !T[p].ch[1]) p = 0;
            else {
                if (!T[p].ch[0]) rotate(p, 0), Remove(T[p].ch[0], val);
                else if (!T[p].ch[1]) rotate(p, 1), Remove(T[p].ch[1], val);
                else {
                    int d = T[T[p].ch[0]].rnd > T[T[p].ch[1]].rnd ? 1 : 0;
                    rotate(p, d); Remove(T[p].ch[d], val);
                }
            }
        }
    } else Remove(T[p].ch[val < T[p].val ? 0 : 1], val);
    if (p) maintain(p);
}
int Rank(int p, int val) { // 小于 val 的数的个数
    if (!p) return 0;
    if (val < T[p].val) return Rank(T[p].ch[0], val);
    if (val == T[p].val) return T[T[p].ch[0]].siz;
    return T[T[p].ch[0]].siz + T[p].cnt + Rank(T[p].ch[1], val);
}
int GetPre(int p, int k) {
    if (!p) return -INF;
    if (T[p].val >= k) return GetPre(T[p].ch[0], k);
    return max(T[p].val, GetPre(T[p].ch[1], k));
}
int GetSuf(int p, int k) {
    if (!p) return INF;
    if (T[p].val <= k) return GetSuf(T[p].ch[1], k);
    return min(T[p].val, GetSuf(T[p].ch[0], k));
}

int n, m; 
int a[50005], root[200005]; 
void build(int o, int l, int r) {
    for (int i = l; i <= r; ++i) insert(root[o], a[i]); 
    if (l == r) return;
    int mid = l + r >> 1;
    build(o << 1, l, mid); build(o << 1 | 1, mid + 1, r);
}
void update(int o, int l, int r, int x, int k) {
    Remove(root[o], a[x]); insert(root[o], k);
    if (l == r) return; 
    int mid = l + r >> 1;
    if (x <= mid) update(o << 1, l, mid, x, k);
    else update(o << 1 | 1, mid + 1, r, x, k);
}
int queryRank(int o, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) return Rank(root[o], k);
    int mid = l + r >> 1, res = 0;
    if (x <= mid) res += queryRank(o << 1, l, mid, x, y, k);
    if (mid < y) res += queryRank(o << 1 | 1, mid + 1, r, x, y, k);
    return res;
}
int queryPre(int o, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) return GetPre(root[o], k);
    int mid = l + r >> 1, res = -INF;
    if (x <= mid) res = max(res, queryPre(o << 1, l, mid, x, y, k));
    if (mid < y) res = max(res, queryPre(o << 1 | 1, mid + 1, r, x, y, k));
    return res;
}
int querySuf(int o, int l, int r, int x, int y, int k) {
    if (x <= l && r <= y) return GetSuf(root[o], k);
    int mid = l + r >> 1, res = INF;
    if (x <= mid) res = min(res, querySuf(o << 1, l, mid, x, y, k));
    if (mid < y) res = min(res, querySuf(o << 1 | 1, mid + 1, r, x, y, k));
    return res; 
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i); 
    build(1, 1, n);
    while (m--) {
        int op, l, r, pos, k; scanf("%d", &op); 
        if (op == 1) {
            scanf("%d%d%d", &l, &r, &k);
            printf("%d\n", queryRank(1, 1, n, l, r, k) + 1);
        } else if (op == 2) {
            scanf("%d%d%d", &l, &r, &k); // 排名为 k 的数
            int L = -1, R = 100000001;
            while (L + 1 != R) {
                int mid = L + R >> 1;
                if (queryRank(1, 1, n, l, r, mid) < k) L = mid; 
                else R = mid; 
            }
            printf("%d\n", L);
        } else if (op == 3) {
            scanf("%d%d", &pos, &k);
            update(1, 1, n, pos, k); a[pos] = k; 
        } else if (op == 4) {
            scanf("%d%d%d", &l, &r, &k);
            printf("%d\n", queryPre(1, 1, n, l, r, k));
        } else {
            scanf("%d%d%d", &l, &r, &k);
            printf("%d\n", querySuf(1, 1, n, l, r, k));
        } 
    }
    return 0;
}

这样会导致在查询区间排名为 $k$ 的数时需要二分出答案。如果想要避免，可以采用动态开点权值线段树套 FHQ，外层维护权值，内层维护位置（可以通过根据大小的分裂来快速求出在位置区间 $[l,r]$ 内的数的个数），这样可以直接在权值线段树上二分出答案。

二维线段树

不同树套树的优劣

不管是什么树套树，常数都是巨大的（因为线段树和平衡树都很慢）。下面我们来对比一下不同的树套树：

Problemset

前面是一些基础题，最后部分放了一些综合应用。

可持久化数据结构

一些基础题。

[POI2014] KUR-Couriers

Portal.

建立主席树，查询的时候如果在 $[l,mid]$ 的值域的数的个数大于要求的数量，那么就到左子树查询，右子树同理，否则就是无解。因为右子树的值域区间大小只能比左子树的值域区间大小小或者相等，所以当落在左子树值域的数的个数满足限制条件时，右子树就不可能满足了，就不用查询了。

注意！由于这题的最优做法并不是主席树，所以主席树会被卡空间。初始版本是不能被建立的。要使用如代码中所示的方法。

查看代码

#include <cstdio>
const int MAXN = 500000;

int read(void) {
    int x = 0, c = getchar();
    while (c < '0' || c > '9') c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x;
}

struct Node {
    int lc, rc, dat;
}T[21 * MAXN + 480000];
int tot = 0, root[MAXN + 1];

int build(int l, int r)
{
    int o = tot++;
    if (l == r) return o;
    int mid = l + r >> 1;
    T[o].lc = build(l, mid);
    T[o].rc = build(mid + 1, r);
    return o;
}

void update(int &now, int l, int r, int x) // 注意 now 是引用，会被更新
{
    T[++tot] = T[now]; now = tot;
    T[tot].dat++;
    if (l == r) return;
    int mid = l + r >> 1;
    if (x <= mid) update(T[now].lc, l, mid, x);
    else update(T[now].rc, mid + 1, r, x);
}

int k;
int query(int p, int q, int l, int r)
{
    if (l == r) return l;
    int mid = l + r >> 1;
    if (2 * (T[T[q].lc].dat - T[T[p].lc].dat) > k) return query(T[p].lc, T[q].lc, l, mid);
    if (2 * (T[T[q].rc].dat - T[T[p].rc].dat) > k) return query(T[p].rc, T[q].rc, mid + 1, r);
    return 0;
}

int main(void)
{
    int n, m, l, r, x;
    n = read(), m = read();
    for (int i = 1; i <= n; ++i)
    {
        root[i] = root[i - 1];
        update(root[i], 1, n, read()); // 直接修改
    }
    while (m--)
    {
        l = read(), r = read();
        k = r - l + 1;
        printf("%d\n", query(root[l - 1], root[r], 1, n));
    }
    return 0;
}

[CF840D] Destiny

Portal.

乍一看跟上一题很像，但是无法保证如果左子树没有答案右子树就一定没有。因此考虑左子树满足条件没有答案时再到右子树查询。

慢着！这样复杂度不会变成 $O(n\log n)$ 吗？不会！注意到 $k\le 5$ ，复杂度可以均摊，左子树满足条件但是没有答案的事情最多发生 $k$ 次，数就会被用完。因此单次询问的复杂度是 $O(kn\log n)$ 的。

查看代码

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int ls, rs; 
    int val; 
} T[45 * 300005];
int root[300005], tot; 

int n, m, len, k; 
int a[300005]; 

int build(int l, int r) {
    int o = ++tot; 
    if (l == r) return o;
    int mid = l + r >> 1; 
    T[o].ls = build(l, mid); T[o].rs = build(mid + 1, r);
    return o; 
}
int update(int pre, int l, int r, int x, int k) {
    int o = ++tot; T[o] = T[pre]; 
    if (l == r) return T[o].val += k, o; 
    int mid = l + r >> 1; 
    if (x <= mid) T[o].ls = update(T[pre].ls, l, mid, x, k);
    else T[o].rs = update(T[pre].rs, mid + 1, r, x, k);
    T[o].val = T[T[o].ls].val + T[T[o].rs].val;
    return o; 
}
int query(int p, int q, int l, int r) {
    if (l == r) return l; 
    int mid = l + r >> 1; 
    if (k * (T[T[q].ls].val - T[T[p].ls].val) > len) {
        int res = query(T[p].ls, T[q].ls, l, mid); 
        if (res != -1) return res; 
    }
    if (k * (T[T[q].rs].val - T[T[p].rs].val) > len) return query(T[p].rs, T[q].rs, mid + 1, r); 
    return -1; 
}

int main(void) {
    scanf("%d%d", &n, &m); root[0] = build(1, n); 
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), root[i] = update(root[i - 1], 1, n, a[i], 1);
    while (m--) {
        int l, r; scanf("%d%d%d", &l, &r, &k); len = r - l + 1; 
        printf("%d\n", query(root[l - 1], root[r], 1, n));
    }
    return 0;
}

[Luogu P2633] Count on a tree

Portal.

利用树上差分的思想，同时查询四个版本的主席树。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, m, q, a[100005], b[100005];
vector<int> G[100005];

struct Node {
    int ls, rs; 
    int dat; 
} T[100005 * 36];
int tot, root[100005];

int build(int l, int r) {
    int o = ++tot; if (l == r) return o; int mid = l + r >> 1; 
    T[o].ls = build(l, mid); T[o].rs = build(mid + 1, r);
    return o;
}
int update(int pre, int l, int r, int x) {
    int o = ++tot; T[o] = T[pre];
    if (l == r) return ++T[o].dat, o;
    int mid = l + r >> 1;
    if (x <= mid) T[o].ls = update(T[pre].ls, l, mid, x);
    else T[o].rs = update(T[pre].rs, mid + 1, r, x);
    T[o].dat = T[T[o].ls].dat + T[T[o].rs].dat;
    return o;
}
int query(int u, int v, int lca, int fa, int l, int r, int k) {
    if (l == r) return l;
    int mid = l + r >> 1, res = T[T[u].ls].dat + T[T[v].ls].dat - T[T[lca].ls].dat - T[T[fa].ls].dat;
    if (k <= res) return query(T[u].ls, T[v].ls, T[lca].ls, T[fa].ls, l, mid, k);
    return query(T[u].rs, T[v].rs, T[lca].rs, T[fa].rs, mid + 1, r, k - res);
}

int dfn[100005], siz[100005], top[100005], num; 
int son[100005], dep[100005], f[100005]; 
void dfs1(int x, int fa) {
    root[x] = update(root[fa], 1, m, a[x]);
    f[x] = fa; dep[x] = dep[fa] + 1; siz[x] = 1; 
    for (int y : G[x]) if (y != fa) {
        dfs1(y, x); siz[x] += siz[y];
        if (siz[y] > siz[son[x]]) son[x] = y; 
    }
}
void dfs2(int x, int topf) {
    dfn[x] = ++num; top[x] = topf;
    if (!son[x]) return; dfs2(son[x], topf);
    for (int y : G[x]) if (y != f[x] && y != son[x]) dfs2(y, y);
}
int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = f[top[x]];
    }
    return dep[x] < dep[y] ? x : y; 
} 

int main(void) {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[i] = a[i];
    sort(b + 1, b + n + 1); m = unique(b + 1, b + n + 1) - (b + 1); 
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + m + 1, a[i]) - b; 
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].emplace_back(v); G[v].emplace_back(u);
    } dfs1(1, 0); dfs2(1, 1);
    int u, v, k, lca, last = 0; 
    while (q--) {
        scanf("%d%d%d", &u, &v, &k); u ^= last; lca = LCA(u, v);  
        printf("%d\n", last = b[query(root[u], root[v], root[lca], root[f[lca]], 1, m, k)]);
    }
    return 0;
}

[P4137] Rmq Problem / mex

Portal.

设 $f_{i,j}$ 代表 $j$ 在 $\le i$ 的位置中的最大出现位置，那么相当于求 $f_{i,j}<l$ 的最小 $j$ ，主席树二分或离线扫描。

查看代码

#include <bits/stdc++.h>
using namespace std; 
const int N = 200003; 

int n, m; 
struct Node {
	int ls, rs; 
	int dat; 
} T[40 * 200005]; 
int rt[200005], tot; 

void update(int &o, int pre, int l, int r, int x, int v) {
	T[o = ++tot] = T[pre]; 
	if (l == r) return T[o].dat = v, void(); 
	int mid = l + r >> 1; 
	if (x <= mid) update(T[o].ls, T[pre].ls, l, mid, x, v); 
	else update(T[o].rs, T[pre].rs, mid + 1, r, x, v); 
	T[o].dat = min(T[T[o].ls].dat, T[T[o].rs].dat); 
}
int query(int o, int l, int r, int v) {
	if (l == r) return l; 
	int mid = l + r >> 1; 
	if (T[T[o].ls].dat >= v) return query(T[o].rs, mid + 1, r, v); 
	return query(T[o].ls, l, mid, v); 
}

int main(void) {
	scanf("%d%d", &n, &m);
	for (int i = 1, x; i <= n; ++i) scanf("%d", &x), update(rt[i], rt[i - 1], 1, N, ++x, i); 
	while (m--) {
		int l, r; scanf("%d%d", &l, &r); 
		printf("%d\n", query(rt[r], 1, N, l) - 1); 
	}
	return 0; 
}

[CF1771F] Hossam and Range Minimum Query

Portal.

可持久化降掉序列维，给每一个数随机一个权值，权值线段树维护随机权值的异或和，这样可以直接判断值域内是否有出现次数为奇数的数。

查看代码

#include <bits/stdc++.h>
using namespace std; 

int n, m; 
int a[200005], b[200005]; 
map<int, int> mp;
mt19937 Rand(time(0)); 
struct Node {
	int ls, rs, dat; 
} T[200005 * 45];
int rt[200005], tot; 
int update(int pre, int l, int r, int x, int k) {
	int o = ++tot; T[o] = T[pre]; T[o].dat ^= k; 
	if (l == r) return o; int mid = l + r >> 1; 
	if (x <= mid) T[o].ls = update(T[pre].ls, l, mid, x, k); 
	else T[o].rs = update(T[pre].rs, mid + 1, r, x, k); 
	return o; 
}
int query(int p, int q, int l, int r) {
	if (l == r) return T[p].dat ^ T[q].dat ? l : 0; 
	int mid = l + r >> 1; 
	if (T[T[p].ls].dat ^ T[T[q].ls].dat) return query(T[p].ls, T[q].ls, l, mid); 
	return query(T[p].rs, T[q].rs, mid + 1, r);  
}

int main(void) {
	scanf("%d", &n); 
	for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[i] = a[i]; 
	sort(b + 1, b + n + 1); int nn = unique(b + 1, b + n + 1) - (b + 1); 
	for (int i = 1; i <= n; ++i) {
		a[i] = lower_bound(b + 1, b + nn + 1, a[i]) - b; 
		if (!mp.count(a[i])) mp[a[i]] = Rand(); 
		rt[i] = update(rt[i - 1], 1, nn, a[i], mp[a[i]]); 
	} scanf("%d", &m); 
	for (int last = 0; m--; ) {
		int l, r; scanf("%d%d", &l, &r); l ^= last, r ^= last;
		printf("%d\n", last = b[query(rt[l - 1], rt[r], 1, nn)]); 
	}
	return 0; 
}

[TJOI2018] 异或

Portal.

针对 DFS 序和树上前缀和建立两棵可持久化 01 Trie，不同询问在不同 Trie 上查询。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, q, a[100005]; 
vector<int> G[100005];
int rt1[100005], rt2[100005], tot, val[6200005], ch[6200005][2];

void insert(int x, int pre, int v) {
    for (int i = 29; i >= 0; --i) {
        val[x] = val[pre] + 1; int c = 1 << i & v ? 1 : 0; 
        ch[x][!c] = ch[pre][!c];
        if (!ch[x][c]) ch[x][c] = ++tot; 
        x = ch[x][c]; pre = ch[pre][c];
    }
    val[x] = val[pre] + 1; 
}
int query(int x, int y, int v) {
    int res = 0;
    for (int i = 29; i >= 0; --i) {
        int c = 1 << i & v ? 1 : 0; 
        if (val[ch[x][!c]] - val[ch[y][!c]]) res |= 1 << i, x = ch[x][!c], y = ch[y][!c];
        else x = ch[x][c], y = ch[y][c];
    }
    return res;
}

int dep[100005], f[100005], siz[100005]; 
int top[100005], son[100005], dfn[100005], num;

void dfs1(int x, int fa) {
    dep[x] = dep[f[x] = fa] + 1; siz[x] = 1; 
    insert(rt2[x] = ++tot, rt2[f[x]], a[x]);
    for (int y : G[x]) if (y != fa) {
        dfs1(y, x); siz[x] += siz[y]; 
        if (siz[y] > siz[son[x]]) son[x] = y; 
    }
}
void dfs2(int x, int topf) {
    top[x] = topf; dfn[x] = ++num;
    insert(rt1[num] = ++tot, rt1[num - 1], a[x]);
    if (!son[x]) return; dfs2(son[x], topf);
    for (int y : G[x]) if (y != f[x] && y != son[x]) dfs2(y, y);
}
int LCA(int x, int y) {
    while (top[x] != top[y]) {
        if (dep[top[x]] < dep[top[y]]) swap(x, y);
        x = f[top[x]];
    }
    return dep[x] < dep[y] ? x : y; 
}

int main(void) {
    scanf("%d%d", &n, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    for (int i = 1; i < n; ++i) {
        int u, v; scanf("%d%d", &u, &v);
        G[u].emplace_back(v); G[v].emplace_back(u);
    } dfs1(1, 0); dfs2(1, 1);
    while (q--) {
        int op, x, y, z; scanf("%d%d%d", &op, &x, &y);
        if (op == 1) printf("%d\n", query(rt1[dfn[x] + siz[x] - 1], rt1[dfn[x] - 1], y));
        else {
            scanf("%d", &z); int rl = rt2[f[LCA(x, y)]];
            printf("%d\n", max(query(rt2[x], rl, z), query(rt2[y], rl, z)));
        }
    }
    return 0;
}

[THUSC2015] 异或运算

Portal.

将求第 $k$ 大转化为 $k$ 小，看一下 $n=1$ 怎么做？对 $Y$ 建立可持久化 01 Trie，然后拿着 $X[1]$ 开始从高到低位开始贪心。答案的这一二进制位能取到 $0$ 的个数如果小于 $k$ ，那么这一位就需要取 $1$ ，然后令 $k$ 减去这个个数；否则这一位取 $0$ 。

发现 $n,q$ 都不是很大，因此对于 $n>1$ 直接暴力扫一遍，把总和加起来跟 $k$ 比即可。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, m, q; 
int a[1005], b[300005];
int root[300005], ch[10000005][2], tot, val[10000005]; 

void insert(int x, int pre, int v) {
    for (int i = 30; i >= 0; --i) {
        int c = v >> i & 1; ch[x][!c] = ch[pre][!c];
        if (!ch[x][c]) ch[x][c] = ++tot; 
        x = ch[x][c], pre = ch[pre][c]; 
        val[x] = val[pre] + 1; 
    }
}

int x[1005], y[1005]; 
int query(int u, int d, int l, int r, int k) {
    int ans = 0;
    for (int i = u; i <= d; ++i) x[i] = root[l - 1], y[i] = root[r];
    for (int i = 30; i >= 0; --i) {
        int cnt = 0; 
        for (int j = u; j <= d; ++j) {
            int c = a[j] >> i & 1; 
            cnt += val[ch[y[j]][c]] - val[ch[x[j]][c]];
        }
        int nxt = k <= cnt ? 0 : 1; 
        if (nxt) k -= cnt, ans |= 1 << i; 
        for (int j = u; j <= d; ++j) {
            int c = (a[j] >> i & 1) ^ nxt; 
            x[j] = ch[x[j]][c], y[j] = ch[y[j]][c];
        }
    }
    return ans; 
}

int main(void) {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i); 
    for (int i = 1; i <= m; ++i) {
        scanf("%d", b + i); root[i] = ++tot; 
        insert(root[i], root[i - 1], b[i]);
    }
    scanf("%d", &q); while (q--) {
        int u, d, l, r, k; scanf("%d%d%d%d%d", &u, &d, &l, &r, &k);
        printf("%d\n", query(u, d, l, r, (d - u + 1) * (r - l + 1) - k + 1));
    }
    return 0;
}

[CF1665E] MinimizOR

Portal.

如何处理或的最小值呢？如果出现了两个以上的 $0$ ，那么这一位显然填 $0$ ；如果没有 $0$ 出现，则填 $1$ ；有一个 $0$ 呢？找到这个 $0$ 的位置，让它自己往 $0$ 走，同时搞两个儿子就好了。只会增加 $\log$ 次节点，时间复杂度为 $O(n\log^2 V)$ 。

查看代码

#include <bits/stdc++.h>
using namespace std; 

int n, m; 
int a[100005], rt[100005]; 
int ch[10000005][2], val[10000005], tot; 

void insert(int x, int pre, int v) {
    for (int i = 29; i >= 0; --i) {
        int c = v >> i & 1; ch[x][!c] = ch[pre][!c]; 
        ch[x][c] = ++tot; x = ch[x][c]; pre = ch[pre][c]; 
        val[x] = val[pre] + 1; 
    }
}

int query(vector<pair<int, int>> v, int dep) {
    if (dep == -1) return 0;
    int sum = 0; pair<int, int> p(-1, -1);  
    for (auto& [x, y] : v) {
        sum += val[ch[y][0]] - val[ch[x][0]]; 
        if (val[ch[y][0]] - val[ch[x][0]] > 0) p = make_pair(x, y); 
    }
    if (sum >= 2) {
        for (auto& [x, y] : v) x = ch[x][0], y = ch[y][0];
        return query(v, dep - 1); 
    }
    for (auto& [x, y] : v) x = ch[x][1], y = ch[y][1];
    if (sum == 1) v.emplace_back(ch[p.first][0], ch[p.second][0]); 
    return query(v, dep - 1) + (1 << dep); 
}

int main(void) {
    int T; scanf("%d", &T); 
    while (T--) {
        scanf("%d", &n); 
        for (int i = 1; i <= n; ++i) scanf("%d", a + i), insert(rt[i] = ++tot, rt[i - 1], a[i]); 
        for (scanf("%d", &m); m--; ) {
            int l, r; scanf("%d%d", &l, &r); 
            vector<pair<int, int>> v; v.emplace_back(rt[l - 1], rt[r]); 
            printf("%d\n", query(v, 29)); 
        }
        for (int i = 1; i <= tot; ++i) ch[i][0] = ch[i][1] = val[i] = 0; tot = 0; 
    }
    return 0; 
}

[Luogu P7834] Peaks

Portal.

经过权值 $\le x$ 的边能够到达的点是 Kruskal 重构树上某个子树内的点，而子树上的 $k$ 大点可以通过 DFS 序转换到序列上使用主席树处理。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, A, nn, m, q, a[200005], b[100005]; 
struct edge {
    int u, v, d; 
    bool operator < (const edge &a) const {
        return d < a.d;
    }
} e[500005];
struct UnionFind {
    int fa[200005];
    void init(void) {
        for (int i = 1; i <= n * 2; ++i) fa[i] = i; 
    }
    int find(int x) {
        if (fa[x] == x) return x;
        return fa[x] = find(fa[x]);
    }
} US;

int val[200005]; 
vector<int> G[200005];
void addedge(int x, int y) {
    G[x].emplace_back(y); G[y].emplace_back(x);
}

int f[21][200005], dfn[200005], siz[200005], num, idx[200005];
void dfs(int x, int fa) {
    f[0][x] = fa; siz[x] = 1; idx[dfn[x] = ++num] = x; 
    for (int i = 1; i <= 20; ++i) f[i][x] = f[i - 1][f[i - 1][x]];
    for (int y : G[x]) if (y != fa) dfs(y, x), siz[x] += siz[y];
}

void Kruskal(void) {
    sort(e + 1, e + m + 1); US.init(); A = n; 
    for (int i = 1; i <= m; ++i) {
        int u = e[i].u, v = e[i].v, w = e[i].d; 
        int x = US.find(e[i].u), y = US.find(e[i].v);
        if (x == y) continue; val[++A] = w; 
        US.fa[x] = US.fa[y] = A; 
        addedge(x, A); addedge(y, A);
    }
    for (int i = 1; i <= A; ++i) if (US.fa[i] == i) dfs(i, 0);
}

struct Node {
    int lc, rc;
    int val; 
} T[2200005];
int tot, root[200005]; 
int build(int l, int r) {
    int o = ++tot; if (l == r) return o;
    int mid = l + r >> 1;
    T[o].lc = build(l, mid); T[o].rc = build(mid + 1, r);
    return o;
}
int update(int pre, int l, int r, int x) {
    if (!x) return pre; 
    int o = ++tot; T[o] = T[pre]; T[o].val += 1;
    if (l == r) return o;
    int mid = l + r >> 1; 
    if (x <= mid) T[o].lc = update(T[pre].lc, l, mid, x);
    else T[o].rc = update(T[pre].rc, mid + 1, r, x);
    return o;
}
int query(int x, int y, int l, int r, int k) {
    if (l == r) return l;
    if (T[y].val - T[x].val < k) return 0;
    int mid = l + r >> 1, res = T[T[y].rc].val - T[T[x].rc].val; 
    if (res >= k) return query(T[x].rc, T[y].rc, mid + 1, r, k);
    return query(T[x].lc, T[y].lc, l, mid, k - res);
}

int main(void) {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), b[i] = a[i];
    sort(b + 1, b + n + 1); nn = unique(b + 1, b + n + 1) - (b + 1);
    for (int i = 1; i <= n; ++i) a[i] = lower_bound(b + 1, b + nn + 1, a[i]) - b;
    for (int i = 1; i <= m; ++i) scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].d);
    Kruskal();
    root[0] = build(1, nn);
    for (int i = 1; i <= A; ++i) root[i] = update(root[i - 1], 1, nn, a[idx[i]]);
    for (int last = 0; q--; ) {
        int u, x, k; scanf("%d%d%d", &u, &x, &k);
        u = (u ^ last) % n + 1, x = x ^ last, k = (k ^ last) % n + 1; 
        for (int i = 20; i >= 0; --i) if (f[i][u] && val[f[i][u]] <= x) u = f[i][u];
        printf("%d\n", (last = b[query(root[dfn[u] - 1], root[dfn[u] + siz[u] - 1], 1, nn, k)]) ? last : -1);
    }
    return 0;
}

[CF1777F] Comfortably Numb

Portal.

找出序列中权值最大的位置，答案区间要么在它左侧或右侧，要么跨越区间。合并时采用启发式合并的思想，枚举小区间中的下标，就是要在大区间中找一个异或值最大的，可以使用可持久化 01 Trie 解决。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n; 
int a[200005], f[21][200005], lg[200005], s[200005];
int ch[6400005][2], tot, root[200005], val[6400005];

int qmax(int l, int r) {
    int k = lg[r - l + 1];
    if (a[f[k][l]] > a[f[k][r - (1 << k) + 1]]) return f[k][l];
    return f[k][r - (1 << k) + 1];
}

void insert(int x, int pre, int v) {
    for (int i = 29; i >= 0; --i) {
        int c = v >> i & 1; ch[x][!c] = ch[pre][!c];
        if (!ch[x][c]) ch[x][c] = ++tot; 
        x = ch[x][c], pre = ch[pre][c];
        val[x] = val[pre] + 1;     
    }
    
}
int query(int x, int y, int v) {
    int res = 0; 
    for (int i = 29; i >= 0; --i) {
        int c = v >> i & 1; 
        if (val[ch[y][!c]] - val[ch[x][!c]]) x = ch[x][!c], y = ch[y][!c], res |= 1 << i; 
        else x = ch[x][c], y = ch[y][c];
    }
    return res; 
}

int merge(int l, int r) {
    if (l >= r) return 0; 
    int mid = qmax(l, r), ans = max(merge(l, mid - 1), merge(mid + 1, r));
    if (r - mid < mid - l) { // 将右半段合并到左半段
        for (int i = mid; i <= r; ++i) // 枚举右端点
            ans = max(ans, query(l > 1 ? root[l - 2] : 0, root[mid - 1], a[mid] ^ s[i]));
    } else {
        for (int i = l; i <= mid; ++i) // 枚举左端点
            ans = max(ans, query(root[mid - 1], root[r], a[mid] ^ s[i - 1]));
    }
    return ans; 
}

void solve(void) {
    for (int i = 0; i <= tot; ++i) ch[i][0] = ch[i][1] = val[i] = 0; 
    cin >> n; tot = 0; 
    for (int i = 1; i <= n; ++i) cin >> a[i], f[0][i] = i, s[i] = s[i - 1] ^ a[i];
    for (int i = 0; i <= n; ++i) {
        root[i] = ++tot;
        insert(root[i], i == 0 ? 0 : root[i - 1], s[i]);
    }
    for (int j = 1; 1 << j <= n; ++j) for (int i = 1; i + (1 << j) - 1 <= n; ++i) 
        if (a[f[j - 1][i]] > a[f[j - 1][i + (1 << j - 1)]]) 
            f[j][i] = f[j - 1][i]; 
        else f[j][i] = f[j - 1][i + (1 << j - 1)];
    cout << merge(1, n) << "\n";
}

int main(void) {
    for (int i = 2; i <= 200000; ++i) lg[i] = lg[i >> 1] + 1; 
    ios::sync_with_stdio(false); int T; cin >> T; while (T--) solve();
    return 0;
}

[Luogu P5586] 序列

Portal.

这是可持久化平衡树最经典的应用：区间复制。因为可持久化平衡树在合并时会复制要合并的节点，因此可以支持区间复制。另外由于可持久化平衡树空间开销过大，需要定时重构整棵平衡树。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007; 

mt19937 Rand(time(0)); 
struct Node {
    int setv, addv; bool rev; 
    int val, sum, ls, rs, siz; 
} T[8200005];
int root, tot, a[300005], num; 
inline void pushup(int p) { 
    T[p].sum = (0ll + T[T[p].ls].sum + T[T[p].rs].sum + T[p].val) % MOD; 
    T[p].siz = T[T[p].ls].siz + T[T[p].rs].siz + 1; 
}
inline int newNode(int x) {
    int p = ++tot; 
    T[p].setv = -1; T[p].ls = T[p].rs = T[p].addv = T[p].rev = 0; 
    T[p].val = T[p].sum = x; T[p].siz = 1; 
    return p; 
}
inline int copyNode(int x) {
    T[++tot] = T[x]; 
    return tot; 
}
inline void rever(int p) {
    swap(T[p].ls, T[p].rs);
    T[p].rev ^= 1; 
}
inline void cover(int p, int k) {
    T[p].addv = T[p].rev = 0; 
    T[p].setv = T[p].val = k; 
    T[p].sum = 1ll * T[p].siz * k % MOD; 
}
inline void add(int p, int k) {
    T[p].addv = (T[p].addv + k) % MOD; 
    T[p].val = (T[p].val + k) % MOD; 
    T[p].sum = (T[p].sum + 1ll * k * T[p].siz) % MOD; 
}
inline void pushdown(int p) {
    if (!p) return; 
    if (T[p].ls) T[p].ls = copyNode(T[p].ls); 
    if (T[p].rs) T[p].rs = copyNode(T[p].rs); 
    if (T[p].setv != -1) {
        if (T[p].ls) cover(T[p].ls, T[p].setv);
        if (T[p].rs) cover(T[p].rs, T[p].setv);
        T[p].setv = -1; 
    }
    if (T[p].rev) {
        if (T[p].ls) rever(T[p].ls); 
        if (T[p].rs) rever(T[p].rs);
        T[p].rev = 0; 
    }
    if (T[p].addv) {
        if (T[p].ls) add(T[p].ls, T[p].addv); 
        if (T[p].rs) add(T[p].rs, T[p].addv);
        T[p].addv = 0; 
    }
}
void split(int p, int S, int &x, int &y) {
    if (!p) return x = y = 0, void();
    p = copyNode(p); pushdown(p);
    if (T[T[p].ls].siz + 1 <= S) {
        x = p; 
        split(T[p].rs, S - T[T[p].ls].siz - 1, T[p].rs, y);
    } else {
        y = p; 
        split(T[p].ls, S, x, T[p].ls);
    } pushup(p);
}
int merge(int x, int y) {
    if (x == 0 || y == 0) return x + y; 
    if (T[x].siz > T[y].siz) {
        x = copyNode(x); pushdown(x); T[x].rs = merge(T[x].rs, y);
        pushup(x); return x; 
    } else {
        y = copyNode(y); pushdown(y); T[y].ls = merge(x, T[y].ls); 
        pushup(y); return y; 
    }
}

int build(int l, int r) {
    if (l > r) return 0; 
    int mid = l + r >> 1; int p = newNode(a[mid]); 
    T[p].ls = build(l, mid - 1); T[p].rs = build(mid + 1, r);
    pushup(p); return p; 
}
void dfs(int p) {
    pushdown(p);
    if (T[p].ls) dfs(T[p].ls);
    a[++num] = T[p].val;
    if (T[p].rs) dfs(T[p].rs); 
}

int main(void) {
    int n, m; scanf("%d%d", &n, &m);   
    for (int i = 1; i <= n; ++i) scanf("%d", a + i);
    root = build(1, n);
    int v, w, x, y, z, last = 0; 
    while (m--) {
        int op; scanf("%d", &op);
        if (op == 1) {
            int l, r; scanf("%d%d", &l, &r); l ^= last, r ^= last; 
            split(root, l - 1, x, y);
            split(y, r - l + 1, y, z);
            printf("%d\n", last = T[y].sum);
            root = merge(x, merge(y, z));
        } else if (op == 2) {
            int l, r, k; scanf("%d%d%d", &l, &r, &k); l ^= last, r ^= last; k ^= last; 
            split(root, l - 1, x, y);
            split(y, r - l + 1, y, z);
            cover(y, k);
            root = merge(x, merge(y, z));
        } else if (op == 3) {
            int l, r, k; scanf("%d%d%d", &l, &r, &k); l ^= last, r ^= last; k ^= last;
            split(root, l - 1, x, y);
            split(y, r - l + 1, y, z);
            add(y, k);
            root = merge(x, merge(y, z));
        } else if (op == 4) {
            int l1, r1, l2, r2, flag = 1; scanf("%d%d%d%d", &l1, &r1, &l2, &r2); l1 ^= last; r1 ^= last; l2 ^= last; r2 ^= last; 
            if (r1 > r2) swap(l1, l2), swap(r1, r2), flag = 0;
            split(root, r2, y, z); split(y, l2 - 1, x, y);
            split(x, r1, w, x); split(w, l1 - 1, v, w);
            if (flag) root = merge(v, merge(w, merge(x, merge(w, z))));
            else root = merge(v, merge(y, merge(x, merge(y, z))));
        } else if (op == 5) {
            int l1, r1, l2, r2; scanf("%d%d%d%d", &l1, &r1, &l2, &r2); l1 ^= last; r1 ^= last; l2 ^= last; r2 ^= last; 
            if (r1 > r2) swap(l1, l2), swap(r1, r2);
            split(root, r2, y, z); split(y, l2 - 1, x, y);
            split(x, r1, w, x); split(w, l1 - 1, v, w);
            root = merge(v, merge(y, merge(x, merge(w, z))));
        } else {
            int l, r; scanf("%d%d", &l, &r); l ^= last, r ^= last;
            split(root, l - 1, x, y);
            split(y, r - l + 1, y, z);
            rever(y); 
            root = merge(x, merge(y, z));
        }
        if (tot > 7000000) {
            num = 0; dfs(root); tot = 0; 
            root = build(1, n);
        }
    }
    num = 0; dfs(root); 
    for (int i = 1; i <= n; ++i) printf("%d ", a[i]); 
    putchar('\n'); return 0;
}

【模板】可持久化平衡树

Portal.

就是普通的可持久化 FHQ-Treap。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int N = 500005; 
typedef long long i64; 

mt19937 Rand(time(0));
struct Node {
    int siz, rnd;
    int ls, rs;
    int val; 
} T[N * 105]; int tot, root[N];
int newNode(i64 v) {
    ++tot; T[tot].siz = 1; T[tot].rnd = Rand(); T[tot].val = v; 
    return tot; 
}
int copyNode(int x) {
    T[++tot] = T[x];
    return tot; 
}
void pushup(int p) {
    T[p].siz = T[T[p].ls].siz + T[T[p].rs].siz + 1; 
}
void split(int p, int k, int &x, int &y) {
    if (!p) return x = y = 0, void();
    int o = copyNode(p);
    if (T[o].val <= k) {
        x = o;
        split(T[o].rs, k, T[o].rs, y);
    }
    else {
        y = o;
        split(T[o].ls, k, x, T[o].ls);
    } pushup(o);
}
int merge(int x, int y) {
    if (x == 0 || y == 0) return x + y; 
    if (T[x].rnd > T[y].rnd) {
        x = copyNode(x); T[x].rs = merge(T[x].rs, y); pushup(x);
        return x;
    } else {
        y = copyNode(y); T[y].ls = merge(x, T[y].ls); pushup(y);
        return y; 
    }
}
int kth(int p, int k) {
    while (p) {
        if (T[T[p].ls].siz + 1 == k) break;
        else if (T[T[p].ls].siz + 1 > k) p = T[p].ls;
        else {
            k -= T[T[p].ls].siz + 1;
            p = T[p].rs;
        }
    }
    return T[p].val; 
}

int main(void) {
    int q; scanf("%d", &q); 
    for (int i = 1; i <= q; ++i) {
        int op, v, x, a, b, c; scanf("%d%d%d", &v, &op, &x); root[i] = root[v]; 
        if (op == 1) {
            split(root[i], x, a, b);
            root[i] = merge(a, merge(newNode(x), b)); 
        } else if (op == 2) {
            split(root[i], x - 1, a, b);
            split(b, x, b, c); b = merge(T[b].ls, T[b].rs);
            root[i] = merge(a, merge(b, c));
        } else if (op == 3) {
            split(root[i], x - 1, a, b);
            printf("%d\n", T[a].siz + 1); 
            root[i] = merge(a, b);
        } else if (op == 4) printf("%d\n", kth(root[i], x)); 
        else if (op == 5) {
            split(root[i], x - 1, a, b);
            if (!a) printf("-2147483647\n");
            else {
                int p = a; 
                while (T[p].rs) p = T[p].rs; 
                printf("%d\n", T[p].val);
            }
            root[i] = merge(a, b);
        } else {
            split(root[i], x, a, b);
            if (!b) printf("2147483647\n");
            else {
                int p = b; 
                while (T[p].ls) p = T[p].ls; 
                printf("%d\n", T[p].val);
            }
            root[i] = merge(a, b);
        }
    }
    return 0;
}

[国家集训队] middle

Portal.

中位数二分答案，限制采用 GSS5 的处理方法（将限制区间拆分成三个区间），主席树维护按权值排序的版本信息即可。

查看代码

#include <bits/stdc++.h>
using namespace std;

int n, Q, q[4]; 
int a[20005], id[20005]; 

struct Value {
    int lmax, rmax, sum; 
    friend Value operator+ (const Value &a, const Value &b) {
        Value c; 
        c.lmax = max(a.lmax, a.sum + b.lmax); 
        c.rmax = max(b.rmax, a.rmax + b.sum); 
        c.sum = a.sum + b.sum; 
        return c; 
    }
}; 
struct Node {
    int ls, rs; 
    Value dat; 
} T[400005]; 
int rt[20005], tot; 
int build(int l, int r) {
    int o = ++tot; T[o].dat = {r - l + 1, r - l + 1, r - l + 1}; 
    if (l == r) return o; int mid = l + r >> 1; 
    T[o].ls = build(l, mid); T[o].rs = build(mid + 1, r); 
    return o; 
}
int update(int pre, int l, int r, int x) {
    int o = ++tot; T[o] = T[pre]; 
    if (l == r) return T[o].dat = {-1, -1, -1}, o; 
    int mid = l + r >> 1; 
    if (x <= mid) T[o].ls = update(T[pre].ls, l, mid, x); 
    else T[o].rs = update(T[pre].rs, mid + 1, r, x); 
    T[o].dat = T[T[o].ls].dat + T[T[o].rs].dat; 
    return o; 
}
Value query(int o, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[o].dat; 
    int mid = l + r >> 1; 
    if (y <= mid) return query(T[o].ls, l, mid, x, y); 
    if (mid < x) return query(T[o].rs, mid + 1, r, x, y); 
    return query(T[o].ls, l, mid, x, y) + query(T[o].rs, mid + 1, r, x, y); 
}

bool check(int x) {
    int ans = 0; 
    ans += query(rt[x], 1, n, q[0], q[1]).rmax; 
    if (q[1] + 1 <= q[2] - 1) ans += query(rt[x], 1, n, q[1] + 1, q[2] - 1).sum;
    ans += query(rt[x], 1, n, q[2], q[3]).lmax; 
    return ans >= 0; 
}

int main(void) {
    scanf("%d", &n); 
    for (int i = 1; i <= n; ++i) scanf("%d", a + i), id[i] = i; 
    sort(id + 1, id + n + 1, [&](int x, int y) { return a[x] < a[y]; });
    rt[1] = build(1, n); 
    for (int i = 2; i <= n; ++i) rt[i] = update(rt[i - 1], 1, n, id[i - 1]); 
    scanf("%d", &Q); 
    for (int last = 0; Q--; ) {
        for (int i = 0; i < 4; ++i) scanf("%d", q + i), q[i] = (q[i] + last) % n + 1; 
        sort(q, q + 4); 
        int L = 0, R = n + 1; 
        while (L + 1 != R) {
            int mid = L + R >> 1; 
            if (check(mid)) L = mid; 
            else R = mid; 
        }
        printf("%d\n", last = a[id[L]]); 
    }
    return 0;
}

[SCOI2016] 美味

Portal.

从高到低位贪心，利用主席树判断数是否存在。

查看代码

#include <bits/stdc++.h>
using namespace std;
const int N = 100000; 

struct Node {
    int ls, rs, dat; 
} T[10000005]; 
int rt[200005], tot; 

int n, m; 
int a[200005]; 

int build(int l, int r) {
    int o = ++tot; if (l == r) return o; 
    int mid = l + r >> 1; T[o].ls = build(l, mid); T[o].rs = build(mid + 1, r); 
    return o; 
}
int update(int pre, int l, int r, int x) {
    int o = ++tot; T[o] = T[pre]; ++T[o].dat; 
    if (l == r) return o; 
    int mid = l + r >> 1; 
    if (x <= mid) T[o].ls = update(T[pre].ls, l, mid, x); 
    else T[o].rs = update(T[pre].rs, mid + 1, r, x); 
    return o; 
}
int query(int p, int q, int l, int r, int x, int y) {
    if (x <= l && r <= y) return T[q].dat - T[p].dat; 
    int mid = l + r >> 1, res = 0; 
    if (x <= mid) res += query(T[p].ls, T[q].ls, l, mid, x, y); 
    if (mid < y) res += query(T[p].rs, T[q].rs, mid + 1, r, x, y); 
    return res; 
}
bool find(int p, int q, int l, int r) {
    l = max(l, 0); r = min(r, N); 
    if (l > r) return 0; 
    return query(rt[p], rt[q], 1, N, l, r); 
}

int main(void) {
    scanf("%d%d", &n, &m); 
    for (int i = 1; i <= n; ++i) scanf("%d", a + i); 
    rt[0] = build(1, N); 
    for (int i = 1; i <= n; ++i) rt[i] = update(rt[i - 1], 1, N, a[i]); 
    while (m--) {
        int b, x, l, r, ans = 0; scanf("%d%d%d%d", &b, &x, &l, &r); 
        for (int i = 17; i >= 0; --i) {
            int now = ans + (((b >> i & 1) ^ 1) << i); 
            if (find(l - 1, r, now - x, now + (1 << i) - 1 - x)) ans = now; 
            else ans += ((b >> i & 1) << i); 
        }
        printf("%d\n", ans ^ b); 
    }
    return 0;
}

嵌套数据结构

应用不是很多（因为通常没有要求这么复杂的玩意），但是出出来都挺吓人。

综合应用

这里的题目难度会有所上升。