算法简介：彩色歌谣

可持久化，字面意思就是持久，但是什么东西可以叫做持久呢？这一篇文章主要讲的是可持久化数据结构，也就是说，所谓可持久化其实是对于数据结构中所存储的数据的持久化，说直白一点，就是历史版本。你可以在任何时候查询任意时刻你维护的的任何数据的状态，这就是所谓的可持久化。

但是你看这里的标签，一排排打了一堆可持久化数据结构，似乎很繁杂，但是说呢其实这也没什么。这里的可持久化数据结构都是基于这个可持久化线段树来建立的，所以这篇文章就会从可持久化线段树开始，一步一步讲解。

友情链接：

线段树 | 祝馀宫
【算法介绍】线段树合并 | 祝馀宫

算法基础：元气迸发

那么首先我们知道，可持久化线段树也就是我们常说的主席树。它的一大作用是查询历史版本，但是在引入这个概念之前，我要先讲一个更加好理解的内容，先看题罢。

给出一个长度为 $n$ 的数组 $a$，一共有 $m$ 次查询，每次查询询问一个区间 $[l,r]$ 中的第 $k$ 小数字。

模型构建

既然已经透露过线段树的风声，那我们肯定是也知道这道题要用线段树了。但是这个线段树该怎么建呢？总不能对于每一个区间都建立一个线段树吧，这显然是不可能的，单是建立的时间都不够，更别想着要后面的查询了。

那么问题就是，如何去做到这样的一个优化来得出这道题的答案呢？我们来想想，一个熟悉的问题，求整体区间第 $k$ 小的数据。整体区间第 $k$ 小？这个似乎不难，我们直接建一个权值线段树，来统计每一个数字的出现次数，然后合并的节点也是统计这一个值域内有多少个数字。

这样的话我们就只需要顺着左右子树的大小查询下去就可以了。这个函数应该不难得到，如果不理解的话，止步于此，可以自己想想或看看上面的友情链接。

那么我们可以想想，我们目前有了全局第 $k$ 小，那么前缀第 $k$ 小可以算么？似乎没什么思路，但是我们可以想想所谓前缀，从字符串的角度来讲，前缀应该是可递推的。意思就是如果我们用 $pre[i]$ 表示结尾为 $i$ 的前缀的话，就可以用 $pre[i]=pre[i-1]+s[i]$ 来表示前缀递推的过程。

而从局部的角度来看，我们已经开放的前缀，就是一个全局，每增加一个数字，相当于扩大了一个全局使其变成新的全局。也就是说我们可以通过建立 $n$ 个线段树来实现我们所谓的前缀第 $k$ 小。如果我们有了前缀的话，那么区间不就简单了。前缀和算法，大家都知道吧，其实我们查询的时候也是一样的，比如说我们要求区间 $[l,r]$ 中，值域 $[1,mid]$ 有多少个数字，那么就可以用前缀 $[1,r]$ 这个值域中数字的数量减去前缀 $[1,l-1]$ 相同值域中数字的数量。那么如果要对应到代码里，我们就是同时在两个线段树上寻找，同样是前缀 $k$ 小，我们可以这样的得到代码：

调用的时候应该也不难想，这里就是两边同步走，不然的话不能保证值域相同，如果值域不相同，相减也没有意义了。其次是这里的两个线段树的根，线段树 $u$ 应该对应的是前缀 $[1,l-1]$，线段树 $v$ 应该对应的是前缀 $[1,r]$，也就是说如果我们对于每一个前缀建立线段树的话，调用函数应该向下面这样：

至此这个问题似乎就解决了，但是有一个我们都未曾注意的点。

空间优化

我们可以分析一下这样做的复杂度，先说时间复杂度，显而易见的两边寻找的时间就是线段树的深度，也就是单次查询 $O(\log n)$ 的优秀复杂度，但是转眼看一眼空间，$O(n^2\log n)$ ？开玩笑，完全开不下好不好，这该怎么办呢？我们现在的目标就是压下空间。

观察一下这样的结构，发现一个大问题，每次我们的前缀递推过来，只会增加一个数字，也就是说，两次的线段树差距，微乎其微，但是我们依然重新建立了一个线段树来保存新的前缀。也就是说这样做会有大大的浪费，具体是浪费多少呢？我们发现，每次修改一个叶子，跟着改变的其实是这个点到根的路径上所有节点，也就是 $\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
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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

