poj 3468 A Simple Problem with Integers

题目思路：splay，成段更新，求和。

[cpp] 
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<string> 
#include<queue> 
#include<algorithm> 
#include<vector> 
#include<stack> 
#include<list> 
#include<iostream> 
#include<map> 
using namespace std; 
#define inf 0x3f3f3f3f 
#define keytree (ch[ch[root][1]][0]) 
#define Max 110 
#define M 100100 
int max(int a,int b) 
{ 
    return a>b?a:b; 
} 
int min(int a,int b) 
{ 
    return a<b?a:b; 
} 
int n,m; 
int p[M],ch[M][2]; 
__int64 s[M],v[M],a[M],co[M],sum[M]; 
int root,top1; 
void visit(int x) 
{ 
    printf("x %d s %I64d v %I64d p %d ch0 %d ch1 %d co %I64d sum %I64d/n",x,s[x],v[x],p[x],ch[x][0],ch[x][1],co[x],sum[x]); 
    if(ch[x][0]) visit(ch[x][0]); 
    if(ch[x][1]) visit(ch[x][1]); 
} 
void debug() 
{ 
    printf("debug/n"); 
   // printf("sumroot %I64d",sum[root]); 
    visit(root); 
} 
void up(int x) 
{ 
    int l=ch[x][0],r=ch[x][1]; 
    s[x]=1+s[l]+s[r]; 
    sum[x]=sum[l]+sum[r]+v[x]; 
} 
void down(int x) 
{ 
    if(!co[x]) return; 
    int l=ch[x][0],r=ch[x][1]; 
    if(l) 
    { 
        sum[l]+=s[l]*co[x]; 
        co[l]+=co[x]; 
        v[l]+=co[x]; 
    } 
    if(r) 
    { 
        sum[r]+=s[r]*co[x]; 
        co[r]+=co[x]; 
        v[r]+=co[x]; 
    } 
      co[x]=0; 
} 
void newnode(int &x,__int64 val,int pre) 
{ 
    x=++top1; 
    s[x]=1; 
    sum[x]=v[x]=val; 
    co[x]=ch[x][0]=ch[x][1]=0; 
    p[x]=pre; 
} 
void build(int &x,int l,int r,int pre) 
{ 
    if(l>r) return; 
    int mid=(l+r)>>1; 
    newnode(x,a[mid],pre); 
    build(ch[x][0],l,mid-1,x); 
    build(ch[x][1],mid+1,r,x); 
    up(x); 
} 
void init() 
{ 
    top1=0; 
    p[0]=ch[0][0]=ch[0][1]=v[0]=sum[0]=co[0]=0; 
    newnode(root,-inf,0); 
    newnode(ch[root][1],inf,root); 
    s[root]=2; 
    build(keytree,1,n,ch[root][1]); 
    up(ch[root][1]); 
    up(root); 
   // debug(); 
} 
void rot(int x,int f) 
{ 
   // printf("f %d/n",f); 
    int y=p[x]; 
    p[ch[x][f]]=y; 
    ch[y][!f]=ch[x][f]; 
    p[x]=p[y]; 
    if(p[y]) ch[p[y]][ch[p[y]][1]==y]=x; 
    p[y]=x; 
    ch[x][f]=y; 
    up(y); 
} 
void splay(int x,int goal) 
{ 
    while(p[x]!=goal) 
    { 
        if(p[p[x]]==goal) rot(x,ch[p[x]][0]==x); 
        else 
        { 
            int y=p[x],f=ch[p[y]][0]==y; 
          //  printf("fff %d/n",f); 
            if(ch[y][f]==x) 
                rot(x,!f); 
            else 
                rot(y,f); 
            rot(x,f); 
        } 
    } 
    up(x); 
    if(!goal) root=x; 
} 
void rotto(int k,int goal) 
{ 
    int x=root; 
    down(x); 
    while(s[ch[x][0]]!=k) 
    { 
        if(s[ch[x][0]]>k) 
            x=ch[x][0]; 
        else 
        { 
            k-=s[ch[x][0]]+1; 
            x=ch[x][1]; 
        } 
        down(x); 
    } 
   // printf("find %d/n",x); 
    splay(x,goal); 
} 
void modify(int l,int r ,int data) 
{ 
    rotto(l-1,0); 
    rotto(r+1,root); 
    v[keytree]+=data; 
    sum[keytree]+=data*s[keytree]; 
    co[keytree]+=data; 
} 
void getsum(int l,int r) 
{ 
    rotto(l-1,0);//debug(); 
    rotto(r+1,root); 
    printf("%I64d/n",sum[keytree]); 
} 
int main() 
{ 
    int i,l,r,z; 
    char op[4]; 
    while(scanf("%d%d",&n,&m)!=EOF) 
    { 
        for(i=1;i<=n;i++) 
            scanf("%I64d",&a[i]); 
        init(); 
      //  printf("srot %I64d/n",sum[root]); 
        while(m--) 
        { 
            scanf("%s",op); 
            if(op[0]=='C') 
            { 
                scanf("%d%d%d",&l,&r,&z); 
                { 
                    modify(l,r,z); 
                } 
            } 
            else 
            { 
                scanf("%d%d",&l,&r); 
                getsum(l,r); 
            } 
        } 
    } 
    return 0; 
} 

作者：Wings_of_Liberty