poj 2155 Matrix 二维树状数组

缘起

研究一下二维树状数组~ poj 2155 Matrix

【1】就是本题的一维版本.

分析

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
给你一个N*N的方阵A,A[1,...,N]*[1,...,N](2<=N<=1000),每个方阵元素不是0就是1,一开始全部是0,
然后给你两种操作
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= N, 1 <= y1 <= y2 <= N) 
表示将左上角的A[x1][y1]与右下角的A[x2,y2]组成的矩形的0变成1,1变成0
2. Q x y (1 <= x, y <= N) 就是询问A[x][y]等于多少
操作的数目T<=5万次,每遇到Q操作就要输出询问结果

【输入】
多样例. 第一行是样例数. 每个样例开始于N和T,然后T行, 每行都是上面说的指令.

【输出】
对每个Q指令, 输出结果

【样例输入】
1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1

【样例输出】
1
0
0
1

【限制】
3s

【来源】
poj月赛@楼教主

本题是经典的二维树状数组. 根据【2】我们知道树状数组是处理前缀和的有力工具.

回到本题, 其实每个元素最终到底是0还是1, 取决于它变化的次数. 而每次操作

1
C x1 y1 x2 y2

其实等价于, 将 A[x1,…N]*A[y1,…,N]的变换次数+1, 将A[x2+1,…,N]*A[y2+1,…,N]的变换次数-1（其实吧~ 因为本题仅仅考察奇偶性, 所以变换次数都+1也行）.然后将A[x2+1,..N]*A[y1,…,N]的变换次数+1，再将A[x1,…,N]*[y2+1,…,N]的变换次数+1, 共计四次树状数组更新操作.

令 a[x][y] 是 A[x,…,N]*[y,…,N]变换的次数. 而最终要回答的是 A[i][j], 所以只需要知道 a[1,…,i][1,..,j] 这i*j和元素的部分和. 而这不就是二维前缀和吗? 完全可以使用树状数组高效维护. 只不过是二维树状数组而已.

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
//#include "stdafx.h"
#include <stdio.h>
#include <ctype.h>
#include <string.h>
//#define LOCAL
const int maxn = 1005;
int n,t,b[maxn][maxn]; // b是a的树状数组, 但是a没必要显式的写出来

void read(int &x)
{
	x=0;
	int f = 1;
	char c = getchar();
	while(!isdigit(c))
	{
		if (c=='-')
		{
			f = -1;
		}
		c = getchar();
	}
	while(isdigit(c))
	{
		x = (x<<3)+(x<<1)+(c^48);
		c = getchar();
	}
	x*=f;
}

void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x = -x;
	}
	if (x>9)
	{
		write(x/10);
	}
	putchar(48+x%10);
}

inline int lowbit(int i)
{
	return i&-i;
}

void updata(int x,int y) // 二维树状数组的更新, 复杂度 O(logn*logn)
{
	for (int i = x;i<=n; i+=lowbit(i))
	{
		for (int j = y; j<=n; j+=lowbit(j))
		{
			b[i][j]^=1;
		}
	}
}

int query(int x, int y) // 二维树状数组的询问, 复杂度 O(logn*logn)
{
	int ans = 0;
	for (int i = x;i;i-=lowbit(i))
	{
		for (int j = y;j;j-=lowbit(j))
		{
			ans+=b[i][j];
		}
	}
	return ans&1;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	read(kase);
	while(kase--)
	{
		memset(b,0,sizeof(b));
		read(n), read(t);
		while(t--)
		{
			int x1,y1,x2,y2;
			char c = getchar();
			if (c=='C')
			{
				read(x1), read(y1), read(x2), read(y2);
				updata(x1,y1);
				updata(x2+1,y1);
				updata(x1, y2+1);
				updata(x2+1,y2+1);

			}
			else
			{
				read(x1), read(y1);
				write(query(x1,y1));
				puts("");
			}
		}
		if (kase)
		{
			puts("");
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 235ms
Memory 4236kB
Length 1434
Lang G++
Submitted 2019-10-22 13:01:44
Shared
RemoteRunId 20979763

参考

【1】https://yfsyfs.github.io/2019/10/22/hdu-1556-Color-the-ball-%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84/

【2】https://yfsyfs.github.io/2019/10/21/%E7%BA%BF%E6%AE%B5%E6%A0%91%E5%92%8C%E6%A0%91%E7%8A%B6%E6%95%B0%E7%BB%84%E4%B9%8B%E9%97%B4%E7%9A%84%E8%81%94%E7%B3%BB/