struct Node {
    int sum;
    Node() {}
    inline Node operator + (const Node & b) const {
        Node ans; ans.sum = sum + b.sum; return ans;
    }
};
template<const int N > 
class PerSegTree {
public :
    Node node[N]; int cntn;
    int lc[N], rc[N];
    int rt[N];

    inline int& operator [] (int x) {
        return rt[x];
    }

    int Build(int L, int R) {
        int root = ++cntn;
        if(L == R) return root;
        int mid = L + R >> 1;
        lc[root] = Build(L, mid);
        rc[root] = Build(mid + 1, R);
        return root;
    }

    int Update(int p, int L, int R, int val) {
        int dir = ++cntn;
        lc[dir] = lc[p], rc[dir] = rc[p];
        node[dir].sum = node[p].sum + 1;
        if(L == R) return dir;
        int mid = L + R >> 1;
        if(val <= mid) 
            lc[dir] = Update(lc[dir], L, mid, val);
        else 
            rc[dir] = Update(rc[dir], mid+1,R,val);
        return dir;
    }

    int Query(int u, int v, int L, int R, int val) {
        int mid = L + R >> 1;
        int x = node[lc[v]].sum - node[lc[u]].sum;
        if(L == R) return L;
        if(val <= x) 
            return Query(lc[u], lc[v], L, mid, val);
        else 
            return Query(rc[u], rc[v], mid+1, R, val - x);
    }
};

const int N = 1e5 + 10;

int n, m;
int a[N];

int uni[N], unilen;

inline void Input() {
    read(n, m);
    for(int i = 1; i <= n; i++) {
        read(a[i]);
    }
}

PerSegTree< N << 5 >Tree;

inline int getid(int x) {
    return lower_bound(uni + 1, uni + unilen + 1, x) - uni;
}

inline void Init() {
    memcpy(uni, a, sizeof(uni));
    sort(uni + 1, uni + n + 1);
    unilen = unique(uni + 1, uni + n + 1) - uni - 1;
    Tree[0] = Tree.Build(1, unilen);
    for(int i = 1; i <= n; i++) {
        Tree[i] = Tree.Update(Tree[i - 1], 1, unilen, getid(a[i]));
    }
}

inline void Work() {
    Init();
    int l, r, k;
    while(m--) {
        read(l, r, k);
        printf("%d\n", uni[Tree.Query(Tree[l - 1], Tree[r], 1, unilen, k)]);
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}

算法拓展：明日之星

那么秉承着线段树的优良传统，这么好用的一个数据结构当然是不可能只有这一种用法的，相反的，这个被称为主席树的数据结构真的和主席一样，有着一大片一大片的应用，我先挑几个简单的来说。

可持久化下标线段树

首先就是典型的，可持久化下标线段树，也被称为可持久化数组。这个的用处非常广泛，他的作用就不再是向上面这样的处理区间问题了，他是真正意义上的存储历史版本。也就是说它存在一个时间的维度，来解决问题。

我们给一个经典的题目来开开眼罢，题目传送门 。

这个的题怎么做呢？我们发现似乎很困难啊，因为一开始的各项任务都是区间，相当于区修单查。似乎非常的困难，但是我们不难想到的是，既然已经在主席树种用到了前缀和的思想，那么用差分似乎也不过分了。也就是说，我们可以把这个时间变成一个维度，就像刚刚的前缀一样。

这时候我们套用差分的思想，对于工作时段在 $[l,r]$ 的任务来讲，我们可以认为这是一个对于时间 $l$ 的单点加操作和对于时间 $r + 1$ 的单点减操作。那么如何在同一个时间点到时候处理多条信息呢？直接开一个 vector 存储每一个时间发生的事就可以，一个常用的小技巧。

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

namespace FastIO {
    template<typename T> inline void read(T& x) {
        x = 0; int f = 1; char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x); read(x_...);
    }
}
using namespace FastIO;

const int N = 1e5 + 10, M = 1e5 + 10;

int n, m, tot, root[N];
ll ans = 1;
int a[M], b[M], num;
vector<int> be[N], ed[N];

struct Tree {
    ll sum; int cnt, l, r;
} t[N << 6];

