学步园

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;<br /> a:array[0..100000]of int64;<br /> n,m,m1:longint;<br /> procedure change(k,x:longint;y:int64);<br /> begin<br /> x:=x+m1;<br /> while x<>0 do begin<br /> d[k,x]:=d[k,x]+y;x:=x>>1<br /> end<br /> end;<br /> function ask(k,l,r:longint):int64;<br /> begin<br /> l:=l+m1-1;r:=r+m1+1;ask:=0;<br /> while not(l xor r=1) do begin<br /> if l and 1=0 then ask:=ask+d[k,l+1];<br /> if r and 1=1 then ask:=ask+d[k,r-1];<br /> l:=l>>1;r:=r>>1<br /> end<br /> end;<br /> procedure origin;<br /> begin<br /> fillchar(d,sizeof(d),0);<br /> m1:=1;<br /> while m1<=n+2 do m1:=m1<<1;m1:=m1-1<br /> end;<br /> procedure init;<br /> var l,r,ans1,ans2,x:int64;<br /> i:longint;<br /> z1,z2:char;<br /> begin<br /> readln(n,m);<br /> origin;<br /> for i:=1 to n do read(a[i]);<br /> for i:=1 to n do begin<br /> change(1,i,a[i]-a[i-1]);change(2,i,i*(a[i]-a[i-1]))<br /> end;<br /> readln;<br /> for i:=1 to m do begin<br /> read(z1,z2,l,r);<br /> if z1='Q' then begin<br /> l:=l-1;<br /> ans1:=ask(1,1,r)*(r+1);ans1:=ans1-ask(2,1,r);<br /> if l<>0 then begin<br /> ans2:=ask(1,1,l)*(l+1);ans2:=ans2-ask(2,1,l);<br /> end else ans2:=0;<br /> writeln(ans1-ans2)<br /> end<br /> else begin<br /> read(x);<br /> change(1,l,x);if r<n then change(1,r+1,-x);<br /> change(2,l,l*x);if r<n then change(2,r+1,-(r+1)*x)<br /> end;<br /> readln<br /> end<br /> end;<br /> begin<br /> init<br /> 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;
}