【分析】 splay搞yeah
【代码】
//线段树板子(splay复习) #include<iostream> #include<cstring> #include<cstdio> #define ll long long #define M(a) memset(a,0,sizeof a) #define fo(i,j,k) for(i=j;i<=k;i++) using namespace std; const int mxn=100005; ll n,m,sz,root,k; int ch[mxn][2],f[mxn],size[mxn]; ll key[mxn],sum[mxn],add[mxn],a[mxn]; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();} while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar(); return x*f; } inline int get(int x) { if(ch[f[x]][1]==x) return 1;return 0; } inline void update(int x) { size[x]=size[ch[x][0]]+size[ch[x][1]]+1; sum[x]=sum[ch[x][0]]+sum[ch[x][1]]+key[x]; } inline void ADD(int x,ll ad) { add[x]+=ad,key[x]+=ad; sum[x]+=ad*size[x]; } inline void pushdown(int x) { if(x && add[x]) { if(ch[x][0]) ADD(ch[x][0],add[x]); if(ch[x][1]) ADD(ch[x][1],add[x]); add[x]=0; } } inline void rotate(int x) { pushdown(x); int fa=f[x],fafa=f[fa],which=get(x); ch[fa][which]=ch[x][which^1],f[ch[fa][which]]=fa; ch[x][which^1]=fa,f[fa]=x; f[x]=fafa; if(fafa) ch[fafa][ch[fafa][1]==fa?1:0]=x; update(fa),update(x); } inline void splay(int x,int lastfa) { for(int fa;(fa=f[x])!=lastfa;rotate(x)) if(f[fa]!=lastfa) rotate(get(x)==get(fa)?fa:x); if(!lastfa) root=x; } inline int number(int x) { int now=root; while(1) { pushdown(now); if(x<=size[ch[now][0]] && ch[now][0]) now=ch[now][0]; else { if(x==size[ch[now][0]]+1) return now; x=x-size[ch[now][0]]-1; now=ch[now][1]; } } } inline int build(int fa,int l,int r) { if(l>r) return 0; int now=++sz,mid=l+r>>1; f[now]=fa,key[now]=sum[now]=a[mid],size[now]=1; ch[now][0]=build(now,l,mid-1); ch[now][1]=build(now,mid+1,r); update(now); return now; } int main() { int i,j,x,y,opt; scanf("%lld%lld",&n,&m); fo(i,2,n+1) scanf("%lld",&a[i]); root=build(0,1,n+2); fo(i,1,m) { opt=read(); if(opt==1) { scanf("%d%d%lld",&x,&y,&k);x++,y++; x=number(x-1),y=number(y+1); splay(x,0),splay(y,x); ADD(ch[y][0],k); } if(opt==2) { scanf("%d%d",&x,&y);x++,y++; x=number(x-1),y=number(y+1); splay(x,0),splay(y,x); printf("%lld\n",sum[ch[y][0]]); } } return 0; }