测试2

最近学了一下平衡树，想做一些笔记。

1.$Splay$

$Splay$是我学会的第一棵平衡树（滑稽）

 $Splay$通过$Splay$操作，让$Splay$保持乱序，即“平衡”。

基本操作：

1.$pushup$/$pushdown$ 维护标记。$O(1)$

2.$rotate$ 上旋。$O(log n)$

3.$splay$ 将节点向上移动。$O(1)$

模板

  1 #include<cstdio>
  2 #define MAXL 100003
  3 #define INF (1 << 30)
  4 using namespace std;
  5 class Splay {
  6     #define root e[0].ch[1]
  7     private:
  8         class node {
  9             public:
 10                 int v, father, ch[2], recy, sum;
 11         } e[MAXL];
 12         int n, points;
 13         inline void update(int x){
 14             e[x].sum = e[e[x].ch[0]].sum + e[e[x].ch[1]].sum + e[x].recy;
 15         }
 16         inline int identify(int x){
 17             return e[e[x].father].ch[1] == x;
 18         }
 19         inline void connect(int x, int f, int son){
 20             e[f].ch[son] = x;
 21             e[x].father = f;
 22         }
 23         inline void rotate(int x){
 24             int y = e[x].father, mroot = e[y].father, mrootson = identify(y), yson = identify(x),
 25                     B = e[x].ch[yson ^ 1];
 26             connect(B, y, yson);connect(y, x, yson ^ 1);connect(x, mroot, mrootson);
 27             update(y);update(x);
 28         }
 29         inline void splay(int at, int to){
 30             to = e[to].father;
 31             while(e[at].father != to){
 32                 int up = e[at].father;
 33                 if(e[up].father == to) rotate(at);
 34                 else if(identify(at) == identify(up)){
 35                     rotate(up);rotate(at);
 36                 } else {
 37                     rotate(at);rotate(at);
 38                 }
 39             }
 40         }
 41         inline int crepoint(int v, int father){
 42             n ++;
 43             e[n].v = v;
 44             e[n].father = father;
 45             e[n].sum = e[n].recy = 1;
 46             return n;
 47         }
 48         inline void destroy(int x){
 49             e[x].v = e[x].father = e[x].ch[0] = e[x].ch[1] = e[x].recy = e[x].sum = 0;
 50             if(x == n) n --;
 51         }
 52     public:
 53         inline int getroot(){return root;}
 54         inline int find(int v){
 55             int now = root;
 56             while(true){
 57                 if(e[now].v == v){
 58                     splay(now, root);
 59                     return now;
 60                 }
 61                 int nxt = e[now].v < v;
 62                 if(!e[now].ch[nxt]) return 0;
 63                 now = e[now].ch[nxt];
 64             }
 65         }
 66         inline int build(int v){
 67             if(!points) n = 0;
 68             points ++;
 69             if(!n){
 70                 root = 1;
 71                 return crepoint(v, 0);
 72             }
 73             int now = root;
 74             while(true){
 75                 e[now].sum ++;
 76                 if(e[now].v == v){
 77                     e[now].recy ++;
 78                     return now;
 79                 }
 80                 int nxt = e[now].v < v;
 81                 if(!e[now].ch[nxt]) return e[now].ch[nxt] = crepoint(v, now);
 82                 now = e[now].ch[nxt];
 83             }
 84             return 0;
 85         }
 86         inline void push(int v){
 87             splay(build(v), root);
 88         }
 89         inline void pop(int v){
 90             int deal = find(v);
 91             if(!deal) return;
 92             points --;
 93             if(e[deal].recy > 1){
 94                 e[deal].recy --;
 95                 e[deal].sum --;
 96                 return;
 97             }
 98             if(!e[deal].ch[0]){
 99                 root = e[deal].ch[1];
100                 e[root].father = 0;
101             } else {
102                 int lef = e[deal].ch[0];
103                 while(e[lef].ch[1]) lef = e[lef].ch[1];
104                 splay(lef, e[deal].ch[0]);
105                 int rig = e[deal].ch[1];
106                 connect(rig, lef, 1);connect(lef, 0, 1);
107                 update(lef);
108             }
109             destroy(deal);
110         }
111         inline int rank(int v){
112             int ans = 1, now = root;
113             while(true){
114                 if(e[now].v == v){
115                     ans += e[e[now].ch[0]].sum;
116                     break;
117                 }
118                 if(!now) break;
119                 if(v < e[now].v) now = e[now].ch[0];
120                 else {
121                     ans += e[e[now].ch[0]].sum + e[now].recy;
122                     now = e[now].ch[1];
123                 }
124             }
125             if(now) splay(now, root);
126             return ans;
127         }
128         inline int atrank(int x){
129             if(x > points) return INF;
130             int now = root;
131             while(true){
132                 int minused = e[now].sum - e[e[now].ch[1]].sum;
133                 if(x > e[e[now].ch[0]].sum && x <= minused) break;
134                 if(x <= minused) now = e[now].ch[0];
135                 else {
136                     x -= minused;
137                     now = e[now].ch[1];
138                 }
139             }
140             splay(now, root);
141             return e[now].v;
142         }
143         inline int lower(int v){
144             int now = root, res = -INF;
145             while(now){
146                 if(e[now].v < v && e[now].v > res) res = e[now].v;
147                 if(e[now].v >= v) now = e[now].ch[0];
148                 else now = e[now].ch[1];
149             }
150             return res;
151         }
152         inline int upper(int v){
153             int now = root, res = INF;
154             while(now){
155                 if(e[now].v > v && e[now].v < res) res = e[now].v;
156                 if(e[now].v > v) now = e[now].ch[0];
157                 else now = e[now].ch[1];
158             }
159             return res;
160         }
161 } sp;
162 int n;
163 int main(){
164     scanf("%d", &n);
165     while(n --){
166         int opt, x;
167         scanf("%d%d", &opt, &x);
168         switch(opt){
169             case 1:
170                 sp.push(x);
171                 break;
172             case 2:
173                 sp.pop(x);
174                 break;
175             case 3:
176                 printf("%dn", sp.rank(x));
177                 break;
178             case 4:
179                 printf("%dn", sp.atrank(x));
180                 break;
181             case 5:
182                 printf("%dn", sp.lower(x));
183                 break;
184             case 6:
185                 printf("%dn", sp.upper(x));
186         }
187     }
188 }
View Code

 因为$Splay$操作，$Splay$是一种非常强大的序列区间操作的数据结构。

  1 // 文艺平衡树
  2 // luogu-judger-enable-o2
  3 #include<cstdio>
  4 #include<algorithm>
  5 #define MAXL 100010
  6 #define Rint register int
  7 using namespace std;
  8 int n, m;
  9 struct Splay {
 10     #define root e[0].ch[1]
 11     struct node {
 12         int v, father, ch[2], sum, tag;
 13     } e[MAXL];
 14     int n;
 15     Splay(): n(0){}
 16     inline void update(int x){
 17         e[x].sum = e[e[x].ch[0]].sum + e[e[x].ch[1]].sum + 1;
 18     }
 19     inline void pushdown(int x){
 20         if(x && e[x].tag){
 21             e[e[x].ch[0]].tag ^= 1;
 22             e[e[x].ch[1]].tag ^= 1;
 23             swap(e[x].ch[0], e[x].ch[1]);
 24             e[x].tag = 0;
 25         }
 26     }
 27     inline int identify(int x){
 28         return e[e[x].father].ch[1] == x;
 29     }
 30     inline int crepoint(int v, int f){
 31         e[++ n].v = v;
 32         e[n].father = f;
 33         e[n].sum = 1;
 34         e[n].tag = 0;
 35         return n;
 36     }
 37     inline void connect(int x, int f, int son){
 38         e[f].ch[son] = x;
 39         e[x].father = f;
 40     }
 41     inline void rotate(int x){
 42         int y = e[x].father, mroot = e[y].father, mrootson = identify(y), yson = identify(x),
 43                 B = e[x].ch[yson ^ 1];
 44         connect(B, y, yson);connect(y, x, yson ^ 1);connect(x, mroot, mrootson);
 45         update(y);update(x);
 46     }
 47     inline void splay(int at, int to){
 48         while(e[at].father != to){
 49             int up = e[at].father;
 50             if(e[up].father == to) rotate(at);
 51             else if(identify(at) == identify(up)){
 52                 rotate(up);rotate(at);
 53             } else {
 54                 rotate(at);rotate(at);
 55             }
 56         }
 57     }
 58     inline int build(int fa, int l, int r){
 59         if(l > r) return 0;
 60         int mid = l + r >> 1, now = crepoint(mid, fa);
 61         if(!root) root = now;
 62         e[now].ch[0] = build(now, l, mid - 1);
 63         e[now].ch[1] = build(now, mid + 1, r);
 64         update(now);
 65         return now;
 66     }
 67     inline int atrank(int x){
 68         int now = root;
 69         while(true){
 70             pushdown(now);
 71             int minused = e[e[now].ch[0]].sum + 1;
 72             if(x == minused) return now;
 73             if(x < minused) now = e[now].ch[0];
 74             else {
 75                 x -= minused;
 76                 now = e[now].ch[1];
 77             }
 78         }
 79     }
 80     inline void rev(int l, int r){
 81         l = atrank(l);
 82         r = atrank(r + 2);
 83         splay(l, 0);
 84         splay(r, l);
 85         e[e[e[root].ch[1]].ch[0]].tag ^= 1;
 86     }
 87     inline void write(int x){
 88         pushdown(x);
 89         if(e[x].ch[0]) write(e[x].ch[0]);
 90         if(e[x].v > 1 && e[x].v < ::n + 2) printf("%d ", e[x].v - 1);
 91         if(e[x].ch[1]) write(e[x].ch[1]);
 92     }
 93 } sp;
 94 int main(){
 95     scanf("%d%d", &n, &m);
 96     sp.build(0, 1, n + 2);
 97     while(m --){
 98         int l, r;
 99         scanf("%d%d", &l, &r);
100         sp.rev(l, r);
101     }
102     sp.write(sp.root);
103 }
View Code

 2.替罪羊树