inline void update(int &u, int l, int r, int pre, int pos, int v) {
    u = ++tot, t[u] = t[pre];
    t[u].cnt += v, t[u].sum += 1LL * v * b[pos];
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (pos <= mid) update(t[u].l, l, mid, t[pre].l, pos, v);
    else update(t[u].r, mid + 1, r, t[pre].r, pos, v);
}

inline ll query(int u, int l, int r, int k) {
    int num = t[t[u].l].cnt;
    if (l == r) return 1LL * t[u].sum / t[u].cnt * k;
    int mid = (l + r) >> 1;
    if (k <= num) return query(t[u].l, l, mid, k);
    return query(t[u].r, mid + 1, r, k - num) + t[t[u].l].sum;
}

inline void Input() {
    read(m, n);
    int x, y; 
    for (int i = 1; i <= m; i++) {
        read(x, y, a[i]);
        b[i] = a[i];
        be[x].push_back(i), ed[y + 1].push_back(i);
    }
}

inline void Init() {
    sort(b + 1, b + 1 + m);
    num = unique(b + 1, b + 1 + m) - b - 1;
    for (int i = 1; i <= n; i++) {
        root[i] = root[i - 1];
        for (int j : be[i]) {
            int pos = lower_bound(b + 1, b + 1 + num, a[j]) - b;
            update(root[i], 1, num, root[i], pos, 1);
        }
        for (int j : ed[i]) {
            int pos = lower_bound(b + 1, b + 1 + num, a[j]) - b;
            update(root[i], 1, num, root[i], pos, -1);
        }
    }
}

