自己写的第一颗splay。
http://acm.hdu.edu.cn/showproblem.php?pid=3487
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 using namespace std; 5 const int maxn = 3e5 + 10; 6 int pre[maxn], ch[maxn][2], key[maxn], size[maxn]; 7 bool rev[maxn], ok; 8 int n, m, nodes; 9 int root; 10 char buf[15]; 11 12 void new_node(int &u, int fa, int value){ 13 u = ++nodes; 14 ch[u][0] = ch[u][1] = 0; 15 key[u] = value; 16 pre[u] = fa; 17 size[u] = size[ch[u][0]] = size[ch[u][1]] = 0; 18 rev[u] = 0; 19 } 20 21 void push_up(int u) { size[u] = 1 + size[ch[u][0]] + size[ch[u][1]]; } 22 23 void build(int l, int r, int &u, int fa){ 24 if(r < l) return; 25 int mid = (l + r) >> 1; 26 new_node(u, fa, mid); 27 build(l, mid - 1, ch[u][0], u); 28 build(mid + 1, r, ch[u][1], u); 29 push_up(u); 30 } 31 32 void push_down(int u){ 33 if(!size[u] || !rev[u]) return; 34 rev[ch[u][0]] ^= 1; 35 rev[ch[u][1]] ^= 1; 36 swap(ch[u][0], ch[u][1]); 37 rev[u] = 0; 38 } 39 40 void rotate(int u, int d){ 41 int y = pre[u]; 42 ch[y][!d] = ch[u][d]; 43 if(pre[y]) ch[pre[y]][ch[pre[y]][1] == y] = u; 44 pre[ch[u][d]] = y; 45 ch[u][d] = y; 46 pre[u] = pre[y]; 47 pre[y] = u; 48 push_up(y), push_up(u); 49 } 50 51 void splay(int u, int dest){ 52 while(pre[u] != dest){ 53 if(pre[pre[u]] == dest) { rotate(u, ch[pre[u]][0] == u); break; } 54 int y = pre[u]; 55 int d = ch[pre[u]][0] == u; 56 if(ch[pre[y]][d] == y) rotate(u, d), rotate(u, !d); 57 else rotate(y, d), rotate(u, d); 58 } 59 if(!dest) root = u; 60 } 61 62 int get_kth(int u, int k){ 63 push_down(u); 64 int tem = size[ch[u][0]]; 65 if(tem + 1 == k) return u; 66 return tem >= k ? get_kth(ch[u][0], k) : get_kth(ch[u][1], k - tem - 1); 67 } 68 69 void reverse(int a, int b){ 70 int x = get_kth(root, a); 71 int y = get_kth(root, b + 2); 72 splay(x, 0); 73 splay(y, root); 74 rev[ch[y][0]] ^= 1; 75 } 76 77 void cut(int a, int b, int c){ 78 int x = get_kth(root, a);//get address 79 int y = get_kth(root, b + 2); 80 splay(x, 0); 81 splay(y, root); 82 int tem = ch[y][0]; 83 ch[ch[root][1]][0] = 0; 84 push_up(ch[root][1]); 85 push_up(root);//maintain size, cut interval[a,b] 86 int z = get_kth(root, c + 1); 87 splay(z, 0); 88 int nex = get_kth(root, 2 + size[ch[root][0]]); 89 splay(nex, root); 90 pre[tem] = nex;//link 91 ch[nex][0] = tem; 92 push_up(nex); 93 push_up(root); 94 } 95 96 void print(int u){ 97 if(!size[u]) return; 98 push_down(u); 99 print(ch[u][0]); 100 if(key[u] >= 1 && key[u] <= n) ok ? putchar(' ') : ok ^= 1, printf("%d", key[u]); 101 print(ch[u][1]); 102 push_up(u); 103 } 104 105 int main(){ 106 freopen("in.txt", "r", stdin); 107 while(~scanf("%d%d", &n, &m) && (n + 1)){ 108 ok = nodes = 0; 109 pre[0] = ch[0][0] = ch[0][1] = size[0] = 0;//null node 110 build(0, n + 1, root, 0); 111 for(int i = 1, x, y, z; i <= m; i++){ 112 scanf("%s%d%d", buf, &x, &y); 113 if(buf[0] == 'C') scanf("%d", &z), cut(x, y, z); 114 else reverse(x, y); 115 } 116 print(root), putchar(' '); 117 } 118 return 0; 119 }