替罪羊树有一个平衡因子$alpha$，一般取0.75~0.8时最佳。

每次在更新和查询的时候，对于节点$x$，若$max(siz_{ls},siz_{rs})>siz_x*alpha$，则对以$x$为根的子树进行拍扁重构。

拍扁指的是将排序的数组，即中序遍历记录到一个数组中，然后在对这个子树进行建树，建树的时候选择中点作为根，这颗子树就平衡了。

因为经常需要拍扁重构，所以最好使用垃圾回收，用一个内存池，使用一个栈或队列记录空余空间，这样就不会担心$MLE$了。

#include<cstdio>
#define alpha 0.8
#define MAXN 100003
#define Rint register int
using namespace std;
int n, top, goat, rt, t1, ls[MAXN], rs[MAXN], siz[MAXN], v[MAXN], tmp[MAXN], cnt[MAXN], stk[MAXN];
inline int max(int a, int b){return a < b ? b : a;}
inline void dfs(int root){
    if(root){
        dfs(ls[root]);
        if(exist[root]) tmp[++ t1] = root;
        else stk[top ++] = root;
        dfs(rs[root]);
    }
}
inline void build(int &root, int L, int R){
    int mid = L + R >> 1;
    root = tmp[mid];
    if(L == R){
        siz[root] = cnt[root] = 1;
        ls[root] = rs[root] = 0;
        exist[root] = true;
        return;
    }
    if(L < mid) build(ls[root], L, mid - 1);
    else ls[root] = 0;
    build(rs[root], mid + 1, R);
    siz[root] = siz[ls[root]] + siz[rs[root]] + 1;
    cnt[root] = cnt[ls[root]] + cnt[rs[root]] + 1;
}
inline void rebuild(int &root){
    t1 = 0;
    dfs(root);
    if(t1) build(root, 1, t1);
    else root = 0;
}
inline int rank(int x){
    int now = rt, ans = 1;
    while(now){
        if(x <= v[now]) now = ls[now];
        else {
            ans += siz[ls[now]] + exist[now];
            now = rs[now];
        }
    }
    return ans;
}
inline void insert(int &root, int x){
    if(!root){
        root = stk[-- top];
        v[root] = x;
        siz[root] = cnt[root] = 1;
        exist[root] = true;
        ls[root] = rs[root] = 0;
        return;
    }
    siz[root] ++;cnt[root] ++;
    if(x <= v[root]) insert(ls[root], x);
    else insert(rs[root], x);
    if(siz[root] * alpha < max(siz[ls[root]], siz[rs[root]])){
        if(goat){
            if(goat == ls[root]) rebuild(ls[root]);
            else rebuild(rs[root]);
            goat = 0;
        }
    } else goat = root;
}
inline void del_id(int root, int x){
    siz[root] --;
    if(exist[root] && x == siz[ls[root]] + 1){
        exist[root] = false;
        return;
    }
    if(x <= siz[ls[root]] + exist[root])
        del_id(ls[root], x);
    else
        del_id(rs[root], x - siz[ls[root]] - exist[root]);
}
inline void del_val(int x){
    del_id(rt, rank(x));
    if(siz[rt] < alpha * cnt[rt]) rebuild(rt);
}
inline int get_xth(int x){
    int now = rt;
    while(now){
        if(exist[now] && x == siz[ls[now]] + 1)
            return v[now];
        else if(x <= siz[ls[now]] + exist[now])
            now = ls[now];
        else{
            x -= siz[ls[now]] + exist[now];
            now = rs[now];
        }
    }
}
int main(){
    scanf("%d", &n);
    rt = 0;
    for(Rint i = 1;i <= 100000;i ++)
        stk[top ++] = i;
    for(Rint i = 1;i <= n;i ++){
        int opt, x;
        scanf("%d%d", &opt, &x);
        switch(opt){
            case 1:
                insert(rt, x);
                break;
            case 2:
                del_val(x);
                break;
            case 3:
                printf("%dn", rank(x));
                break;
            case 4:
                printf("%dn", get_xth(x));
                break;
            case 5:
                printf("%dn", get_xth(rank(x) - 1));
                break;
            case 6:
                printf("%dn", get_xth(rank(x + 1)));
        }
    }
}
View Code