inline void Work() {
    Init();
    int x, A, B, C; 
    for (int i = 1; i <= n; i++) {
        read(x, A, B, C);
        int k = (1LL * A * ans + B) % C + 1;
        if (k > t[root[x]].cnt) ans = t[root[x]].sum;
        else ans = query(root[x], 1, num, k);
        printf("%lld\n", ans);
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}

带修可持久化线段树

我一般叫他可持久化树状数组 /yiw ？好吧这个名字是我乱编的……

事情是这样，题目传送门，一道貌似很简单的题……

首先不删除的逆序对还会搞嘛？就是建立一个树状数组，离散化后每一个节点操作，最后查询的时候查找小于等于这个节点数值的点的数量。这个很好说，但是这到题目是要删除节点的，似乎和树状数组扯不上关系。

但是我们想想，主席树其实借用的就是前缀和思想，树状数组其实也是也是前缀和，于是乎我么们可以建立一个树状数组，不过这个树状数组的每一个节点都是一个主席树，然后在上面操作。

具体的，我们可以先得到整体的逆序对数量，建立出主席树后，去寻找这个数字删除后他所影响的贡献，从整体减去即可。

我们在一个开始维护主席树插入元素时，我们要从 i-lowbit(i)+1 一直加到 i 这是为什么呢？树状数组的第 $i$ 个节点，维护的是区间 $(i-\operatorname{lowbit}(i),i\ ]$ 的值，所以说我们统计的也得是 i-lowbit(i)+1 ~ i 。

友情链接：

树状数组，这一篇就够了！ | 祝馀宫

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
// typedef __int128 int128;
typedef pair<int , int > pii;
typedef unsigned long long ull;

namespace FastIO 
{
    // char buf[1 << 20], *p1, *p2;
    // #define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 20, stdin), p1 == p2) ? EOF : *p1++)
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
        read(x);
        read(x_...);
        return;
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 1e5 + 10;
#define lowbit(x) (x&(-x))

namespace BIT {
    const int M = N << 5;
    int c[M];
    inline void Modify(int x, int val, int n) {
        for(int i = x; i <= n; i += lowbit(i))
            c[i] += val;
    }
    inline int PreSum(int x) {
        int ans = 0;
        for(int i = x; i > 0; i -= lowbit(i)) 
            ans += c[i];
        return ans;
    }
    inline int Query(int l, int r) {
        return PreSum(r) - PreSum(l - 1);
    }
};

namespace PerSegTree {
    const int M = N << 7;
    int cnt[M], lc[M], rc[M];
    int cntn;

    void Update(int &p, int L, int R, int val, int f) {
        if(p == 0) p = ++cntn;
        cnt[p] += f;
        if(L == R) return ;
        int mid = L + R >> 1;
        if(val <= mid) Update(lc[p], L, mid, val, f);
        else Update(rc[p], mid + 1, R, val, f);
    }

    ll Query1(int p, int L, int R, int val) {
        if(p == 0) return 0;
        if(L == R) {
            if(val < L) return cnt[p];
            return 0;
        }
        int mid = L + R >> 1;
        if(val > mid) return Query1(rc[p], mid + 1, R, val);
        return cnt[rc[p]] + Query1(lc[p], L, mid, val);
    }
    ll Query2(int p, int L, int R, int val) {
        if(p == 0) return 0;
        if(L == R) {
            if(val > L) return cnt[p];
            return 0;
        }
        int mid = L + R >> 1;
        if(val <= mid) return Query2(lc[p], L, mid, val);
        return cnt[lc[p]] + Query2(rc[p], mid + 1, R, val);
    }
};

int n, Q;
int a[N], b[N];

ll ans;

int rt[N];

inline void Input() {
    read(n, Q);
    for(int i = 1; i <= n; i++) {
        read(a[i]), b[a[i]] = i;
        ans += BIT::Query(a[i] + 1, n);
        BIT::Modify(a[i], 1, n);
        for(int j = i-lowbit(i)+1; j <= i; j++)
            PerSegTree::Update(rt[i], 1, n, a[j], 1);
    }
}

inline ll QueryBigger(int l, int r, int val) {
    if(l > r) return 0;
    l--; ll ans = 0;
    for(int i = r; i > 0; i -= lowbit(i)) 
        ans += PerSegTree::Query1(rt[i], 1, n, val);
    for(int i = l; i > 0; i -= lowbit(i))
        ans -= PerSegTree::Query1(rt[i], 1, n, val);
    return ans;
}

inline ll QueryLitter(int l, int r, int val) {
    if(l > r) return 0;
    l--; ll ans = 0;
    for(int i = r; i > 0; i -= lowbit(i)) 
        ans += PerSegTree::Query2(rt[i], 1, n, val);
    for(int i = l; i > 0; i -= lowbit(i))
        ans -= PerSegTree::Query2(rt[i], 1, n, val);
    return ans;
}

inline ll CountBackW(int del, int pos) {
    ll Bigger = QueryBigger(1, b[del]-1, del);
    ll Litter = QueryLitter(b[del]+1, n, del);
    return Bigger + Litter;
}

inline void Delete(int del, int pos) {
    for(int i = pos; i <= n; i += lowbit(i)) {
        PerSegTree::Update(rt[i], 1, n, del, -1);
    }
}

inline void Work() {
    int del;
    while(Q--) {
        printf("%lld\n", ans);
        read(del);
        ans -= CountBackW(del, b[del]);
        Delete(del, b[del]);
    }
}

int main() {
    int T = 1;
    while(T--) {
        Input();
        Work();
    }
    return 0;
}

可持久化树维护

这个其实也没什么好讲了，有了上面几道题做铺垫，这个其实并不难做。老样子抛一道例题上来，题目传送门 。

这是一个很简单的问题，几乎和我们一开始的问题如出一辙，为什么这么说呢？这道题也是求第 $k$ 小罢，但是他是树上的，可是树上的会影响我们什么吗？学过树上查询的应该都知道，树上的数据应该是端点相加减去两倍 LCA ，这时候我们维护的数据应该是根节点到当前点的所有数字。

不过不同的是，我们这里计算的是点上的数据，也就是说直接的减去两倍 LCA 就会使得 LCA 这个点被抹除，但是只减去一个又会使得 LCA 这个点被计算两边，非常的不方便。于是，我们就可以适当变通，虽然 LCA 我们只要一个，但是 LCA 父亲方向的那一堆，我们都是不需要的，所以说式子应该是：

然后其他的部分就一模一样，不过传的参数就需要四颗线段树才可以，代码就不再给了。

算法模板：努力即魔法

先别高兴，在刚刚的若干的模板题的锻炼下，我相信你已经学会了基本的主席树，所以说这个不再是模板题了会略略有一点点难度，嗯，就亿点点。

题目大意

题目传送门 ：P2617 Dynamic Rankings - 洛谷 | 计算机科学教育新生态

给定一个含有 $n$ 个数的序列 $a_1,a_2 \dots a_n$，需要支持两种操作：

  • Q l r k 表示查询下标在区间 $[l,r]$ 中的第 $k$ 小的数
  • C x y 表示将 $a_x$ 改为 $y$

解题思路

嗯，非常简单，一眼就是带修改的可持久化线段树。什么？你没看出来？重开之路

那么这个带修第 k 小似乎也不难了。只不过这次查询时要同时处理的线段树是树状数组左端点 $l-1$ 到右端点 $r$ 所有 $\operatorname{lowbit}$ 不断相减的全部内容罢了。

绝对不难，包不难的，代码自己写去（绝对不是我不想写

正确代码

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
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
namespace FastIO {
    template<typename T> inline T read(T& x) {
        x = 0;
        int f = 1;
        char ch;
        while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
        while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
        x *= f;
        return x;
    }
    template<typename T, typename... Args> inline void read(T& x, Args&... x_) {
        read(x);
        read(x_...);
    }
    inline ll read() {
        ll x;
        read(x);
        return x;
    }
};
using namespace FastIO;

const int N = 1e4 + 5;
#define lowbit(x) ((x) & -(x))

int n, m, sz, totn, totx, toty;
int a[N], b[N << 1], ca[N], cb[N], cc[N];
int xx[N], yy[N], rt[N], size[600 * N], ls[600 * N], rs[600 * N];

void Insert(int& o, int l, int r, int x, int q, int v) {
    o = ++sz;
    size[o] = size[x] + v;
    ls[o] = ls[x];
    rs[o] = rs[x];
    if (l == r) return;
    int mid = (l + r) >> 1;
    if (q <= mid) Insert(ls[o], l, mid, ls[x], q, v);
    else Insert(rs[o], mid + 1, r, rs[x], q, v);
}

int Query(int l, int r, int q) {
    if (l == r) return l;
    int sum = 0, mid = (l + r) >> 1;
    for (int i = 1; i <= totx; i++) sum -= size[ls[xx[i]]];
    for (int i = 1; i <= toty; i++) sum += size[ls[yy[i]]];
    if (q <= sum) {
        for (int i = 1; i <= totx; i++) xx[i] = ls[xx[i]];
        for (int i = 1; i <= toty; i++) yy[i] = ls[yy[i]];
        return Query(l, mid, q);
    } else {
        for (int i = 1; i <= totx; i++) xx[i] = rs[xx[i]];
        for (int i = 1; i <= toty; i++) yy[i] = rs[yy[i]];
        return Query(mid + 1, r, q - sum);
    }
}

void Add(int x, int v) {
    int k = lower_bound(b + 1, b + totn + 1, a[x]) - b;
    for (int i = x; i <= n; i += lowbit(i)) Insert(rt[i], 1, totn, rt[i], k, v);
}

void Input() {
    read(n, m);
    for (int i = 1; i <= n; i++) read(a[i]), b[++totn] = a[i];
    for (int i = 1; i <= m; i++) {
        char s[20];
        scanf("%s", s);
        read(ca[i], cb[i]);
        if (s[0] == 'Q') read(cc[i]);
        else b[++totn] = cb[i];
    }
    sort(b + 1, b + totn + 1);
    totn = unique(b + 1, b + totn + 1) - b - 1;
    for (int i = 1; i <= n; i++) Add(i, 1);
}

void Work() {
    for (int i = 1; i <= m; i++) {
        if (cc[i]) {
            totx = toty = 0;
            for (int j = ca[i] - 1; j; j -= lowbit(j)) xx[++totx] = rt[j];
            for (int j = cb[i]; j; j -= lowbit(j)) yy[++toty] = rt[j];
            printf("%d\n", b[Query(1, totn, cc[i])]);
        } else {
            Add(ca[i], -1);
            a[ca[i]] = cb[i];
            Add(ca[i], 1);
        }
    }
}

int main() {
    int T = 1;
    while (T--) {
        Input();
        Work();
    }
    return 0;
}

算法应用：纯真的羁绊

接下来才是真正的主席树应用！

可持久化并查集

所谓可持久化并查集，其实就是并查集可以查询历史版本，就好比说，在什么什么时候，那个和那个团体是针对关系，然后再什么什么之后，这两个团体合并了，这时候普通并查集只能查询到合并，不能查询到分裂的状态，这就是普通并查集的限制。

那么我们要如何实现这个可持久化并查集呢？其实说难不难说简单不简单，可持久化并查集就是用可持久化数组分别维护它的组成部分就可以了。一般来说，并查集应该是 fa 数组，然后通过路径压缩来得到均摊 $O(n\times\alpha(n))$ 的复杂度。但是如果用在可持久化并查集就不可以了。

因为我们的可持久化并查集是一个可以查询历史版本的东西，你要是用他，万恶的出题人就会让你反复做 $O(n)$ 的操作，然你卡死在 $O(n^2)$，所以说我们要用严格稳定的算法，但是所谓严格稳定的合并算法是什么？按秩合并。

友情链接：

【奇技淫巧】特殊思维题的复杂度分析 | 祝馀宫

嗯，众所周知，按秩合并的复杂度应该是 $O(n\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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
// copied from solution
#include<bits/stdc++.h>
#define N 300005
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int n,m,now,to,cnt,rt[N];
struct tree
{
	int ls,rs,fa,dep;
}tr[N*20];
inline int build(int l,int r)
{
	int to=++cnt;
	if(l==r)
	{
		tr[to].fa=l;
		return to;
	}
	int mid=(l+r)>>1;
	tr[to].ls=build(l,mid);
	tr[to].rs=build(mid+1,r);
	return to;
}
inline int que(int now,int l,int r,int x)
{
	if(l==r)return now;
	int mid=(l+r)>>1;
	if(mid>=x)return que(tr[now].ls,l,mid,x);
	else return que(tr[now].rs,mid+1,r,x);
}
inline int find(int now,int a)
{
	int fa=que(rt[now],1,n,a);
	if(tr[fa].fa==a)return fa;
	return find(now,tr[fa].fa);
}
inline int news(int now)
{
	int to=++cnt;
	tr[to]=tr[now];
	return to;
}
inline int hb(int now,int l,int r,int x,int f)
{
	int to=news(now);
	if(l==r)
	{
		tr[to].fa=f;
		return to;
	}
	int mid=(l+r)>>1;
	if(mid>=x)tr[to].ls=hb(tr[now].ls,l,mid,x,f);
	else tr[to].rs=hb(tr[now].rs,mid+1,r,x,f);
	return to;
}
inline int add(int now,int l,int r,int x)
{
	int to=news(now); 
	if(l==r)
	{
		tr[to].dep++;
		return to;
	}
	int mid=(l+r)>>1;
	if(mid>=x)tr[to].ls=add(tr[now].ls,l,mid,x);
	else tr[to].rs=add(tr[now].rs,mid+1,r,x);
	return to;
}
inline void merge(int now,int a,int b)
{
	rt[now]=rt[now-1];
	a=find(now,a);b=find(now,b);
	if(tr[a].fa!=tr[b].fa)
	{
		if(tr[a].dep>tr[b].dep)swap(a,b);
		rt[now]=hb(rt[now-1],1,n,tr[a].fa,tr[b].fa);
		if(tr[a].dep==tr[b].dep)rt[now]=add(rt[now],1,n,tr[b].fa);
	} 
}
inline bool pan(int now,int a,int b)
{
	a=find(now,a),b=find(now,b);
	if(tr[a].fa==tr[b].fa)return 1;
	else return 0;
}
int main()
{
	n=read();m=read();
	rt[0]=build(1,n);
	int op,a,b;
	for(int i=1;i<=m;i++)
	{
		op=read();a=read();
		if(op==1)
		{
			b=read();
			merge(i,a,b);
		}
		if(op==2)rt[i]=rt[a];
		if(op==3)
		{
			b=read();
			if(pan(i-1,a,b))cout<<1<<"\n";
			else cout<<0<<"\n";
			rt[i]=rt[i-1];
		}
	}
	return 0;
}

可持久化字典树

可持久化字典树也是一样的！可以查询每次插入一个数之前的版本，这里不在赘述，感兴趣出门右转 OIwiki

可持久化字典树 - OI Wiki

算法实战：将一切美好献给你

查看相关算法标签喵！

参考资料（以下排名不分先后）