Solution - P4514 上帝造题的七分钟

Posted on Edited on

P4514 上帝造题的七分钟

idea:

二维树状数组，数学

解决：

如果是单点查询或者是单点询问那就是二维树状数组的裸题。

但是区间修改区间询问怎么办呢？

很显然，要做到区间修改，必须得差分。

而要区间查询，又得前缀和。

于是我们需要找到差分和前缀和之间的关系。

设原数组为 aa ，差分为 bb ，前缀和为 cc 。

显然有

∑i=1x∑j=1ybi,j=ax,y\sum_{i=1}^{x}\sum_{j=1}^{y} b_{i,j} = a_{x,y}

cx,y=∑i=1x∑j=1yai,jc_{x,y} = \sum_{i=1}^{x}\sum_{j=1}^{y} a_{i,j}

那么消去 aa ，得

cx,y=∑i=1x∑j=1y∑k=1i∑h=1jbk,hc_{x,y} = \sum_{i=1}^{x}\sum_{j=1}^{y}\sum_{k=1}^{i}\sum_{h=1}^{j}b_{k,h}

枚举 k,hk,h ，得

cx,y=∑k=1x∑h=1ybk,h∑i=kx∑j=hy1c_{x,y} = \sum_{k=1}^{x}\sum_{h=1}^{y} b_{k,h}\sum_{i=k}^{x}\sum_{j=h}^{y} 1

即

cx,y=∑k=1x∑h=1ybk,h(x+1−k)(y+1−h)c_{x,y} = \sum_{k=1}^{x}\sum_{h=1}^{y} b_{k,h}(x+1-k)(y+1-h)

打开，再稍微变换一下

cx,y=(x+1)(y+1)∑k=1x∑h=1ybk,hc_{x,y} = (x+1)(y+1)\sum_{k=1}^{x}\sum_{h=1}^{y} b_{k,h}

         −(y+1)∑k=1x∑h=1yk⋅bk,h\ \ \ \ \ \ \ \ \ - (y+1)\sum_{k=1}^{x}\sum_{h=1}^{y} k\cdot b_{k,h}

         −(x+1)∑k=1x∑h=1yh⋅bk,h\ \ \ \ \ \ \ \ \ - (x+1)\sum_{k=1}^{x}\sum_{h=1}^{y} h\cdot b_{k,h}

  +∑k=1x∑h=1yk⋅h⋅bk,h\ \ + \sum_{k=1}^{x}\sum_{h=1}^{y} k\cdot h\cdot b_{k,h}

开四个树状数组维护一下就好了。

美丽的 CODE:CODE:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include<bits/stdc++.h>
#define gc getchar
#define pc putchar
inline int read(){
	int x=0;bool p=1;char ch=gc();
	while (!isdigit(ch)) ch=='-'?p=0:0,ch=gc();
	while ( isdigit(ch)) x=(x<<1)+(x<<3)+(ch^'0'),ch=gc();
	return p?x:-x;
}
inline void print(int x){ if (x<0) pc('-'),x=-x;if (x>9) print(x/10);pc('0'+x%10); }
inline char get(){ char ch=gc();while (ch!='L'&&ch!='k'&&ch!=EOF) ch=gc();return ch; }
const int N=2051;
int T1[N][N],T2[N][N],T3[N][N],T4[N][N];
int n,m;
inline void I(int x,int y,int c){
	for (int i=x;i<=n;i+=i&-i){
		for (int j=y;j<=m;j+=j&-j){
			T1[i][j]+=c;
			T2[i][j]+=x*c;
			T3[i][j]+=y*c;
			T4[i][j]+=x*y*c;
		}
	}
}
inline int Q(int x,int y){
	int res=0;
	for (int i=x;i;i-=i&-i){
		for (int j=y;j;j-=j&-j){
			res+=(x+1)*(y+1)*T1[i][j];
			res-=(y+1)*T2[i][j];
			res-=(x+1)*T3[i][j];
			res+=T4[i][j];
		}
	}
	return res;
}
inline bool inmap(int a,int b){ return a>0&&a<=n&&b>0&&b<=m; }
signed main(){
	n=read(),m=read();
	char op;
	while ((op=get())!=EOF){
		if (op=='L'){
			int a=read(),b=read(),c=read(),d=read(),delta=read();
			if (inmap(a  ,b  )) I(a  ,b  , delta);
			if (inmap(a  ,d+1)) I(a  ,d+1,-delta);
			if (inmap(c+1,b  )) I(c+1,b  ,-delta);
			if (inmap(c+1,d+1)) I(c+1,d+1, delta);
		}else{
			int a=read(),b=read(),c=read(),d=read(),res=0;
			if (inmap(c  ,d  )) res+=Q(c  ,d  );
			if (inmap(c  ,b-1)) res-=Q(c  ,b-1);
			if (inmap(a-1,d  )) res-=Q(a-1,d  );
			if (inmap(a-1,b-1)) res+=Q(a-1,b-1);
			print(res),pc('\n');
		}
	}
	return 0;
}