BZOJ-3132 上帝造题的七分钟
首先这道题所有操作都能转换为对$(1,1)$~$(x,y)$的矩形区域内的修改和询问。
对一个 $N\times M$ 的矩阵的差分:
对于每一个点 $(i,j)$ ,$a'_{i,j} = a_{i,j}-a_{i-1,j}-a_{i,j-1}+a_{i-1,j-1}$
然后就有 $a_{x,y}=\sum_{i=1}^x \sum_{j=1}^y a'_{i,j}$
我们再来一次离散积分
$$\begin{eqnarray}\\
\sum_{x=1}^N \sum_{y=1}^M a_{x,y} &=& \sum_{x=1}^N \sum_{y=1}^M \sum_{i=1}^x \sum_{j=1}^y a'_{i,j}\\
&=& \sum_{x=1}^N \sum_{y=1}^M (N+1-x)\cdot (M+1-y)\cdot a'_{i,j}\\
&=& \sum_{x=1}^N \sum_{y=1}^M [(N+1)\cdot(M+1)\cdot a'_{i,j}\\
& &-(N+1)\cdot y\cdot a'_{i,j}-(M+1)\cdot x\cdot a'_{i,j}+x\cdot y\cdot a'_{i,j}]\end{eqnarray}$$
于是对于每个点 $(i,j)$,维护4个值 $a'_{i,j},\ i\cdot a'_{i,j},\ j\cdot a'_{i,j},\ i\cdot j\cdot a'_{i,j}$
/************************************************************** Problem: 3132 User: wjy1998 Language: C++ Result: Accepted Time:10696 ms Memory:69744 kb ****************************************************************/ #include<cstdio> char ch,B[1<<15],*S=B,*T=B; #define getc() (S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++) int aa,bb;int F(){ while(ch=getc(),(ch<'0'||ch>'9')&&ch!='-');ch=='-'?aa=bb=0:(aa=ch-'0',bb=1); while(ch=getc(),ch>='0'&&ch<='9')aa=aa*10+ch-'0';return bb?aa:-aa; } #define N 2100 char op;int n,m,a,b,c,d,v; struct T{ int s[N][N]; void add(int x,int y,int v){ for(int i=x;i<=n;i+=i&-i) for(int j=y;j<=m;j+=j&-j)s[i][j]+=v; } int gs(int x,int y){ int f=0; for(int i=x;i;i-=i&-i) for(int j=y;j;j-=j&-j)f+=s[i][j]; return f; } }t1,ti,tj,tij; void upd(int x,int y,int v){ t1.add(x,y,v),ti.add(x,y,v*x),tj.add(x,y,v*y),tij.add(x,y,v*x*y); } int query(int x,int y){ return t1.gs(x,y)*(x+1)*(y+1)-ti.gs(x,y)*(y+1)-tj.gs(x,y)*(x+1)+tij.gs(x,y); } int main(){ for(n=F()+1,m=F()+1;;){ while(op=getc(),op!='L'&&op!='k')if(op==0)return 0; a=F(),b=F(),c=F(),d=F(); if(op=='L')v=F(),upd(a,b,v),upd(a,d+1,-v),upd(c+1,b,-v),upd(c+1,d+1,v); else printf("%d\n",query(a-1,b-1)-query(a-1,d)-query(c,b-1)+query(c,d)); } }