神一般的二维区间更新，运用二维树状数组会有神奇的效果。更改四个角实现区间更改的效果实在是太神奇了。。
|
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 |
#pragma warning(disable:4996)#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<vector>#include<cmath>#define maxn 1000using
namespace std;int
bit[maxn + 50][maxn + 50];int
n;void
inc(int
i, int
j,int m){ for
(; i <= n; i += i&(-i)){ for
(int tmpj = j; tmpj <= n; tmpj += (tmpj&(-tmpj))) bit[i][tmpj] += m; }}int
get(int
i, int
j){ int
sum = 0; for
(; i > 0; i -= i&-i){ for
(int tmpj = j; tmpj > 0; tmpj -= tmpj&-tmpj) sum += bit[i][tmpj]; } return
sum;}int
q;int
main(){ int
T; cin >> T; while
(T--) { memset(bit, 0, sizeof(bit)); scanf("%d%d", &n, &q); char
str[3]; int
x1, y1, x2, y2; for
(int i = 0; i < q; i++) { scanf("%s",str); if
(str[0] == ‘C‘){ scanf("%d%d%d%d", &x1, &y1, &x2, &y2); x2++; y2++; inc(x1, y1,1); inc(x2, y2,1); inc(x1, y2,-1); inc(x2, y1,-1); } else{ scanf("%d%d", &x1, &y1); printf("%d\n", get(x1, y1) & 1); } } if
(T) puts(""); } return
0;} |
原文：http://www.cnblogs.com/chanme/p/3554580.html