[cpp]
/******************************************
數據結構：
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
#include
#include
#include
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
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
{
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]
r=ch[r][key[r]
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
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\n",Query(x,y));
else
Update(x,y);
}
}
return 0;
}
