题目思路：splay，成段更新，求和。
[cpp] #include #include #include #include #include #include #include #include #include #include #include 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 } 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);