HDU 4453：Looploop（Splay各种操作）***

http://acm.hdu.edu.cn/showproblem.php?pid=4453

题意：很多种操作：1、add x，将从光标起的 k2 个数全部加上 x；2、reverse，将从光标起的 k1 个数全部反转；3、insert x，在光标处的后一位插入值为 x 的数；4、delete，删除光标所在位置的数；5、move x，如果x是2，将光标右移，否则将光标左移。6、查询光标所在位置的值。

思路：在ACM中第一次写了6000+bytes的代码，把Splay几乎所有操作都汇集了，是一个很好的入门题目（虽然写了好久好久）。Splay是先插入两个结点，即0号节点下面的root，root的右孩子。Splay是一棵二叉树，满足左儿子比节点小，右儿子比节点大，中序遍历出来的结果就是原来数组的结果。所以我们在插入数组的时候，只要将数组插入到 ch[root][1] 的左孩子 ch[ch[root][1][0] (我的代码中的keytree) 的位置，那么就可以对这些数进行区间操作，并且这些数都是按顺序的。Splay就是利用这样的性质来完成各种操作的。注意因为一开始插入了两个点，所以实际上SplayTree的节点有 n + 2 个，数组中的元素标号从 2 开始到 n + 1。还要注意有 Insert 操作所以数组开大点，有一次TLE是因为这个。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <map>
#include <queue>
using namespace std;
#define N 1000010
#define INF 0x3f3f3f3f
#define lson ch[x][0]
#define rson ch[x][1]
#define keytree ch[ch[root][1]][0]
struct SplayTree
{
    int fa[N], ch[N][2], col[N], rev[N], sz[N], val[N], cnt, root, num[N];
    int n, tol, k1, k2;

    int NewNode(int w, int f, int kind)
    {
        cnt++;
        rev[cnt] = col[cnt] = ch[cnt][0] = ch[cnt][1] = 0;
        sz[cnt] = 1; val[cnt] = w; fa[cnt] = f;
        ch[f][kind] = cnt;
        return cnt;
    }

    void PushUp(int x)
    {
        sz[x] = sz[lson] + sz[rson] + 1;
    }

    void PushDown(int x)
    {
        if(rev[x]) {
            swap(lson, rson);
            if(lson) rev[lson] ^= 1;
            if(rson) rev[rson] ^= 1;
            rev[x] = 0;
        }
        if(col[x]) {
            if(lson) {
                col[lson] += col[x];
                val[lson] += col[x];
            }
            if(rson) {
                col[rson] += col[x];
                val[rson] += col[x];
            }
            col[x] = 0;
        }
    }

    void Build(int l, int r, int &x, int f, int kind)
    {
        if(r < l) return ;
        int m = (l + r) >> 1;
        x = NewNode(num[m], f, kind);
        Build(l, m - 1, ch[x][0], x, 0);
        Build(m + 1, r, ch[x][1], x, 1);
        PushUp(x);
    }

    void Init() // 初始化
    {
        cnt = root = 0;
        col[0] = fa[0] = rev[0] = val[0] = ch[0][0] = ch[0][1] = sz[0] = 0;
        root = NewNode(0, 0, 1); // 先开两个节点,然后把数组元素放进 keytree 的位置
        ch[root][1] = NewNode(0, root, 1);
        sz[root] = 2;
        Build(1, n, keytree, ch[root][1], 0);
        PushUp(ch[root][1]); PushUp(root);
    }

    void Rotate(int x, int kind)
    {
        int y = fa[x], z = fa[y];
        PushDown(y); PushDown(x);
        ch[y][!kind] = ch[x][kind];
        if(ch[x][kind]) fa[ch[x][kind]] = y;
        fa[y] = x; fa[x] = z;
        if(z) {
            if(ch[z][0] == y) ch[z][0] = x;
            else ch[z][1] = x;
        }
        ch[x][kind] = y;
        PushUp(y);
    }

    void Splay(int x, int goal)
    {
        while(fa[x] != goal) {
            int y = fa[x], z = fa[y];
            PushDown(z); PushDown(y); PushDown(x);
            int kind1 = ch[y][0] == x;
            int kind2 = ch[z][0] == y;
            if(z == goal) {
                Rotate(x, kind1);
            } else {
                if(kind1 == kind2) {
                    Rotate(y, kind2);
                } else {
                    Rotate(x, kind1);
                }
                Rotate(x, kind2);
            }
//            printf("%d, %d, %d
", x, fa[x], goal);
        }
        PushUp(x);
        if(goal == 0) root = x;
    }

    void RTO(int k, int goal) // 将第k个元素旋转到0号节点下面
    {
        int x = root;
        PushDown(x);
        while(1) {
            if(k <= sz[lson]) x = lson;
            else if(k == sz[lson] + 1) break;
            else {
                k -= sz[lson] + 1;
                x = rson;
            }
            PushDown(x);
        }
        Splay(x, goal);
    }

    void Insert(int val, int index)
    {
        RTO(index, 0); RTO(index + 1, root);
        keytree = NewNode(val, ch[root][1], 0);
        PushUp(ch[root][1]); PushUp(root);
//        Splay(keytree, 0);
    }

    int Delete(bool kind)
    {
        int w;
        if(kind) {
            RTO(1, 0); RTO(3, root);
            w = val[keytree];
            keytree = 0;
        } else {
            int ed = sz[root];
            RTO(ed - 2, 0); RTO(ed, root);
            w = val[keytree];
            keytree = 0;
        }
        PushUp(ch[root][1]); PushUp(root);
//        Splay(root, 0);
        return w;
    }

    void Move(int kind) // 光标移动, 如果向左移动就删除最后的元素插到最前面, 向右移动反之
    {
        int w;
        if(kind == 1) {
            w = Delete(0);
            Insert(w, 1);
        } else {
            w = Delete(1);
            Insert(w, sz[root] - 1);
        }
    }

    void Reverse()
    {
        RTO(1, 0);
//        Debug(root);
        RTO(k1 + 2, root);
//        puts("----------------");
//        Debug(root);
//        puts("----------------");
        rev[keytree] ^= 1;
//        swap(ch[keytree][0], ch[keytree][1]);
        PushUp(ch[root][1]); PushUp(root);
    }

    void Add(int w)
    {
        RTO(1, 0); RTO(k2 + 2, root);
//        printf("add
");
        col[keytree] += w;
        val[keytree] += w;
        PushUp(ch[root][1]); PushUp(root);
    }

    int Query() // 查询操作将要查询的数移动到根节点直接查询
    {
        RTO(2, 0);
//        printf("%d
", root);
        return val[root];
    }

    void Debug(int x)
    {
        if(lson) Debug(lson);
        printf("%d : %d, %d, %d, %d
", val[x], val[lson], val[rson], lson, rson);
        if(rson) Debug(rson);
    }
}splay;

int main()
{
    int q, cas = 1;
    while(~scanf("%d%d%d%d", &splay.n, &q, &splay.k1, &splay.k2), splay.n + q + splay.k1 + splay.k2) {
        for(int i = 1; i <= splay.n; i++) scanf("%d", &splay.num[i]);
        splay.Init();
        char s[20];
        printf("Case #%d:
", cas++);
        for(int i = 1; i <= q; i++) {
            scanf("%s", s);
            int x;
            if(s[0] == 'q') printf("%d
", splay.Query());
            else if(s[0] == 'a') {
                scanf("%d", &x);
                splay.Add(x);
            } else if(s[0] == 'r') {
                splay.Reverse();
            } else if(s[0] == 'i') {
                scanf("%d", &x);
                splay.Insert(x, 2);
            } else if(s[0] == 'd') {
                splay.Delete(1);
            } else if(s[0] == 'm') {
                scanf("%d", &x);
                splay.Move(x);
            }
//            splay.Debug(splay.root);
        }
    }
    return 0;
}