Description
红学姐和黄学长是好朋友。红学姐有一只宠物，叫魔法猪。黄学长也有一只宠物，叫小奇。有 n 个猪圈排成一排
，魔法猪藏在某个猪圈中。为了找到魔法猪，小奇会向你询问一些猪圈中猪的个数和。在询问的过程中，魔法猪可
能会释放魔法来改变这些猪圈。
共有 m 次操作。每次操作是以下三种之一。
Q x y 询问从左到右第 x 个猪圈到第 y 个猪圈中猪的个数和。
C x y 将从左到右第 x 个猪圈中猪的个数变为 y。
M x y 将从左到右第 x 个猪圈移动到第 y 个猪圈的位置，并将第 y 个猪圈到第 x-1 个猪圈全部右移一格。保证
x>y。保证任何时候每个猪圈中猪的数量在 0 至 1000000 之间。
Input
第一行包含两个整数 n，m,其值均小于等于10^5
第二行 n 个整数表示从左到右每个猪圈中猪的个数。
接下来 m 行每行一个操作。
Output
对于每个询问操作，输出一行一个整数表示答案。
由于卡空间，这里考虑平衡树维护分块以减小空间常数，若取块大小为B=O(logn)则不会增加时间复杂度
限制块大小为[B,2B-1]，但最后一块为[1,2B-1]，在插入删除时可能破坏这一性质，需要相应维护
插入：
若插入后块大小为2B，则将这个块分裂。
删除：
对最后一个块，若删除后块大小为0，则删去这一块。
对其余的块，若删除后块大小为B-1，则考虑下一个块：
若下一个块大小为B，则合并这两个块，
否则将下一个块的第一个元素移到当前块的末尾。
#include<cstdio>
#include<cstdlib>
const int B=,B2=B*,M=,N=;
typedef long long i64;
i64 _a;
#define lc c[0]
#define rc c[1]
struct node{
int v[B2];
node*c[];
i64 s2;
int sz,len,rnd,s1;
void init(int D){
lc=rc=;
sz=len=D;
rnd=rand();
s2=s1;
}
void read(int D){
init(D);
s1=;
for(int i=;i<len;++i)scanf("%d",v+i),s1+=v[i];
s2=s1;
}
void get(node*a){
init(B);
s1=;
for(int i=,*b=a->v+B;i<B;++i)s1+=v[i]=b[i];
a->s1-=s1,a->len=B;
s2=s1;
}
void up(){
sz=len,s2=s1;
if(lc)sz+=lc->sz,s2+=lc->s2;
if(rc)sz+=rc->sz,s2+=rc->s2;
}
void sum(int L,int R){
if(!this)return;
if(L<=&&R>=sz){
_a+=s2;
return;
}
int ls=lc?lc->sz:;
if(L<=ls)lc->sum(L,R),L=ls+;
L-=ls,R-=ls;
if(R>len)rc->sum(L-len,R-len),R=len;
if(L==&&R==len)_a+=s1;
else for(--L;L<R;++L)_a+=v[L];
}
void set(int w,int x){
int ls=lc?lc->sz:;
if(w<=ls)lc->set(w,x);
else if(w>ls+len)rc->set(w-ls-len,x);
else{
w-=ls+;
s1+=x-v[w];
v[w]=x;
}
up();
}
node*chk(int d){
if(c[d]&&c[d]->rnd>rnd){
node*u=c[d];
c[d]=u->c[d^];
u->c[d^]=this;
return up(),u->up(),u;
}
return up(),this;
}
node*del(int x);
node*ins(int x);
}ns[N/B+],*ss[N/B+],*rt,*tmp;
int n,m,sp=,flag,_pos;
node*mg(node*a,node*b){
if(!a)return b;
if(!b)return a;
if(a->rnd>b->rnd){
a->rc=mg(a->rc,b);
a->up();
return a;
}else{
b->lc=mg(a,b->lc);
b->up();
return b;
}
}
node*node::del(int w){
int ls=lc?lc->sz:;
if(w<=ls)return lc=lc->del(w),chk();
if(w>ls+len)return rc=rc->del(w-ls-len),chk();
if(flag&&len<=B){
flag=;
for(int i=len-;i>=;--i)v[i+B-]=v[i];
for(int i=;i<B-;++i)v[i]=tmp->v[i];
len+=B-,sz+=B-;
s1+=tmp->s1,s2+=tmp->s1;
ss[sp++]=tmp;
return this;
}
_a=v[w-ls-];
s1-=_a,s2-=_a;
for(int i=w-ls;i<len;++i)v[i-]=v[i];
--len,--sz;
if(flag){
tmp->s1+=tmp->v[B-]=_a;
tmp->init(B);
return lc=mg(lc,tmp),chk();
}
if(len<B){
if(!len)ss[sp++]=this;
else flag=,_pos=ls-w,tmp=this;
return mg(lc,rc);
}
return this;
}
node*node::ins(int w){
int ls=lc?lc->sz:;
if(w<=ls)return lc=lc->ins(w),chk();
if(w>ls+len+)return rc=rc->ins(w-ls-len),chk();
w-=ls+;
for(int i=len++;i>w;--i)v[i]=v[i-];
v[w]=_a;
s1+=_a,s2+=_a;
if(len<B2)return up(),this;
tmp=ss[--sp];
tmp->get(this);
return rc=mg(tmp,rc),chk();
}
int main(){
scanf("%d%d",&n,&m);
srand(n^m<<^);
for(int i=,mx=n/B+;i<mx;++i)ss[sp++]=ns+i;
for(int D=B*/,l=,r=D;l<=n;l+=D,r+=D){
if(r>n)r=n;
node*w=ss[--sp];
w->read(r-l+);
rt=mg(rt,w);
}
for(;m;--m){
char o;
int a,b;
scanf(" %c %d%d",&o,&a,&b);
if(o=='Q'-){
_a=;
rt->sum(a,b);
printf("%lld\n",_a);
}else if(o=='C'-){
rt->set(a,b);
}else{
flag=;
rt=rt->del(a);
if(flag){
_pos+=a+;
if(_pos<=n--tmp->len){
i64 a0=_a;
rt=rt->del(_pos);
_a=a0;
}else{
tmp->init(tmp->len);
rt=mg(rt,tmp);
}
}
rt=rt->ins(b);
}
}
return ;
}