可持久化数据结构第二部分：可持久化平衡树和文艺平衡树。阅读本文需要前缀知识FHQ Treap。

可持久化平衡树

        可持久化数据结构在前一篇文章中已经提到。fhq Treap是非旋的树堆，可以很好地实现可持久化平衡树。
        根据前一篇文章的铺垫，可以初步理解可持久化数据结构的实现原理，那就是只要需要修改原有结点，就重建一个。旋转操作很容易破坏原树的结构，而fhq Threap没有旋转操作，在实现可持久化时有天然优势。一个模板题。
        fhq Treap的核心操作为split和merge。只要修改这两个函数就可以实现可持久化。具体实现过程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
inline int newNode(Node *p) {//通过传入指针来构造一个相同内容的新结点
    static int cnt = 1;
    node[cnt] = *p;
    return cnt++;
}

void split(int rt, int &a, int &b, int v) {//注意newNode函数的使用
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (node[rt].v <= v)a = newNode(node + rt), split(node[rt].ch[1], node[a].ch[1], b, v), update(a);
    else b = newNode(node + rt), split(node[rt].ch[0], a, node[b].ch[0], v), update(b);
}

        split中实现可持久化的原则是不能修改rt树上的结点。因此，当需要修改时，a和b总是需要拷贝一份rt结点，再进行修改操作。注意这里的update需要在两个分枝分别进行调用，这与普通的fhq Treap中一步update(rt)有所不同。
        那merge函数是不是也需要不断拷贝结点？从道理上讲，这样做完全没有问题，可以得到下面的代码：
1
2
3
4
5
6
7
8
9
void merge(int &rt, int a, int b) {
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (node[a].key > node[b].key)rt = newNode(node + a), merge(node[rt].ch[1], node[a].ch[1], b);
    else rt = newNode(node + b), merge(node[rt].ch[0], a, node[b].ch[0]);
    update(rt);
}

        这里merge可持久化的原则是不能修改a和b上的结点。因此，当需要修改时，rt总是拷贝一份a或b的结点，再进行更新。
        这样做没有什么错，只是浪费了空间。注意到我们在fhq Treap上的操作总是先split再merge，这样在merge之前，需要新建的结点已经被split过程新建出来了。可以这样做的不严格证明：split总是要按照一定指标来进行，譬如本题需要按值分离。那些新建结点与原有结点之间的交界部分姑且称之为断层，断层处体现了split的依据。无论是插入结点还是删除结点，后来merge的操作总是在断层上进行。比如插入值为x的结点，需要先将不大于x的结点树split出来，这样新的结点必然是接在这棵树的断层上的，因此原有的结点不会被修改，仅有split时新建的结点被修改。merge操作的树与之前的split均为同一版本，于是就可以省略复制结点的过程。
        这样merge过程保留原有的函数不变即可，从而降低空间消耗。后面的操作也没有什么大的变动，全代码如下：
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
#include<bits/stdc++.h>

#define N 500005
using namespace std;

struct Node {
    int v{}, key{}, ch[2]{}, num;

    Node() : num(0) {
        ch[0] = ch[1] = 0;
    }
} node[N << 6];

inline void read(int &s) {
    char e = getchar();
    int p = 0;
    s = 0;
    while (e < '-')e = getchar();
    if (e == '-')e = getchar(), p = 1;
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    if (p)s = -s;
}

int root[N], ver[N], n, a, b, c, rcnt = 1;

inline int newNode(Node *p) {
    static int cnt = 1;
    node[cnt] = *p;
    return cnt++;
}

inline void update(int x) {
    node[x].num = node[node[x].ch[0]].num + node[node[x].ch[1]].num + 1;
}

void split(int rt, int &a, int &b, int v) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    if (node[rt].v <= v)a = newNode(node + rt), split(node[rt].ch[1], node[a].ch[1], b, v), update(a);
    else b = newNode(node + rt), split(node[rt].ch[0], a, node[b].ch[0], v), update(b);
}

void merge(int &rt, int a, int b) {
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    if (node[a].key > node[b].key)rt = a, merge(node[rt].ch[1], node[a].ch[1], b);
    else rt = b, merge(node[rt].ch[0], a, node[b].ch[0]);
    update(rt);
}