3.$Treap$

$Treap=Tree+Heap$，这种平衡树利用堆的平衡性质，来维持整个二叉排序树平衡。

每个节点有一个$key$和$prio$值，$key$是维护的集合的数值，$prio$是随机的优先级。

我们保证每一时刻整棵树对$key$是一棵二叉排序树，对$prio$是一个二叉堆。

如果遇到破坏堆性质的情况，使用$rotate$来维持二叉堆的性质。

1 inline void rotate(Treap *&x, int d){
2     Treap *y = x -> ch[d ^ 1];
3     if(y == null) return;
4     x -> ch[d ^ 1] = y -> ch[d];
5     y -> ch[d] = x;
6     y -> size = x -> size;
7     update(x);
8     x = y;
9 }

普通平衡树

  1 #include<cstdio>
  2 #define MAXN 100003
  3 #define INF 2147483647
  4 using namespace std;
  5 struct Treap {
  6     int key, prio, size, cnt;
  7     Treap *ch[2];
  8 } *null, *top, *root;
  9 inline int rand(){
 10     static int seed = 1475369;
 11     return seed = seed * 789456741LL % INF;
 12 }
 13 inline void init(){
 14     null = top = root = new Treap[MAXN];
 15     null -> ch[0] = null -> ch[1] = null;
 16     null -> key = null -> prio = INF;
 17     null -> size = null -> cnt = 0;
 18 }
 19 inline void update(Treap *&x){
 20     x -> size = x -> ch[0] -> size + x -> ch[1] -> size + x -> cnt; 
 21 }
 22 inline void rotate(Treap *&x, int d){
 23     Treap *y = x -> ch[d ^ 1];
 24     if(y == null) return;
 25     x -> ch[d ^ 1] = y -> ch[d];
 26     y -> ch[d] = x;
 27     y -> size = x -> size;
 28     update(x);
 29     x = y;
 30 }
 31 inline Treap* newnode(int key){
 32     top ++;
 33     top -> ch[0] = top -> ch[1] = null;
 34     top -> key = key;
 35     top -> prio = rand();
 36     top -> size = top -> cnt = 1;
 37     return top;
 38 }
 39 void insert(Treap *&x, int key){
 40     if(x == null){x = newnode(key); return;}
 41     if(x -> key == key) x -> cnt ++;
 42     else {
 43         int d = key > x -> key;
 44         insert(x -> ch[d], key);
 45         if(x -> prio > x -> ch[d] -> prio) rotate(x, d ^ 1);
 46     }
 47     update(x);
 48 }
 49 void erase(Treap *&x, int key){
 50     if(x == null) return;
 51     if(x -> key == key){
 52         if(x -> cnt > 1){x -> cnt --; update(x); return;}
 53         if(x -> ch[0] == null) x = x -> ch[1];
 54         else if(x -> ch[1] == null) x = x -> ch[0];
 55         else {
 56             int d = x -> ch[0] -> prio < x -> ch[1] -> prio;
 57             rotate(x, d);
 58             erase(x -> ch[d], key);
 59         }
 60     } else erase(x -> ch[key > x -> key], key);
 61     update(x);
 62 }
 63 inline int rank(int key){
 64     int ans = 1;
 65     Treap *now = root;
 66     while(true){
 67         if(now == null) return ans;
 68         if(now -> key == key)
 69             return ans + now -> ch[0] -> size;
 70         else if(now -> key > key)
 71             now = now -> ch[0];
 72         else {
 73             ans += now -> ch[0] -> size + now -> cnt;
 74             now = now -> ch[1];
 75         }
 76     }
 77 }
 78 inline int atrank(int x){
 79     Treap *now = root;
 80     while(true){
 81         int minused = now -> size - now -> ch[1] -> size;
 82         if(x > now -> ch[0] -> size && x <= minused) return now -> key;
 83         if(x <= now -> ch[0] -> size) now = now -> ch[0];
 84         else {
 85             x -= minused;
 86             now = now -> ch[1];
 87         }
 88     }
 89 }
 90 inline int lower(int key){
 91     Treap *now = root;
 92     int ans = -INF;
 93     while(now != null){
 94         if(now -> key < key && now -> key > ans) ans = now -> key;
 95         if(now -> key >= key) now = now -> ch[0];
 96         else now = now -> ch[1];
 97     }
 98     return ans;
 99 }
