转啊转终于转出来了，然而我的模板跟陈竞潇学长的模板一模一样，还是太弱啊，第一次用指针。
#include<cstdio> #include<cstring> #include<algorithm> #define for1(i,a,b) for(int i=(a);i<=(b);++i) using namespace std; typedef long long ll; const int N=1E5+100; int n,m,data[N]; struct node{ node(); node *ch[2],*fa; ll d,sum,set,add[2]; int size; short vset; short pl() {return this==fa->ch[1];} void count(); void push(); void mark(ll,ll,short); }*null; node::node(){ch[0]=ch[1]=fa=null; size=vset=sum=add[0]=add[1]=0;} void node::mark(ll val,ll dd,short t){ if(this==null) return; if(!t){ set=val; sum=size*set; d=set; vset=1; add[0]=add[1]=0; }else{ add[0]+=val; add[1]+=dd; sum+=val*size; sum+=dd*size*(size-1)/2; d+=val+dd*(ch[0]->size); } } void node::push(){ if(this==null)return; if(vset){ ch[0]->mark(set,0,0); ch[1]->mark(set,0,0); vset=0; set=0; } if(add[0]||add[1]){ ch[0]->mark(add[0],add[1],1); ch[1]->mark(add[0]+add[1]*(ch[0]->size+1),add[1],1); add[0]=add[1]=0; } } void node::count(){ size=ch[0]->size+ch[1]->size+1; sum=ch[0]->sum+ch[1]->sum+d; } namespace Splay{ node *ROOT; node *build(int l=1,int r=n){ if (l>r) return null; int mid=(l+r)>>1; node *ro=new node; ro->d=data[mid]; ro->ch[0]=build(l,mid-1); ro->ch[1]=build(mid+1,r); ro->ch[0]->fa=ro; ro->ch[1]->fa=ro; ro->count(); return ro; } void Build(){ null=new node; *null=node(); ROOT=build(); } void rotate(node *k){ node *r=k->fa; if (k==null||r==null) return; r->push(); k->push(); int x=k->pl()^1;; r->ch[x^1]=k->ch[x]; r->ch[x^1]->fa=r; if (r->fa!=null) r->fa->ch[r->pl()]=k; else ROOT=k; k->fa=r->fa; r->fa=k; k->ch[x]=r; r->count(); k->count(); } void splay(node *r,node *tar=null){ for (;r->fa!=tar;rotate(r)) if (r->fa->fa!=tar)rotate(r->pl()==r->fa->pl()?r->fa:r); r->push(); } void insert(int x,int val){ node *r=ROOT; if (ROOT==null){ ROOT=new node; ROOT->d=val; ROOT->count(); return; } while (1) { r->push(); int c; if (r->ch[0]->size+1>=x) c=0; else c=1,x-=r->ch[0]->size+1; if (r->ch[c]==null){ r->ch[c]=new node; r->ch[c]->fa=r; r->ch[c]->d=val; splay(r->ch[c]); return; }else r=r->ch[c]; } } node *kth(int k){ node *r=ROOT; while (r!=null){ r->push(); if (r->ch[0]->size>=k) r=r->ch[0]; else if (r->ch[0]->size+1>=k) return r; else k-=r->ch[0]->size+1,r=r->ch[1]; } return null; } node *pack(int l,int r){ node *ln=kth(l-1),*rn=kth(r+1); if ((ln==null)&&(rn==null)) return ROOT; else if (ln==null){ splay(rn); return rn->ch[0]; }else if (rn==null){ splay(ln); return ln->ch[1]; }else{ splay(ln); splay(rn,ROOT); return rn->ch[0]; } } } int main(){ scanf("%d%d",&n,&m); for1(i,1,n)scanf("%d",&data[i]); Splay::Build(); int j,a,b,c; for1(i,1,m){ scanf("%d",&j); switch(j){ node *r; case 1: scanf("%d%d%d",&a,&b,&c); r=Splay::pack(a,b); r->mark(c,0,0); Splay::splay(r); break; case 2: scanf("%d%d%d",&a,&b,&c); r=Splay::pack(a,b); r->mark(c,c,1); Splay::splay(r); break; case 3: scanf("%d%d",&a,&b); Splay::insert(a,b); break; case 4: scanf("%d%d",&a,&b); r=Splay::pack(a,b); printf("%lld ",r->sum); break; } } return 0; }