Splay解决区间问题[区间更新,区间求和]

/*http://poj.org/problem?id=3468*/
/*区间更新，区间求和*/
/*注意各种编码细节，特别是splay buildTree和 rotateTo*/
/*仔细体会与线段树解决区间问题的不同点，如结点记录的信息是不同的*/
/*lazy思想*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 111111;
class SplayTree{
    #define l(x) (ch[x][0])
    #define r(x) (ch[x][1])
    #define mid(x,y) (x+y)>>1
public:
    int ch[MAXN][2],pre[MAXN],sz[MAXN];
    long long sum[MAXN],add[MAXN],val[MAXN];
    int a[MAXN];
    int tot,root;
    void init(){
        memset(ch,0,sizeof(int)*MAXN*2);
        memset(pre,0,sizeof(int)*MAXN);
        memset(sz,0,sizeof(int)*MAXN);
        memset(sum,0,sizeof(long long)*MAXN);
        memset(add,0,sizeof(long long)*MAXN);
        memset(val,0,sizeof(long long)*MAXN);
        tot = root = 0;
    }
    void read(int n){
        a[1] = a[n+2] = 0;
        for(int i=2;i<=n+1;i++) scanf("%d",&a[i]);
    }
    void push_up(int rt){
        sum[rt] = sum[l(rt)]+sum[r(rt)]+val[rt];
        sz[rt] = sz[l(rt)]+sz[r(rt)]+1;
    }
    void push_down(int rt){
        if(add[rt]){
            if(l(rt)){
                val[l(rt)] += add[rt];
                add[l(rt)] += add[rt];
                sum[l(rt)] += add[rt]*sz[l(rt)];
            }
            if(r(rt)){
                val[r(rt)] += add[rt];
                add[r(rt)] += add[rt];
                sum[r(rt)] += add[rt]*sz[r(rt)];
            }
            add[rt] = 0;
        }
    }
    void rotate(int x,int f){
        int y = pre[x];
        push_down(x);
        push_down(y);
        ch[y][!f] = ch[x][f];
        if(ch[y][!f]) pre[ch[y][!f]] = y;
        push_up(y);
        if(pre[y]) ch[pre[y]][r(pre[y])==y] = x;
        pre[x] = pre[y];
        ch[x][f] = y;
        pre[y] = x;
    }
    void splay(int x,int goal){
        while(pre[x]!=goal){
            int y = pre[x],z = pre[pre[x]];
            if(z==goal){
                rotate(x,l(y)==x);
            }else{
                int f = l(z)==y;
                if(ch[y][!f]==x){
                    rotate(y,f); rotate(x,f);
                }else{
                    rotate(x,!f); rotate(x,f);
                }
            }
        }
        push_up(x);
        if(goal==0) root = x;
    }
    void rotateTo(int k,int goal){
        int x = root;
        while(1){
            push_down(x);
            if(k==(sz[l(x)]+1)) break;
            else if(k<(sz[l(x)]+1)) x = l(x);
            else{
                k -= sz[l(x)]+1;
                x = r(x);
            }
        }
        splay(x,goal);
    }
    void buildTree(int l,int r,int &rt,int f){
        if(l>r)return;
        int m = mid(l,r);
        rt = ++tot;
        pre[rt] = f;
        val[rt] = a[m];
        buildTree(l,m-1,l(rt),rt);
        buildTree(m+1,r,r(rt),rt);
        push_up(rt);
    }
    long long query(int l,int r){
        rotateTo(l-1,0);
        rotateTo(r+1,root);
        return sum[l(r(root))];
    }
    void update(int l,int r,int c){
        rotateTo(l-1,0);
        rotateTo(r+1,root);
        val[l(r(root))] += c;
        sum[l(r(root))] += c*sz[l(r(root))];
        add[l(r(root))] += c;
    }
}spt;
int main(){
    int n,q;
    while(scanf("%d%d",&n,&q)!=EOF){
        spt.init();
        spt.read(n);
        spt.buildTree(1,n+2,spt.root,0);
        char op[2]; int a,b,c;
        while(q--){
            scanf("%s%d%d",op,&a,&b);
            if(op[0]=='Q'){
                printf("%I64d\n",spt.query(a+1,b+1));
            }else{
                scanf("%d",&c);
                spt.update(a+1,b+1,c);
            }
        }
    }
    return 0;
}