100 inline int upper(int key){
101     Treap *now = root;
102     int ans = INF;
103     while(now != null){
104         if(now -> key > key && now -> key < ans) ans = now -> key;
105         if(now -> key > key) now = now -> ch[0];
106         else now = now -> ch[1];
107     }
108     return ans;
109 }
110 int n;
111 int main(){
112 //    freopen("Treap.in", "r", stdin);
113 //    freopen("Treap.out", "w", stdout);
114     scanf("%d", &n);
115     init();
116     while(n --){
117         int opt, x;
118         scanf("%d%d", &opt, &x);
119         switch(opt){
120             case 1:
121                 insert(root, x);
122                 break;
123             case 2:
124                 erase(root, x);
125                 break;
126             case 3:
127                 printf("%dn", rank(x));
128                 break;
129             case 4:
130                 printf("%dn", atrank(x));
131                 break;
132             case 5:
133                 printf("%dn", lower(x));
134                 break;
135             case 6:
136                 printf("%dn", upper(x));
137         }
138     }
139 }
View Code

4.$fhq treap$

$fhq treap$和$treap$一样，使用随机权值来保持随机性质。

但它不是依靠$rotate$操作，而是分裂$split$和合并$merge$操作。

$split$将整棵树分为两部分，其中一部分的最大值小于另一部分的最小值。

