[Splay] POJ3468 A Simple Problem with Integers

一道經典的線段樹題目，被我拿來SPLAY練手了，。

熟悉下區間求和，lazy區間更新。

SPLAY的旋轉操作真心太強了，從AVL學習了旋轉之後迫不及待地學習了SPLAY。

SPLAY原本也是二叉樹，我們對SPLAY的層次結構并不關注，隻需要注意到任意旋轉操作不會改變中序周遊，于是就可以用來維護數列了。

有個技巧就是預先插入兩個無關節點，ROOT和ROOT->right_kid。之後把要操作的節點都插入到ROOT->right_kid的左子樹，這樣就可以確定整個區間都可以操作。

于是對[L,R]區間操作時就可以把L-1對應的節點旋轉到根，把R+1對應的節點旋轉成根的右兒子，是以對ROOT->right_kid的左子樹就是對應整個區間了。

需要注意的是無關節點要真正做到無關，比如我們要維護最小值，那麼這兩個節點的值要置為INF，否則統計到root可能會出錯。

#include<algorithm>
#include<cstdio>
#define lson(x) (kid[x][0])
#define rson(x) (kid[x][1])
#define ll long long int
using namespace std;
const int N = 100005;
int pre[N], size[N], kid[N][2];
ll data[N], sum[N], lazy[N];
int root, cnt;
void NewNode(int &x, int val, int f){
    x = ++cnt;
    pre[x] = f;
    size[x] = 1;
    data[x] = sum[x] = val;
    lazy[x] = lson(x) = rson(x) = 0;
}
void push_up(int x){
    size[x] = size[lson(x)] + size[rson(x)] + 1;
    sum[x] = sum[lson(x)] + sum[rson(x)] + data[x] + lazy[x];
}
void push_down(int x){
    ll &k = lazy[x];
    if(k){
        data[x] += k;
        lazy[lson(x)] += k;
        sum[lson(x)] += k*size[lson(x)];

        lazy[rson(x)] += k;
        sum[rson(x)] += k*size[rson(x)];
        k = 0;
    }
}
void Rotate(int x, int f){
    int y = pre[x];
    push_down(y); push_down(x);
    kid[y][!f] = kid[x][f];
    pre[kid[x][f]] = y;
    if(pre[y]) kid[pre[y]][ kid[pre[y]][1] == y] = x;
    pre[x] = pre[y];
    kid[x][f] = y;
    pre[y] = x;
    push_up(y); //這裡不必更新x
}
void Splay(int x, int goal){ //用兩個單旋代替雙旋偷懶orz, 其實還可以更加偷懶
    push_down(x);
    while(pre[x] != goal){
        if(pre[pre[x]] == goal){
            Rotate(x, kid[pre[x]][0] == x);
        }
        else{
            int y = pre[x], z = pre[y];
            int f = (kid[z][0] == y);
            if(kid[y][f] == x){
                Rotate(x, !f);
                Rotate(x, f);
            }
            else{
                Rotate(y, f);
                Rotate(x, f);
            }
        }
    }
    push_up(x);
    if(goal == 0) root = x;
}
void RotateTo(int k, int goal){
    int x = root;
    push_down(x);
    while(size[lson(x)] != k){
        if(k < size[lson(x)]){
            x = lson(x);
        }
        else{
            k -= (size[lson(x)]+1);
            x = rson(x);
        }
        push_down(x);
    }
    Splay(x, goal);
}
int n, q;
int a[N];
void build(int &x, int l, int r, int f){
    if(l > r) return;
    int m = (l+r) >> 1;
    NewNode(x, a[m], f);
    build(lson(x), l, m-1, x);
    build(rson(x), m+1, r, x);
    push_up(x);
}
void query(int l, int r){
    RotateTo(l-1, 0);
    RotateTo(r+1, root);
    printf("%lld\n", sum[lson(rson(root))]);
}
void update(int l, int r){
    ll tmp;
    scanf("%lld%*c", &tmp);
    RotateTo(l-1, 0);
    RotateTo(r+1, root);
    lazy[lson(rson(root))] += tmp;
    sum[lson(rson(root))] += tmp*size[lson(rson(root))];
}
int main(){
    char p;
    int n1, n2;
    while(scanf("%d %d%*c", &n, &q) != EOF){
        for(int i = 0; i < n; ++i) scanf("%d%*c", &a[i]);
        root = cnt = 0;
        pre[0] = kid[0][0] = kid[0][1] = size[0] = data[0] = lazy[0] = 0;
        sum[0] = 0;
        NewNode(root, -1, 0);  //這裡無關節點不會影響數列，因為操作數列時已經将數列旋轉到ROOT->right_kid的左子樹。
        NewNode(rson(root), -1, root);
        size[root] = 2;
        build(lson(rson(root)), 0, n-1,rson(root));
        push_up(rson(root));
        push_up(root);
        while(q--){
            scanf("%c %d %d%*c", &p, &n1, &n2);
            if(p == 'Q') query(n1, n2);
            else if(p == 'C') update(n1, n2);
        }
        
    }
}