【2018-国庆雅礼-NOIP-培训】-D3T1-u

发表于

题解：

有很多不同的方法，下面这个是其中一种。

..........
..a....... 
..aa...... 
..aaa..... 
..aaaa.... 
..bbbbc... 
..bbbbcc.. 
..bbbbccc.

比如要更新 $a$ 区域，可以先让 $a$、$b$ 、$c$ 同时加上 $s$，然后再分别减去 $b$、$c$ 的部分。 分成两个不同的二维前缀和维护即可。

代码：

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
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=1e3+10;
int n,q;
ll a[maxn][maxn],b[maxn][maxn],ans;

inline void add_a(int x,int y,int v){
	if(x<=n&&y<=n)
		a[x][y]+=v;
}
inline void add_b(int x,int y,int v){
	if(x<=n&&y<=n)
		b[x][y]+=v;
}

int main()
{
	scanf("%d%d",&n,&q);
	while(q--){
		int r,c,l,s;
		scanf("%d%d%d%d",&r,&c,&l,&s);
		add_a(r,c,s);
		add_a(r+l,c+l,-s);
		add_b(r+l,c,-s);
		add_b(r+l,c+l,s);
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j){
			if(i>1)
				a[i][j]+=a[i-1][j-1]+a[i-1][j]-a[i-2][j-1];
			else
				a[i][j]+=a[i-1][j-1]+a[i-1][j];
			b[i][j]+=b[i-1][j]+b[i][j-1]-b[i-1][j-1];
			ans^=a[i][j]+b[i][j];
		}
	printf("%lld\n",ans);
	return 0;
}