$merge$是$split$的逆操作，需要一部分的最大值小于另一部分的最小值。

 1 inline void split(int now, int k, int &x, int &y){
 2     if(!now){
 3         x = y = 0;
 4         return;
 5     }
 6     pushdown(now);
 7     if(e[e[now].ch[0]].size < k){
 8         x = now; split(e[now].ch[1], k - e[e[now].ch[0]].size - 1, e[x].ch[1], y);
 9     } else {
10         y = now; split(e[now].ch[0], k, x, e[y].ch[0]);
11     }
12     pushup(now);
13 }
14 inline void merge(int &now, int x, int y){
15     if(!x || !y){
16         now = x ^ y;
17         return;
18     }
19     if(e[x].prio < e[y].prio){
20         pushdown(x);
21         now = x; merge(e[now].ch[1], e[x].ch[1], y);
22     } else {
23         pushdown(y);
24         now = y; merge(e[now].ch[0], x, e[y].ch[0]); 
25     }
26     pushup(now);
27 }

普通平衡树

  1 // luogu-judger-enable-o2
  2 #include<cstdio>
  3 #define Rint register int
  4 using namespace std;
  5 const int N = 100003, INF = 1000000007;
  6 int n;
  7 inline int rand(){
  8     static int seed = 20050915;
  9     return seed = seed * 19260817ll % 2147483647;
 10 }
 11 struct Node {
 12     int key, prio, size, ch[2];
 13 } e[N];
 14 int tot = 0, root = 1;
 15 inline int newnode(int key = 0){
 16     ++ tot;
 17     e[tot].key = key;
 18     e[tot].prio = rand();
 19     e[tot].size = 1;
 20     return tot;
 21 }
 22 inline void pushup(int x){
 23     e[x].size = e[e[x].ch[0]].size + e[e[x].ch[1]].size + 1;
 24 }
 25 inline void split(int now, int key, int &x, int &y){
 26     if(!now){
 27         x = y = 0;
 28         return;
 29     }
 30     if(e[now].key <= key){
 31         x = now; split(e[now].ch[1], key, e[x].ch[1], y);
 32     } else {
 33         y = now; split(e[now].ch[0], key, x, e[y].ch[0]);
 34     }
 35     pushup(now);
 36 }
 37 inline void merge(int &now, int x, int y){
 38     if(!x || !y){
 39         now = x + y;
 40         return;
 41     }
 42     if(e[x].prio < e[y].prio){
 43         now = x; merge(e[now].ch[1], e[x].ch[1], y);
 44     } else {
 45         now = y; merge(e[now].ch[0], x, e[y].ch[0]);
 46     }
 47     pushup(now);
 48 }
 49 inline void insert(int key){
 50     int x = 0, y = 0, z = newnode(key);
 51     split(root, key, x, y);
 52     merge(x, x, z);
 53     merge(root, x, y);
 54 }
 55 inline void erase(int key){
 56     int x = 0, y = 0, z = 0;
 57     split(root, key, x, y);
 58     split(x, key - 1, x, z);
 59     merge(z, e[z].ch[0], e[z].ch[1]);
 60     merge(x, x, z);
 61     merge(root, x, y);
 62 }
 63 inline int rank(int key){
 64     int x = 0, y = 0;
 65     split(root, key - 1, x, y);
 66     int ans = e[x].size + 1;
 67     merge(root, x, y);
 68     return ans;
 69 }
 70 inline int find(int now, int x){
 71     while(true){
 72         int minused = e[e[now].ch[0]].size + 1;
 73         if(x == minused) return e[now].key;
 74         if(x < minused) now = e[now].ch[0];
 75         else {
 76             x -= minused;
 77             now = e[now].ch[1];
 78         }
 79     }
 80 }
 81 inline int lower(int key){
 82     int x = 0, y = 0;
 83     split(root, key - 1, x, y);
 84     int ans = find(x, e[x].size);
 85     merge(root, x, y);
 86     return ans;
 87 }
 88 inline int upper(int key){
 89     int x = 0, y = 0;
 90     split(root, key, x, y);
 91     int ans = find(y, 1);
 92     merge(root, x, y);
 93     return ans;
 94 }
 95 int main(){
 96     scanf("%d", &n);
 97     newnode(2147483647);
 98     e[1].size = 0;
 99     while(n --){
100         int opt, x;
101         scanf("%d%d", &opt, &x);
102         switch(opt){
103             case 1:
104                 insert(x);
105                 break;
106             case 2:
107                 erase(x);
108                 break;
109             case 3:
110                 printf("%dn", rank(x));
111                 break;
112             case 4:
113                 printf("%dn", find(root, x));
114                 break;
115             case 5:
116                 printf("%dn", lower(x));
117                 break;
118             case 6:
119                 printf("%dn", upper(x));
120         }
121     }
122 }
View Code

