hdu4453 伸展树基本题
题意：很多操作，具体题目中有图http://acm.hdu.edu.cn/showproblem.php?pid=4453
move光标操作，move1， move2， 我们假定伸展树的第一个点为光标的位置，那么假如光标向后移动，我们可以把第一个数删除然后插入到整个序列的最后，同理光标向前移动也差不多，其它操作都是很常见的操作。
伸展树敲的不多，花了一点时间调试，终于AC了。
现在正式比赛估计这种题都会被顺秒了吧，高手越来越多了。
#include <cstdio>#include <cstring>#include <algorithm>using namespace std;#define KT ch[ ch[root][1] ][0]#define L ch[x][0]#define R ch[x][1]const int maxn = 300005;int num[maxn], n, m;int k1, k2;typedef long long ll;struct splayTree { int ch[maxn][2], sz[maxn], pre[maxn]; int root, tot, all; // all：节点总数， tot：最大标号 int add[maxn], val[maxn]; bool flip[maxn]; //翻转标记 int sta[maxn], top; void rotate(int &x, int f) { int y = pre[x], z = pre[y]; down(y); down(x); ch[y][!f] = ch[x][f]; pre[ch[x][f]] = y; pre[x] = pre[y]; if(z) ch[z][ch[z][1] == y] = x; ch[x][f] = y; pre[y] = x; up(y); } void splay(int &x, int g) { down(x); while(pre[x] != g) { int y = pre[x], z = pre[y]; down(z); down(y); down(x); if(z == g) { rotate(x, ch[y][0] == x); } else { int f = (ch[z][0] == y); ch[y][!f] == x ? rotate(y, f) : rotate(x, !f); rotate(x, f); } } if(!g) root = x; up(x); } void rto(int k, int g) { int x = root; while(1) { down(x); if(sz[L] == k) break; if(sz[L] > k) x = L; else { k -= sz[L] + 1; x = R; } } splay(x, g); } void down(int x){ if(add[x]) { val[L] += add[x]; val[R] += add[x]; add[L] += add[x]; add[R] += add[x]; add[x] = 0; } if(flip[x]) { flip[L] ^= 1; flip[R] ^= 1; swap(L, R); flip[x] = 0; } } void up(int x) { sz[x] = sz[L] + sz[R] +1; } void build(int &x, int l, int r, int fa) { if(l > r) return; int m = (l+r) >> 1; newNode(x, num[m], fa); build(L, l, m-1, x); build(R, m+1, r, x); up(x); } void newNode(int &x, int v, int fa) { if(top) x = sta[top--];//内存回收 else x = ++tot; all++; pre[x] = fa; sz[x] = 1; L = R = 0; val[x] = v; add[x] = 0; flip[x] = 0; } void init(int n) { all = tot = top = 0; newNode(root, 0, 0); newNode(ch[root][1], 0, root); for(int i = 0; i < n; i++) scanf("%d", &num[i]); build(KT, 0, n-1, ch[root][1]); up(ch[root][1]); up(root); } ll erase(int k) { //删除第k个数 rto(k, 0); rto(k-1, root); sta[++top] = root; all--; ll ret = val[root]; int ls = ch[root][0], rs = ch[root][1]; root = ls; pre[ls] = 0; ch[ls][1] = rs; if(rs)pre[rs] = ls; up(root); return ret; } void insert(int k, int v) { //在第k个数后面插入一个数v rto(k, 0); int x; int rs = ch[root][1]; newNode(x, v, root); ch[root][1] = x; ch[x][1] = rs; if(rs) pre[ch[x][1]] = x; up(ch[root][1]); up(root); } void move1() { int v = erase(all-2); insert(0, v); } void move2() { int v = erase(1); insert(all-2, v); } void update(int l, int r, int v) { rto(l-1, 0); rto(r+1, root); val[KT] += v; add[KT] += v; up(ch[root][1]); up(root); } void reverse(int l, int r) { rto(l-1, 0); rto(r+1, root); flip[KT] ^= 1; up(ch[root][1]); up(root); } int query() { rto(1, 0); return val[root]; } void print(int x) { printf("node %d: ls=%d rs=%d lsz = %d rsz = %d val = %d\n", x, L, R, sz[L], sz[R], val[x]); if(L)print(L); if(R)print(R); } void debug() { printf("root = %d\n", root); print(root); }}spt;int main() { int ca = 1; while(~scanf("%d%d%d%d", &n, &m, &k1, &k2)) { if(!m && !n && !k1 && !k2) break; char op[111]; spt.init(n); // spt.debug(); printf("Case #%d:\n", ca++); while(m--) { scanf("%s", op); if(op[0] == 'q') { printf("%d\n", spt.query()); } if(op[0] == 'm') { int kd; scanf("%d", &kd); if(kd == 1) spt.move1(); else spt.move2(); } if(op[0] == 'i') { int v; scanf("%d", &v); spt.insert(1, v); } if(op[0] == 'd') spt.erase(1); if(op[0] == 'a') { int v; scanf("%d", &v); spt.update(1, k2, v); } if(op[0] == 'r') spt.reverse(1, k1); } } return 0;}/*5 100000 2 41 2 3 4 5*/