inline int insert(int v, int x) {
    int p = newNode(node), a, b, c;
    node[p].key = rand(), node[p].v = x, node[p].num = 1, split(root[ver[v]], a, b, x);
    merge(a, a, p), merge(c, a, b);
    return c;
}

inline int delNum(int v, int x) {
    int a, b, c;
    split(root[ver[v]], a, b, x), split(a, a, c, x - 1);
    merge(c, node[c].ch[0], node[c].ch[1]), merge(a, a, c), merge(c, a, b);
    return c;
}

inline int findRank(int v, int x) {
    int cur = root[ver[v]], nxt = 0, ans = 0;
    while (true) {
        if (node[cur].v < x)nxt = node[cur].ch[1], ans += node[cur].num - node[nxt].num;
        else if (node[cur].v > x)nxt = node[cur].ch[0];
        else {
            ans += node[node[cur].ch[0]].num;
            break;
        }
        if (nxt != 0)cur = nxt;
        else break;
    }
    return ans + 1;
}

inline int preNum(int v, int x) {
    int cur = root[ver[v]], nxt = 0, maxn = -2147483647, ans = -1;
    while (true) {
        if (node[cur].v > x)nxt = node[cur].ch[0];
        else if (node[cur].v < x) {
            nxt = node[cur].ch[1];
            if (node[cur].v > maxn)maxn = node[cur].v, ans = cur;
        } else nxt = node[cur].ch[0];
        if (nxt != 0)cur = nxt;
        else break;
    }
    return ans == -1 ? -2147483647 : node[ans].v;
}

inline int nextNum(int v, int x) {
    int cur = root[ver[v]], nxt = 0, minn = 2147483647, ans = -1;
    while (true) {
        if (node[cur].v < x)nxt = node[cur].ch[1];
        else if (node[cur].v > x) {
            nxt = node[cur].ch[0];
            if (node[cur].v <= minn)minn = node[cur].v, ans = cur;
        } else nxt = node[cur].ch[1];
        if (nxt != 0)cur = nxt;
        else break;
    }
    return ans == -1 ? 2147483647 : node[ans].v;
}

inline int findNum(int v, int x) {
    int cur = root[ver[v]], nxt = 0;
    while (true) {
        if (node[node[cur].ch[0]].num >= x)nxt = node[cur].ch[0];
        else if (x > node[node[cur].ch[0]].num && x <= node[node[cur].ch[0]].num + 1)return node[cur].v;
        else nxt = node[cur].ch[1], x -= node[node[cur].ch[0]].num + 1;
        if (nxt != 0)cur = nxt;
        else break;
    }
    return -1;
}