因为$fhq treap$可以对树进行分裂合并，所以$fhq treap$可以用来维护序列问题，而且有时候比$splay$要方便得多。

文艺平衡树

 1 // luogu-judger-enable-o2
 2 #include<cstdio>
 3 #include<algorithm>
 4 #define Rint register int
 5 using namespace std;
 6 const int N = 100003, INF = 2147483647;
 7 int n, m;
 8 inline int rand(){
 9     static int seed = 20050915;
10     return seed = seed * 19260817ll % INF;
11 }
12 struct Node {
13     int key, prio, ch[2], size;
14     bool rev;
15 } e[N];
16 int root, tot = 0;
17 inline int newnode(int key = 0){
18     tot ++;
19     e[tot].key = key; e[tot].prio = rand(); e[tot].size = 1;
20     e[tot].ch[0] = e[tot].ch[1] = e[tot].rev = 0;
21     return tot;
22 }
23 inline void pushup(int x){
24     e[x].size = e[e[x].ch[0]].size + e[e[x].ch[1]].size + 1;
25 }
26 inline void pushdown(int x){
27     if(x && e[x].rev){
28         swap(e[x].ch[0], e[x].ch[1]);
29         e[e[x].ch[0]].rev ^= 1;
30         e[e[x].ch[1]].rev ^= 1;
31         e[x].rev = false;
32     }
33 }
34 inline void split(int now, int k, int &x, int &y){
35     if(!now){
36         x = y = 0;
37         return;
38     }
39     pushdown(now);
40     if(e[e[now].ch[0]].size < k){
41         x = now; split(e[now].ch[1], k - e[e[now].ch[0]].size - 1, e[x].ch[1], y);
42     } else {
43         y = now; split(e[now].ch[0], k, x, e[y].ch[0]);
44     }
45     pushup(now);
46 }
47 inline void merge(int &now, int x, int y){
48     if(!x || !y){
49         now = x ^ y;
50         return;
51     }
52     if(e[x].prio < e[y].prio){
53         pushdown(x);
54         now = x; merge(e[now].ch[1], e[x].ch[1], y);
55     } else {
56         pushdown(y);
57         now = y; merge(e[now].ch[0], x, e[y].ch[0]); 
58     }
59     pushup(now);
60 }
61 inline void rever(int l, int r){
62     int a = 0, b = 0, c = 0;
63     split(root, l - 1, a, b);
64     split(b, r - l + 1, b, c);
65     e[b].rev ^= 1;
66     merge(b, b, c);
67     merge(root, a, b);
68 }
69 inline void write(int x){
70     if(!x) return;
71     pushdown(x);
72     write(e[x].ch[0]);
73     printf("%d ", e[x].key);
74     write(e[x].ch[1]);
75 }
76 int main(){
77     scanf("%d%d", &n, &m);
78     root = newnode(1);
79     for(Rint i = 2;i <= n;i ++)
80         merge(root, root, newnode(i));
81     while(m --){
82         int l, r;
83         scanf("%d%d", &l, &r);
84         rever(l, r);
85     }
86     write(root);
87 }
View Code

因为$fhq treap$进行的分裂合并操作，不会大幅度改变树的形态，所以可以进行可持久化。

