BZOJ-3132 上帝造题的七分钟

n+e posted @ 2015年6月30日 16:45 in BZOJ with tags 差分 树状数组 , 1449 阅读

首先这道题所有操作都能转换为对$(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));
    }
}
---By n+e

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter