原题链接:http://www.lydsy.com/JudgeOnline/problem.php?id=1269
伸展树的运用,如下:
1 #include<cstdio> 2 #include<cstdlib> 3 #include<cstring> 4 #include<iostream> 5 #include<algorithm> 6 using std::swap; 7 const int Max_N = 3000010; 8 struct Node{ 9 char chr; 10 int s; 11 bool rev; 12 Node *pre, *ch[2]; 13 inline void 14 set(char _chr = ' ', int _s = 0, Node *p = NULL){ 15 chr = _chr, s = _s, rev = 0; 16 pre = ch[0] = ch[1] = p; 17 } 18 inline void push_up(){ 19 s = ch[0]->s + ch[1]->s + 1; 20 } 21 inline void update(){ 22 rev ^= 1; 23 swap(ch[0], ch[1]); 24 } 25 inline void push_down(){ 26 if (rev != 0){ 27 rev ^= 1; 28 ch[0]->update(); 29 ch[1]->update(); 30 } 31 } 32 }; 33 struct SplayTree{ 34 char buf[Max_N]; 35 Node *tail, *root, *null; 36 Node stack[Max_N], *store[Max_N]; 37 int top, pos; 38 void init(){ 39 top = 0, pos = 0; 40 tail = &stack[0]; 41 null = tail++; 42 null->set(); 43 root = newNode(' '); 44 root->ch[1] = newNode(' '); 45 root->ch[1]->pre = root; 46 root->ch[1]->push_up(); 47 root->push_up(); 48 } 49 inline Node *newNode(char chr){ 50 Node *p = null; 51 if (!top) p = tail++; 52 else p = store[--top]; 53 p->set(chr, 1, null); 54 return p; 55 } 56 inline void rotate(Node *x, int c){ 57 Node *y = x->pre; 58 y->push_down(), x->push_down(); 59 y->ch[!c] = x->ch[c]; 60 x->pre = y->pre; 61 if (x->ch[c] != null) x->ch[c]->pre = y; 62 if (y->pre != null) y->pre->ch[y->pre->ch[0] != y] = x; 63 x->ch[c] = y; 64 y->pre = x; 65 y->push_up(); 66 if (y == root) root = x; 67 } 68 inline void splay(Node *x, Node *f){ 69 if (x == root) return; 70 for (; x->pre != f; x->push_down()){ 71 if (x->pre->pre == f){ 72 rotate(x, x->pre->ch[0] == x); 73 } else { 74 Node *y = x->pre, *z = y->pre; 75 if (z->ch[0] == y){ 76 if (y->ch[0] == x) 77 rotate(y, 1), rotate(x, 1); 78 else rotate(x, 0), rotate(x, 1); 79 } else { 80 if (y->ch[1] == x) 81 rotate(y, 0), rotate(x, 0); 82 else rotate(x, 1), rotate(x, 0); 83 } 84 } 85 } 86 x->push_up(); 87 } 88 inline Node *built(int l, int r){ 89 if (l > r) return null; 90 int mid = (l + r) >> 1; 91 Node *p = newNode(buf[mid]); 92 p->ch[0] = built(l, mid - 1); 93 if (p->ch[0] != null) p->ch[0]->pre = p; 94 p->ch[1] = built(mid + 1, r); 95 if (p->ch[1] != null) p->ch[1]->pre = p; 96 p->push_up(); 97 return p; 98 } 99 inline void recycle(Node *x){ 100 if (x != null){ 101 recycle(x->ch[0]); 102 store[top++] = x; 103 recycle(x->ch[1]); 104 } 105 } 106 inline Node *select(Node *x, int k){ 107 for (int t = 0; x != null;){ 108 x->push_down(); 109 t = x->ch[0]->s; 110 if (k == t + 1) break; 111 else if (k <= t) x = x->ch[0]; 112 else k -= t + 1, x = x->ch[1]; 113 } 114 return x; 115 } 116 inline void get_range(int x, int y){ 117 splay(select(root, x + 1), null); 118 splay(select(root, y + 2), root); 119 } 120 inline void Gets(char *s){ 121 char c; 122 while (c = getchar(), c != ' ') *s++ = c; 123 *s = '