可持久化平衡树

  1 #include<cstdio>
  2 #define Rint register int
  3 using namespace std;
  4 const int N = 500003, INF = 2147483647;
  5 inline int rand(){
  6     static int seed = 20050915;
  7     return seed = seed * 19820605ll % INF;
  8 }
  9 struct Node {
 10     int key, prio, ch[2], size;
 11 } e[N * 50];
 12 int tot = 0, root[N];
 13 inline int newnode(int key = 0){
 14     e[++ tot].key = key; e[tot].prio = rand();
 15     e[tot].size = 1; e[tot].ch[0] = e[tot].ch[1] = 0;
 16     return tot;
 17 }
 18 inline void pushup(int x){
 19     e[x].size = e[e[x].ch[0]].size + e[e[x].ch[1]].size + 1;
 20 }
 21 inline int merge(int x, int y){
 22     if(!x || !y) return x + y;
 23     if(e[x].prio < e[y].prio){
 24         int now = ++ tot; e[now] = e[x];
 25         e[now].ch[1] = merge(e[x].ch[1], y);
 26         pushup(now); return now;
 27     }
 28     int now = ++ tot; e[now] = e[y];
 29     e[now].ch[0] = merge(x, e[y].ch[0]);
 30     pushup(now); return now;
 31 }
 32 inline void split(int now, int key, int &x, int &y){
 33     if(!now){
 34         x = y = 0;
 35         return;
 36     }
 37     if(e[now].key <= key){
 38         x = ++ tot; e[x] = e[now]; split(e[now].ch[1], key, e[x].ch[1], y); pushup(x);
 39     } else {
 40         y = ++ tot; e[y] = e[now]; split(e[now].ch[0], key, x, e[y].ch[0]); pushup(y);
 41     }
 42 }
 43 inline void insert(int &root, int key){
 44     int x = 0, y = 0, z = newnode(key);
 45     split(root, key, x, y);
 46     root = merge(merge(x, z), y);
 47 }
 48 inline void erase(int &root, int key){
 49     int x = 0, y = 0, z = newnode(key);
 50     split(root, key, x, y);
 51     split(x, key - 1, x, z);
 52     z = merge(e[z].ch[0], e[z].ch[1]);
 53     root = merge(merge(x, z), y);
 54 }
 55 inline int rank(int &root, int key){
 56     int x = 0, y = 0;
 57     split(root, key - 1, x, y);
 58     int ans = e[x].size + 1;
 59     root = merge(x, y);
 60     return ans;
 61 }
 62 inline int atrank(int now, int k){
 63     if(k == e[e[now].ch[0]].size + 1) return e[now].key;
 64     if(k <= e[e[now].ch[0]].size) return atrank(e[now].ch[0], k);
 65     return atrank(e[now].ch[1], k - e[e[now].ch[0]].size - 1);
 66 }
 67 inline int lower(int &root, int key){
 68     int x = 0, y = 0;
 69     split(root, key - 1, x, y);
 70     int ans = atrank(x, e[x].size);
 71     root = merge(x, y);
 72     return ans;
 73 }
 74 inline int upper(int &root, int key){
 75     int x = 0, y = 0;
 76     split(root, key, x, y);
 77     int ans = atrank(y, 1);
 78     root = merge(x, y);
 79     return ans;
 80 }
 81 int n;
 82 int main(){
 83     scanf("%d", &n);
 84     for(Rint i = 1;i <= n;i ++){
 85         int tim, opt, x;
 86         scanf("%d%d%d", &tim, &opt, &x);
 87         root[i] = root[tim];
 88         switch(opt){
 89             case 1:
 90                 insert(root[i], x); break;
 91             case 2:
 92                 erase(root[i], x); break;
 93             case 3:
 94                 printf("%dn", rank(root[i], x)); break;
 95             case 4:
 96                 printf("%dn", atrank(root[i], x)); break;
 97             case 5:
 98                 printf("%dn", lower(root[i], x)); break;
 99             case 6:
100                 printf("%dn", upper(root[i], x)); break;
101         }
102     }
103 }
View Code