int main() {
    srand(time(NULL)), read(n);
    for (int i = 1; i <= n; i++) {
        read(a), read(b), read(c);
        if (b == 1)root[rcnt] = insert(a, c), ver[i] = rcnt++;
        else if (b == 2)root[rcnt] = delNum(a, c), ver[i] = rcnt++;
        else if (b == 3)printf("%d\n", findRank(a, c)), ver[i] = ver[a];
        else if (b == 4)printf("%d\n", findNum(a, c)), ver[i] = ver[a];
        else if (b == 5)printf("%d\n", preNum(a, c)), ver[i] = ver[a];
        else printf("%d\n", nextNum(a, c)), ver[i] = ver[a];
    }
    return 0;

可持久化文艺平衡树

        有可持久化平衡树，自然有可持久化文艺平衡树。它同样可以用fhq Treap实现，模板题。
        与上面类似：spilt时复制结点，merge时不用复制。但这里需要特别注意的是：下压标记时也需要复制结点。这是因为下压标记需要修改左右子树的标记，对结果造成影响（这个结点的两个子结点可能也属于其它版本），因此需要复制一份。

1
2
3
4
5
6
7
inline void down(int x) {
    if (!node[x].tag)return;
    if (node[x].ch[0])node[x].ch[0] = newNode(node + node[x].ch[0]);
    if (node[x].ch[1])node[x].ch[1] = newNode(node + node[x].ch[1]);
    swap(node[x].ch[0], node[x].ch[1]);
    node[node[x].ch[0]].tag ^= 1, node[node[x].ch[1]].tag ^= 1, node[x].tag = 0;
}

        在结点中添加指标sum记录子树和，之后就可以搞出来了。全代码（本题强制在线）：
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
#include<bits/stdc++.h>

#define N 200005
using namespace std;

struct Node {
    int v{}, key{}, ch[2]{}, num;
    long long sum;
    short tag;
} node[N << 6];

inline long long read() {
    char e = getchar();
    int p = 0;
    long long s = 0;
    while (e < '-')e = getchar();
    if (e == '-')e = getchar(), p = 1;
    while (e > '-')s = (s << 1) + (s << 3) + (e & 15), e = getchar();
    return p ? -s : s;
}

int root[N], ver[N], rcnt = 1;
long long n, opt, a, b, v;

inline int newNode(Node *p) {
    static int cnt = 1;
    node[cnt] = *p;
    return cnt++;
}

inline void update(int x) {
    node[x].num = node[node[x].ch[0]].num + node[node[x].ch[1]].num + 1;
    node[x].sum = node[node[x].ch[0]].sum + node[node[x].ch[1]].sum + node[x].v;
}

inline void down(int x) {
    if (!node[x].tag)return;
    if (node[x].ch[0])node[x].ch[0] = newNode(node + node[x].ch[0]);
    if (node[x].ch[1])node[x].ch[1] = newNode(node + node[x].ch[1]);
    swap(node[x].ch[0], node[x].ch[1]);
    node[node[x].ch[0]].tag ^= 1, node[node[x].ch[1]].tag ^= 1, node[x].tag = 0;
}

void split(int rt, int &a, int &b, int v) {
    if (rt == 0) {
        a = b = 0;
        return;
    }
    down(rt);
    if (node[node[rt].ch[0]].num < v)
        a = newNode(node + rt), split(node[rt].ch[1], node[a].ch[1], b, v - node[node[rt].ch[0]].num - 1), update(a);
    else b = newNode(node + rt), split(node[rt].ch[0], a, node[b].ch[0], v), update(b);
}

void merge(int &rt, int a, int b) {
    if (a == 0 || b == 0) {
        rt = a + b;
        return;
    }
    down(a), down(b);
    if (node[a].key > node[b].key)rt = a, merge(node[rt].ch[1], node[a].ch[1], b);
    else rt = b, merge(node[rt].ch[0], a, node[b].ch[0]);
    update(rt);
}

inline int insert(int v, int x, int y) {
    int p = newNode(node), a, b, c;
    node[p].key = rand(), node[p].sum = node[p].v = y, node[p].num = 1, split(root[ver[v]], a, b, x);
    merge(a, a, p), merge(c, a, b);
    return c;
}

inline int delNum(int v, int x) {
    int a, b, c;
    split(root[ver[v]], a, b, x - 1), split(b, b, c, 1), merge(a, a, c);
    return a;
}

int main() {
    long long last = 0;
    srand(time(NULL));
    n = read();
    for (int i = 1; i <= n; i++) {
        v = read(), opt = read(), a = read() ^ last;
        if (opt == 1)b = read() ^ last, root[rcnt] = insert(v, a, b), ver[i] = rcnt++;
        else if (opt == 2)root[rcnt] = delNum(v, a), ver[i] = rcnt++;
        else if (opt == 3) {
            b = read() ^ last;
            int x, y, z, p;
            split(root[ver[v]], x, y, b), split(x, x, z, a - 1), node[z].tag ^= 1, merge(p, x, z), merge(x, p, y);
            root[rcnt] = x, ver[i] = rcnt++;
        } else {
            int x, y, z, p;
            b = read() ^ last;
            split(root[ver[v]], x, y, b), split(x, x, z, a - 1), printf("%lld\n", last = node[z].sum);
            merge(p, x, z), merge(x, p, y);
            root[rcnt] = x, ver[i] = rcnt++;
        }
    }
    return 0;
}