再来一道Splay Tree的简单题，因为只用到两个基本操作，剪接和反转。虽说是简单题，可是我对细节稍有疏忽，所以我wa了几次。问题出在延迟标记的更新上，可能是半夜打代码的缘故，头脑有点不灵活，从而导致这种不容易debug出问题的错误，以后要多加注意这样的小问题！
AC代码：
View Code 1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 const int inf = 0x7f7f7f7f; 8 9 bool pnt; 10 struct Node { 11 int key, cnt; 12 bool rev; 13 Node *c[2], *p; 14 15 Node(int _key = 0, int _cnt = 0) { 16 cnt = _cnt; 17 key = _key; 18 rev = false; 19 c[0] = c[1] = p = NULL; 20 } 21 } *Null, *Root; 22 23 void up(Node *rt) { 24 rt->cnt = rt->c[0]->cnt + rt->c[1]->cnt + 1; 25 } 26 27 void down(Node *rt) { 28 if (rt->rev) { 29 Node *ls = rt->c[0], *rs = rt->c[1]; 30 31 if (ls != Null) { 32 swap(ls->c[0], ls->c[1]); 33 ls->rev = !ls->rev; 34 } 35 if (rs != Null) { 36 swap(rs->c[0], rs->c[1]); 37 rs->rev = !rs->rev; 38 } 39 rt->rev = false; 40 } 41 } 42 43 void rotate(Node *x, bool right) { 44 Node *y = x->p; 45 46 down(y); 47 down(x); 48 y->c[!right] = x->c[right]; 49 if (x->c[right] != Null) { 50 x->c[right]->p = y; 51 } 52 x->p = y->p; 53 if (y->p != Null) { 54 if (y->p->c[0] == y) y->p->c[0] = x; 55 else y->p->c[1] = x; 56 } 57 x->c[right] = y; 58 y->p = x; 59 60 up(y); 61 if (y == Root) Root = x; 62 } 63 64 void splay(Node *x, Node *f) { 65 down(x); 66 while (x->p != f) { 67 if (x->p->p == f) { 68 if (x->p->c[0] == x) rotate(x, 1); 69 else rotate(x, 0); 70 } else { 71 Node *y = x->p, *z = y->p; 72 73 if (z->c[0] == y) { 74 if (y->c[0] == x) { 75 rotate(y, 1); 76 rotate(x, 1); 77 } else { 78 rotate(x, 0); 79 rotate(x, 1); 80 } 81 } else { 82 if (y->c[0] == x) { 83 rotate(x, 1); 84 rotate(x, 0); 85 } else { 86 rotate(y, 0); 87 rotate(x, 0); 88 } 89 } 90 } 91 } 92 93 up(x); 94 } 95 96 void inTra(Node *rt) { 97 if (rt == Null) { 98 return ; 99 }100 down(rt);101 inTra(rt->c[0]);102 if (rt->key != inf){103 if (!pnt) pnt = true;104 else putchar(' ');105 printf("%d", rt->key);106 }107 inTra(rt->c[1]);108 }109 110 void initSplay() {111 Null = new Node();112 Root = new Node(inf, 1);113 114 Root->p = Root->c[0] = Null;115 Root->c[1] = new Node(inf, 1);116 Root->c[1]->p = Root;117 Root->c[1]->c[0] = Root->c[1]->c[1] = Null;118 up(Root);119 }120 121 void insSplay(int x) {122 Node *tmp = new Node(x, 1);123 124 tmp->c[1] = Root->c[1];125 Root->c[1]->p = tmp;126 Root->c[1] = tmp;127 tmp->p = Root;128 tmp->c[0] = Null;129 130 splay(tmp, Null);131 }132 133 Node *getNode(int pos) {134 Node *p = Root;135 136 pos++;137 while (true) {138 down(p);139 140 int cnt = p->c[0]->cnt;141 142 // printf("pos %d cnt %d\n", pos, cnt);143 if (pos == cnt + 1) {144 return p;145 } else if (pos <= cnt) {146 p = p->c[0];147 } else {148 pos -= cnt + 1;149 p = p->c[1];150 }151 }152 }153 154 void cutSeg(int l, int r, int pos) {155 Node *pl = getNode(l - 1);156 splay(pl, Null);157 Node *pr = getNode(r + 1);158 splay(pr, pl);159 160 // inTra(Root);161 // puts("!!!");162 163 // cut segment164 Node *tmp = pr->c[0];165 166 down(tmp);167 pr->c[0] = Null;168 splay(pr, Null);169 // insert segment170 // printf("pos %d\n", pos);171 // inTra(Root);172 // puts("~~~");173 pl = getNode(pos);174 splay(pl, Null);175 pr = getNode(pos + 1);176 splay(pr, pl);177 // puts("cut??");178 179 pr->c[0] = tmp;180 tmp->p = pr;181 splay(tmp, Null);182 }183 184 void reverse(int l, int r) {185 Node *pl = getNode(l - 1);186 splay(pl, Null);187 Node *pr = getNode(r + 1);188 splay(pr, pl);189 190 pr = pr->c[0];191 down(pr);192 pr->rev = true;193 swap(pr->c[0], pr->c[1]);194 splay(pr, Null);195 }196 197 void build(int n) {198 initSplay();199 for (int i = 1; i <= n; i++) {200 insSplay(i);201 }202 }203 204 void process(int m) {205 char buf[5];206 int l, r, pos;207 208 while (m--) {209 scanf("%s", buf);210 if (buf[0] == 'C') {211 scanf("%d%d%d", &l, &r, &pos);212 if (l > r) swap(l, r);213 cutSeg(l, r, pos);214 // puts("cut~");215 } else {216 scanf("%d%d", &l, &r);217 if (l > r) swap(l, r);218 reverse(l, r);219 // puts("flip~");220 }221 }222 }223 224 void delSplay(Node *rt) {225 if (rt == Null) {226 return ;227 } else {228 delSplay(rt->c[0]);229 delSplay(rt->c[1]);230 delete rt;231 }232 }233 234 int main() {235 int n, m;236 237 // freopen("in", "r", stdin);238 // freopen("out", "w", stdout);239 while (~scanf("%d%d", &n, &m) && (n >= 0 || m >= 0)) {240 build(n);241 // inTra(Root);242 // puts("built!");243 process(m);244 // puts("processed!");245 pnt = false;246 inTra(Root);247 puts("");248 delSplay(Root);249 delete Null;250 }251 252 return 0;253 }
——written by Lyon