poj 3468
经典的区间修改和区间和查询，需要灵活运用差分和前缀和。
设A为原数组，A'为差分数组（A'i：=Ai-A[I-1]）。
那么，我们如果要求Ai，便可从A'1+...A'I得出，由此看来A=SA'（前缀和），
于是，我们想要快速知道Ai~j的和方法之一便是SAj-SAi，由上式可知，SA=SSA'（前缀和的前缀和）
SSA'i=SA’1+...SA'i=i*A‘1+(I-1)*A’2...=(i+1)*(A‘1+...A’i)-(1*A‘1+2*A’2+...I*A‘i)
我们为什么要把简单式子弄这么复杂，原因只有有一个——方便维护。
线段树支持区间修改加点查询或点修改加区间查询，但难以实现区间修改加区间查询，想不变splay之类的东西的话，就要充分利用转化思想，
上式的性质很优美，当你在[i,j]加上v时，由于差分，除A’I,A‘[J+1]外，其他点都不需要修改，每次查询时可以很方便求区间和再利用上式出解。
我们只需维护两个数列的线段树，A'、{i*A'I}。利用差分性质讨论，可以得出单点如何修改维护，实在不懂可以看我代码，或直接提问。
多说一句，我前面一个竟然就是zkw神牛。。。
var d:array[1..2,1..262144]of int64; a:array[0..100000]of int64; n,m,m1:longint; procedure change(k,x:longint;y:int64); begin x:=x+m1; while x<>0 do begin d[k,x]:=d[k,x]+y;x:=x>>1 end end; function ask(k,l,r:longint):int64; begin l:=l+m1-1;r:=r+m1+1;ask:=0; while not(l xor r=1) do begin if l and 1=0 then ask:=ask+d[k,l+1]; if r and 1=1 then ask:=ask+d[k,r-1]; l:=l>>1;r:=r>>1 end end; procedure origin; begin fillchar(d,sizeof(d),0); m1:=1; while m1<=n+2 do m1:=m1<<1;m1:=m1-1 end; procedure init; var l,r,ans1,ans2,x:int64; i:longint; z1,z2:char; begin readln(n,m); origin; for i:=1 to n do read(a[i]); for i:=1 to n do begin change(1,i,a[i]-a[i-1]);change(2,i,i*(a[i]-a[i-1])) end; readln; for i:=1 to m do begin read(z1,z2,l,r); if z1='Q' then begin l:=l-1; ans1:=ask(1,1,r)*(r+1);ans1:=ans1-ask(2,1,r); if l<>0 then begin ans2:=ask(1,1,l)*(l+1);ans2:=ans2-ask(2,1,l); end else ans2:=0; writeln(ans1-ans2) end else begin read(x); change(1,l,x);if r<n then change(1,r+1,-x); change(2,l,l*x);if r<n then change(2,r+1,-(r+1)*x) end; readln end end; begin init end.
写了个自顶向下的splay版
#include <cstdio> #include <cstdlib> #include <cstring> long long t[105000],sum[105000],ans,a[105000],size[105000]; int l[105000],r[105000],ll,rr,lr,rl,rs[105000],ls[105000],n,k,mid; void pushdown(int x) { if (0==x) return ; if (l[x]) sum[l[x]]=sum[l[x]]+t[x]*size[l[x]],t[l[x]]=t[l[x]]+t[x],a[l[x]]=a[l[x]]+t[x]; if (r[x]) sum[r[x]]=sum[r[x]]+t[x]*size[r[x]],t[r[x]]=t[r[x]]+t[x],a[r[x]]=a[r[x]]+t[x]; t[x]=0; } void updata(int x) {size[x]=size[l[x]]+size[r[x]]+1,sum[x]=sum[l[x]]+sum[r[x]]+a[x];} int left(int x,int y) {pushdown(x),r[y]=l[x],l[x]=y,updata(y);return x;} int right(int x,int y){pushdown(x),l[y]=r[x],r[x]=y,updata(y);return x;} void lconnect(int x) { if (0==x) return ; if (0==ll) {ll=lr=x,ls[ls[0]=1]=x;return ;} r[lr]=x,ls[++ls[0]]=lr=x; } void rconnect(int x) { if (0==x) return ; if (0==rr) {rr=rl=x,rs[rs[0]=1]=x;return ;} l[rl]=x,rs[++rs[0]]=rl=x; } void splay(int &mid,int x) { ll=rr=lr=rl=rs[0]=ls[0]=0; int y,i; for (;(mid!=x);) { pushdown(mid); if (x<mid) { if ((x<l[mid])&&(l[mid])) mid=right(l[mid],mid); rconnect(mid),y=l[mid],l[mid]=0,mid=y; } else { if ((r[mid]<x)&&(r[mid])) mid=left(r[mid],mid); lconnect(mid),y=r[mid],r[mid]=0,mid=y; } } pushdown(mid),pushdown(l[mid]),pushdown(r[mid]); if (l[mid]) lconnect(l[mid]),ls[0]--; if (r[mid]) rconnect(r[mid]),rs[0]--; for (i=ls[0];i>=1;i--) y=ls[i],updata(y); for (i=rs[0];i>=1;i--) y=rs[i],updata(y); l[mid]=ll,r[mid]=rr,updata(mid); } int build(int ll,int rr) { int mid=(ll+rr)>>1; if (mid+1<=rr) r[mid]=build(mid+1,rr); if (ll<=mid-1) l[mid]=build(ll,mid-1); updata(mid); return mid; } void init() { int i,al,ar; char ch; long long ak; scanf("%d%d\n",&n,&k);n+=2; for (i=2;i<=n-1;i++) scanf("%I64d",&a[i]);scanf("\n"); mid=(1+n)>>1,l[mid]=build(1,mid-1),r[mid]=build(mid+1,n),updata(mid); for (i=1;i<=k;i++) { scanf("%c",&ch); if ('Q'==ch){ scanf("%d%d\n",&al,&ar);al++,ar++; splay(mid,ar+1),splay(l[mid],al-1); ans=sum[r[l[mid]]]; printf("%I64d\n",ans); } else { scanf("%d%d%I64d\n",&al,&ar,&ak);al++,ar++; splay(mid,ar+1),splay(l[mid],al-1); al=r[l[mid]]; t[al]=t[al]+ak,sum[al]=sum[al]+ak*size[al],a[al]=a[al]+ak; updata(l[mid]),updata(mid); } } } int main() { freopen("simple.in","r",stdin); freopen("simple.out","w",stdout); init(); return 0; }