可持久化文艺平衡树

  1 // luogu-judger-enable-o2
  2 #include<cstdio>
  3 #include<algorithm>
  4 #define Rint register int
  5 using namespace std;
  6 typedef long long LL;
  7 const int N = 220003, INF = 2147483647;
  8 inline int rand(){
  9     static int seed = 20050915;
 10     return seed = ((seed * 19260817ll % 998244353) ^ 20050818ll)% INF;
 11 }
 12 struct Node {
 13     int key, prio, ch[2], size;
 14     LL sum;
 15     bool rev;
 16 } e[N * 70];
 17 int tot, root[N];
 18 inline void pushup(int x){
 19     e[x].size = e[e[x].ch[0]].size + e[e[x].ch[1]].size + 1;
 20     e[x].sum = e[e[x].ch[0]].sum + e[e[x].ch[1]].sum + e[x].key;
 21 }
 22 inline void pushdown(int x){
 23     if(x && e[x].rev){
 24         if(e[x].ch[0]){
 25             int now = ++ tot;
 26             e[now] = e[e[x].ch[0]];
 27             e[now].rev ^= 1;
 28             e[x].ch[0] = now;
 29         }
 30         if(e[x].ch[1]){
 31             int now = ++ tot;
 32             e[now] = e[e[x].ch[1]];
 33             e[now].rev ^= 1;
 34             e[x].ch[1] = now;
 35         }
 36         swap(e[x].ch[0], e[x].ch[1]);
 37         e[x].rev = false;
 38     }
 39 }
 40 inline int crepoint(int key){
 41     tot ++;
 42     e[tot].key = e[tot].sum = key;
 43     e[tot].ch[0] = e[tot].ch[1] = e[tot].rev = 0;
 44     e[tot].size = 1;
 45     e[tot].prio = rand();
 46     return tot;
 47 }
 48 inline int merge(int x, int y){
 49     if(!x || !y) return x + y;
 50     if(e[x].prio < e[y].prio){
 51         pushdown(x);
 52         e[x].ch[1] = merge(e[x].ch[1], y);
 53         pushup(x);
 54         return x;
 55     } else {
 56         pushdown(y);
 57         e[y].ch[0] = merge(x, e[y].ch[0]);
 58         pushup(y);
 59         return y;
 60     }
 61 }
 62 inline void split(int now, int k, int &x, int &y){
 63     if(!now){
 64         x = y = 0;
 65         return;
 66     }
 67     pushdown(now);
 68     if(e[e[now].ch[0]].size < k){
 69         x = ++ tot; e[x] = e[now]; split(e[now].ch[1], k - e[e[now].ch[0]].size - 1, e[x].ch[1], y); pushup(x);
 70     } else {
 71         y = ++ tot; e[y] = e[now]; split(e[now].ch[0], k, x, e[y].ch[0]); pushup(y);
 72     }
 73 }inline void insert(int &root, int pos, int key){
 74     int x = 0, y = 0;
 75     split(root, pos, x, y);
 76     root = merge(x, merge(crepoint(key), y));
 77 }
 78 inline void erase(int &root, int pos){
 79     int x = 0, y = 0, z = 0;
 80     split(root, pos - 1, x, y);
 81     split(y, 1, y, z);
 82     root = merge(x, z);
 83 }
 84 inline void rever(int &root, int l, int r){
 85     int a = 0, b = 0, c = 0;
 86     split(root, l - 1, a, b);
 87     split(b, r - l + 1, b, c);
 88     e[b].rev ^= 1;
 89     root = merge(a, merge(b, c));
 90 }
 91 inline LL query(int &root, int l, int r){
 92     int a = 0, b = 0, c = 0;
 93     split(root, l - 1, a, b);
 94     split(b, r - l + 1, b, c);
 95     LL ans = e[b].sum;
 96     root = merge(a, merge(b, c));
 97     return ans;
 98 }
 99 int n;
100 LL lastans = 0;
101 int main(){
102     scanf("%d", &n);
103     for(Rint i = 1;i <= n;i ++){
104         int opt;
105         LL v, x, y;
106         scanf("%lld%d%lld", &v, &opt, &x);
107         x ^= lastans;
108         if(opt != 2) scanf("%lld", &y), y ^= lastans;
109         root[i] = root[v];
110         switch(opt){
111             case 1:
112                 insert(root[i], x, y);
113                 break;
114             case 2:
115                 erase(root[i], x);
116                 break;
117             case 3:
118                 rever(root[i], x, y);
119                 break;
120             case 4:
121                 printf("%lldn", lastans = query(root[i], x, y));
122         }
123     }
124 }
View Code

注意可持久化$fhq treap$中，对于$pushup$和$pushdown$是有一定区别的。

注意其中一些细微的差异，比如普通版本的split只要update(x)即可，而可持久化版本的要对r或l而非x调用update，因为x的孩子并没有被修改
另外，关于merge，理论上来讲merge里也应该克隆结点，但是本题并不需要，因为我们在调用merge之前总是会调用split，就已经把该克隆的结点克隆完了。 ———— GKxx dalao

【剩下的坑以后再补】

内容来源于网络如有侵权请私信删除
标签： 算法 数据结构
你还没有登录，请先登录或注册！
  • 还没有人评论，欢迎说说您的想法！

相关课程

英特尔® OpenVINO™工具套件初级课程
293613 0元 限免
基于 OpenVINO™ 的 AI 视觉应用进阶课
42088 0元 限免