主席树（可持久化线段树）

发表于 | 更新于: | 分类于

主席树用于维护多个版本的线段树。由于开多颗线段树的话空间会炸到飞起，所以可以充分利用每棵线段树中的重复部分。比如在第$i + 1$的版本的末尾新增一个节点，第$i + 1$棵版本的线段树和第i棵线段树的区别只是rt的右儿子及其子树中的一小部分。我们就可以在每一次更新版本时，另开那些有变化的节点，并与没有变化的节点连边（我们把这称之为动态开点），再把新版本的根节点存起来，这样即可节省大量空间。查询仿照普通线段树即可，

注意事项

有些题目一开始一定要开一棵空树；

JZOJ 3794 高级打字机

Description

早苗入手了最新的高级打字机。最新款自然有着与以往不同的功能，那就是它具备撤销功能，厉害吧。
请为这种高级打字机设计一个程序，支持如下3种操作：
T x：在文章末尾打下一个小写字母x。(type操作)
U x：撤销最后的x次修改操作。（Undo操作）（注意Query操作并不算修改操作）
Q x：询问当前文章中第x个字母并输出。（Query操作）文章一开始可以视为空串。

Input

第1行：一个整数n，表示操作数量。以下n行，每行一个命令。保证输入的命令合法。

Output

每行输出一个字母，表示Query操作的答案。

Sample Input

1
2
3
4
5
6
7
8
7
T a
T b
T c
Q 2
U 2
T c
Q 2

Sample Output

1
bc

Data Constraint

n<=100000；Undo操作可以撤销Undo操作。

代码

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
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;

const int N = 10000007;

int n, tot = 0, cnt = 0, t;
int rt[N], lson[N], rson[N], len[N];
char v[N], c;

void add(int &cur, int po, int l, int r, int last)
{
    if (!cur) cur = ++tot;
    if (l == r)
    {
        v[cur] = c;
        return;
    }
    int mid = (l + r) >> 1;
    if (po <= mid) 
        rson[cur] = rson[last], add(lson[cur], po, l, mid, lson[last]);
    if (mid + 1 <= po)
        lson[cur] = lson[last], add(rson[cur], po, mid + 1, r, rson[last]);    
}
char ask(int po, int cur, int l, int r)
{
    if (l == r) 
        return v[cur];
    int mid = (l + r) >> 1;
    if (po <= mid)
        return ask(po, lson[cur], l, mid);
    if (mid + 1 <= po)
        return ask(po, rson[cur], mid + 1, r);
}
int main()
{
    scanf("%d", &n);
    memset(rt, 0, sizeof rt);
    memset(lson, 0, sizeof lson);
    memset(rson, 0, sizeof rson);
    memset(len, 0, sizeof len);
    for (int i = 1; i <= n; i++)
    {
        char type;
        scanf(" %c", &type);
        if (type == 'T')
        {
            scanf(" %c", &c);
            len[++cnt] = len[cnt - 1] + 1;
            add(rt[cnt], len[cnt], 1, N, rt[cnt - 1]);//r在这道题中一定要是常数N哦，不然不变化的节点所代表的区间就不一样了 
        }
        if (type == 'U')
        {
            scanf("%d", &t);
            len[++cnt] = len[cnt - t - 1];
            rt[cnt] = rt[cnt - t - 1];
        }
        if (type == 'Q')
        {
            scanf("%d", &t);
            printf("%c\n", ask(t, rt[cnt], 1, N));
        }
    }
    return 0;
}