普通平衡树与文艺平衡树的splay代码

主要综合借鉴了yyb和马前卒两位大佬的。

  1 //普通平衡树
  2 #include <cstdio>
  3 #include <cctype>
  4 #include <cstring>
  5 #include <algorithm>
  6 #define R(x) scanf("%d", &x)
  7 #define ri readint()
  8 #define gc getchar()
  9 #define wi(x) printf("%d
", x)
 10 #define ls(x) T[x].ch[0]
 11 #define rs(x) T[x].ch[1]
 12 using namespace std;
 13 
 14 int readint() {
 15     int x = 0, s = 1, c = gc;
 16     while (c <= 32)    c = gc;
 17     if (c == '-')    s = -1, c = gc;
 18     for (; isdigit(c); c = gc)
 19         x = x * 10 + c - 48;
 20     return x * s;
 21 }
 22 
 23 struct node {
 24     int fa;
 25     int ch[2];
 26     int val, cnt;
 27     int size;
 28 };
 29 node T[100005];
 30 int tot, root;
 31 
 32 int lr(int x) {
 33     return x == rs(T[x].fa);
 34 }
 35 
 36 void Connect(int son, int fa, int way) {
 37     T[fa].ch[way] = son;
 38     T[son].fa = fa;
 39 }
 40 
 41 void push_up(int pos) {
 42     T[pos].size = T[ls(pos)].size + T[rs(pos)].size + T[pos].cnt;
 43 }
 44 
 45 void Rotate(int x) {
 46     int f = T[x].fa, gf = T[f].fa;
 47     int x_f = lr(x), f_gf = lr(f);
 48     Connect(T[x].ch[x_f^1], f, x_f);
 49     Connect(f, x, x_f^1);
 50     Connect(x, gf, f_gf);
 51     push_up(f);
 52     push_up(x);
 53 }
 54 
 55 void splay(int pos, int goal) {
 56     for (; T[pos].fa != goal; Rotate(pos)) {
 57         int f = T[pos].fa, gf = T[f].fa;
 58         if (gf != goal) {
 59             lr(f) ^ lr(pos) ? Rotate(pos) : Rotate(f);
 60         }
 61     }
 62     if (goal == 0)    root = pos;
 63 }
 64 
 65 void Insert(int x) {
 66     int pos = root, fa = 0;
 67     while (pos && T[pos].val != x) {
 68         fa = pos;
 69         pos = T[pos].ch[x > T[pos].val];
 70     }
 71     if (pos) {
 72         T[pos].cnt++;
 73     } else {
 74         pos = ++tot;
 75         if (fa)    T[fa].ch[x > T[fa].val] = pos;
 76         T[pos].ch[0] = T[pos].ch[1] = 0;
 77         T[pos].fa = fa;
 78         T[pos].val = x;
 79         T[pos].cnt = T[pos].size = 1;
 80     }
 81     splay(pos, 0);
 82 }
 83 
 84 int find(int x) {//数字val为x的位置
 85     int pos = root;
 86     if (!pos)    return 0;
 87     while (T[pos].ch[x > T[pos].val] && x != T[pos].val)
 88         pos = T[pos].ch[x > T[pos].val];
 89     splay(pos, 0);
 90     return pos;
 91 }
 92 
 93 int Next(int flag, int x) {//0为前驱，1为后继
 94     find(x);
 95     int pos = root;
 96     if (T[pos].val > x && flag)    return pos;
 97     if (T[pos].val < x && !flag)    return pos;
 98     pos = T[pos].ch[flag];
 99     while (T[pos].ch[flag^1]) {
100         pos = T[pos].ch[flag^1];
101     }
102     return pos;
103 }
104 
105 void Delet(int x) {//删除数字x
106     int pos = find(x);
107     if (!pos)    return;
108     if (T[pos].cnt > 1) {
109         T[pos].cnt--;
110         T[pos].size--;
111         return;
112     } else {
113         if (!ls(pos) && !rs(pos)) {
114             root = 0;
115             return;
116         } else if (ls(pos) && rs(pos)) {
117             int u = ls(pos);
118             while (rs(u))    u = rs(u);
119             splay(u, 0);
120             Connect(rs(pos), u, 1);
121             push_up(u);
122         } else {
123             if (ls(pos))    root = ls(pos);
124             else    root = rs(pos);
125             T[root].fa = 0;
126         }
127     }
128 }
129 
130 int Rank(int x) {//数字x的排名
131     find(x);
132     return T[ls(root)].size + 1;
133 }
134 
135 int Kth(int x) {//第x大的数
136     int pos = root;
137     if (T[pos].size < x)    return -1;
138     while (true) {
139         int lson = ls(pos);
140         if (x > T[lson].size + T[pos].cnt) {
141             x -= T[lson].size + T[pos].cnt;
142             pos = rs(pos);
143         } else {
144             if (x > T[lson].size)    return T[pos].val;//这个题返回的是值
145             pos = lson;
146         }
147     }
148 }
149 
150 int main() {
151     int n;
152     for (n = ri; n; n--) {
153         int op = ri, x = ri;
154         if (op == 1)    Insert(x);
155         else if (op == 2)    Delet(x);
156         else if (op == 3)    wi(Rank(x));
157         else if (op == 4)    wi(Kth(x));
158         else    wi(T[Next(op - 5, x)].val);    
159     }
160     return 0;
161 }

  1 //文艺平衡树
  2 #include <cstdio>
  3 #include <cctype>
  4 #include <iostream>
  5 #include <algorithm>
  6 #define ri readint()
  7 #define gc getchar()
  8 #define init(a, b) memset(a, b, sizeof(a))
  9 #define rep(i, a, b) for (int i = a; i <= b; i++)
 10 #define irep(i, a, b) for (int i = a; i >= b; i--)
 11 #define ls(x) T[x].ch[0]
 12 #define rs(x) T[x].ch[1]
 13 using namespace std;
 14 
 15 typedef double db;
 16 typedef long long ll;
 17 typedef unsigned long long ull;
 18 typedef pair<int, int> P;
 19 const int inf = 0x3f3f3f3f;
 20 const ll INF = 1e18;
 21 
 22 inline int readint() {
 23     int x = 0, s = 1, c = gc;
 24     while (!isdigit(c))    c = gc;
 25     if (c == '-')    s = -1, c = gc;
 26     for (; isdigit(c); c = gc)
 27         x = x * 10 + c - 48;
 28     return x * s;
 29 }
 30 
 31 const int maxn = 1e5 + 5;
 32 int n, m, root, tot;
 33 struct node {
 34     int fa, ch[2];
 35     int val, size, tag;
 36 };
 37 node T[maxn];
 38 
 39 int lr(int x) {
 40     return x == T[T[x].fa].ch[1];
 41 }
 42 
 43 void connect(int son, int fa, int way) {
 44     T[son].fa = fa;
 45     T[fa].ch[way] = son;
 46 }
 47 
 48 void push_down(int pos) {
 49     if (T[pos].tag) {
 50         T[ls(pos)].tag ^= 1;
 51         T[rs(pos)].tag ^= 1;
 52         T[pos].tag = 0;
 53         swap(ls(pos), rs(pos));
 54     }
 55 }
 56 
 57 void push_up(int pos) {
 58     T[pos].size = T[ls(pos)].size + T[rs(pos)].size + 1;
 59 }
 60 
 61 void rotate(int pos) {
 62     int f = T[pos].fa, gf = T[f].fa;
 63     int x_f = lr(pos), f_gf = lr(f);
 64     connect(T[pos].ch[x_f^1], f, x_f);
 65     connect(f, pos, x_f^1);
 66     connect(pos, gf, f_gf);
 67     push_up(f);
 68     push_up(pos);
 69 }
 70 
 71 void splay(int pos, int goal) {
 72     for (; T[pos].fa != goal; rotate(pos)) {
 73         int f = T[pos].fa, gf = T[f].fa;
 74         if (gf != goal)
 75             lr(pos) ^ lr(f) ? rotate(pos) : rotate(f);
 76     }
 77     if (!goal)    root = pos;
 78 }
 79 
 80 void insert(int x) {
 81     int pos = root, fa = 0;
 82     while (pos && T[pos].val != x) {
 83         fa = pos;
 84         pos = T[pos].ch[x > T[pos].val];
 85     }
 86     pos = ++tot;
 87     if (fa)    T[fa].ch[x > T[fa].val] = pos;
 88     T[pos].fa = fa;
 89     T[pos].ch[0] = T[pos].ch[1] = 0;
 90     T[pos].val = x;
 91     T[pos].size = 1;
 92     T[pos].tag = 0;
 93     splay(pos, 0);
 94 }
 95 
 96 int Kth(int x) {
 97     int pos = root;
 98     while (true) {
 99         push_down(pos);
100         int lson = ls(pos);
101         if (x > T[lson].size + 1) {
102             x -= T[lson].size + 1;
103             pos = rs(pos);
104         } else {
105             if (x > T[lson].size)    return pos;
106             pos = lson;
107         }
108     }
109 }
110 
111 void work(int l, int r) {
112     l = Kth(l), r = Kth(r + 2);
113     splay(l, 0), splay(r, l);
114     int pos = rs(root);
115     pos = ls(pos);
116     T[pos].tag ^= 1;
117 }
118 
119 void dfs(int cur) {
120     push_down(cur);
121     if (T[cur].ch[0])    dfs(T[cur].ch[0]);
122     if (T[cur].val != -inf && T[cur].val != inf)
123         printf("%d ", T[cur].val);
124     if (T[cur].ch[1])    dfs(T[cur].ch[1]);
125 }
126 
127 int main() {
128     n = ri, m = ri;
129     insert(inf), insert(-inf);
130     rep(i, 1, n)    insert(i);
131     while (m--) {
132         int l = ri, r = ri;
133         work(l, r);
134     }
135     dfs(root);
136     return 0;
137 }