データ構造-Spaly_Tree

/******************************************
    ：
Splay_Tree,   ;

  ：
              ;
        ,         ;
           x   ：
                x;
               x;
            ，         ;

  ：
               ;
              ,                (logn);

    ：
                 ;
           ,       ;
          ：
(1)Zig Zag(  x    y    )
(2)Zig-Zig Zag-Zag(  x    y     ， x y                          )
(3)Zig-Zag Zag-Zig(  x    y     ，x y                         )
            ;

  ：
         [l,r]，          、    ;
  l-1       (   Splay  )，  r+1           ;
               ,               ;
        ，                [l,r];
        [l,r]，      ，         ;

    ：
PKU3468(A Simple Problem with Integers)

    :
Q a b   ：    [a,b]  ;
C a b x :     [a,b]，       x;
*******************************************/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;

#define Key_value ch[ch[root][1]][0]//         

const int INF=0xffffff;
const int N=100010;
typedef long long LL;

int ch[N][2];//    (0    ，1    )
int pre[N];//   
int key[N];//   
int size[N];//    
int val[N];
int add[N];
int a[N];//    
LL sum[N];//     
int root;  //   
int tot;//    
int n,q;

void Push_Up(int u)//           
{
    size[u]=size[ch[u][0]]+size[ch[u][1]]+1;
    sum[u]=sum[ch[u][0]]+sum[ch[u][1]]+val[u]+add[u];
}

void Push_Down(int u)//            
{
    if(add[u])
    {
        val[u]+=add[u];
        add[ch[u][0]]+=add[u];
        add[ch[u][1]]+=add[u];
        sum[ch[u][0]]+=(LL)add[u]*size[ch[u][0]];
        sum[ch[u][1]]+=(LL)add[u]*size[ch[u][1]];
        add[u]=0;
    }
}

void New_Node(int &u,int f,int c)//      ，f    
{
    u=++tot;
    val[u]=sum[u]=c;
    pre[u]=f;
    size[u]=1;
    ch[u][1]=ch[u][0]=add[u]=0;
}

void Build_Tree(int &u,int l,int r,int f)//  ，       ，                
{
    if(l>r)
        return;
    int m=(l+r)>>1;
    New_Node(u,f,a[m]);
    if(l<m)
        Build_Tree(ch[u][0],l,m-1,u);
    if(r>m)
        Build_Tree(ch[u][1],m+1,r,u);
    Push_Up(u);
}

void Rotate(int x,int c)//    ，c=0     ，c=1     
{
    int y=pre[x];
    Push_Down(y);//   Y         （  Y   ）
    Push_Down(x);//  X       
    ch[y][!c]=ch[x][c];//  SBT，             
    pre[ch[x][c]]=y;
    pre[x]=pre[y];
    if(pre[y])//          ，              
    {
        ch[pre[x]][ch[pre[y]][1]==y]=x;
    }
    pre[y]=x;
    ch[x][c]=y;
    Push_Up(y);
}

void Splay(int x,int f)//Splay  ,    x    f   
{
    Push_Down(x);
    while(pre[x]!=f)
    {
        int y=pre[x];
        if(pre[y]==f)//        f，     
            Rotate(x,ch[y][0]==x);
        else
        {
            int z=pre[y];
            int g=(ch[z][0]==y);
            if(ch[y][g]==x)
                Rotate(x,!g),Rotate(x,g);//     
            else Rotate(y,g),Rotate(x,g);//     
        }
    }
    Push_Up(x);//      X  
    if(f==0)//     
    {
        root=x;
    }
}

void Rotate_Under(int k,int f)//  k      f  
{
    //         k   ，        f    
    int p=root;//      
    Push_Down(p);//      p    ，     
    while(size[ch[p][0]]!=k)//p       
    {
        if(k<size[ch[p][0]])//  k    p  ，   
        {
            p=ch[p][0];
        }
        else//     ,       ，        k 
        {
            k-=(size[ch[p][0]]+1);
            p=ch[p][1];
        }
        Push_Down(p);
    }
    Splay(p,f);//    
}

int Insert(int k)//    
{
    int r=root;
    while(ch[r][key[r]<k])
        r=ch[r][key[r]<k];
    New_Node(ch[r][k>key[r]],r,k);
    //             
    //Push_Up(r);
    Splay(ch[r][k>key[r]],0);
    return 1;
}

int Get_Pre(int x)//   ，         
{
    int tmp=ch[x][0];
    if(tmp==0)
    return INF;
    while(ch[tmp][1])
    {
    	tmp=ch[tmp][1];
    }
    return key[x]-key[tmp];
}

int Get_Next(int x)//   ，         
{
    int tmp=ch[x][1];
    if(tmp==0)
    return INF;
    while(ch[tmp][0])
    {
        tmp=ch[tmp][0];
    }
    return key[tmp]-key[x];
}

LL Query(int l,int r)//  [l,r]    
{
    Rotate_Under(l-1,0);
    Rotate_Under(r+1,root);
    return sum[Key_value];
}

void Update(int l,int r)//  
{
    int k;
    scanf("%d",&k);
    Rotate_Under(l-1,0);
    Rotate_Under(r+1,root);
    add[Key_value]+=k;
    sum[Key_value]+=size[Key_value]*k;
}

void Init()//   
{
    for(int i=0; i<n; i++)
        scanf("%d",&a[i]);
    ch[0][0]=ch[0][1]=pre[0]=size[0]=0;
    add[0]=sum[0]=0;
    root=tot=0;
    New_Node(root,0,-1);
    New_Node(ch[root][1],root,-1);   //         
    size[root]=2;
    Build_Tree(Key_value,0,n-1,ch[root][1]);  //         -1  
    Push_Up(ch[root][1]);
    Push_Up(root);
}

int main()
{
    //freopen("C:\\Users\\Administrator\\Desktop\\kd.txt","r",stdin);
    while(~scanf("%d%d",&n,&q))
    {
        Init();
        while(q--)
        {
            char op;
            scanf(" %c",&op);
            int x,y;
            scanf("%d%d",&x,&y);
            if(op=='Q')
                printf("%lld
",Query(x,y));
            else
                Update(x,y);
        }
    }
    return 0;
}