题目地址:http://poj.org/problem?id=2155
题目:
t个测试样例, n*n的网格,q个询问
每次区间修改所做的操作:使区间内的数1变为0, 0变为1
输出每次询问的坐标点对应的值
解题思路:
一维/二维树状数组的讲解参见大佬博客:https://www.cnblogs.com/RabbitHu/p/BIT.html(不仅oi打得好,还是市状元ORZ)
二维树状数组模版题。
这里的区间修改可以转变成每次区间内的值都加1, 最后对2取模即可。
ac代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll maxn = 1005;
#define lowbit(x) ((x) & (-x))
int tree[maxn][maxn];
int T, n, q, x11, y11, x22, y22, x, y;
void update(int x, int y, int v)
{
for(int i = x; i < maxn; i += lowbit(i))
for(int j = y; j < maxn; j += lowbit(j))
tree[i][j] += v;
}
void range_update(int x1, int y1, int x2, int y2)
{
update(x1, y1, 1);
update(x1, y2 + 1, -1);
update(x2 + 1, y2 + 1, 1);
update(x2 + 1, y1, -1);
}
int getval(int x, int y)
{
int res = 0;
for(int i = x; i > 0; i -= lowbit(i))
for(int j = y; j > 0; j -= lowbit(j))
res += tree[i][j];
return res % 2;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
scanf("%d", &T);
for(int t = 1; t <= T; t++)
{
if(t != 1) printf("\n");
scanf("%d %d", &n, &q);
getchar();
memset(tree, 0, sizeof(tree));
for(int i = 1; i <= q; i++)
{
char op;
scanf("%c", &op);
// cout << "op:" << op << endl;
if(op == 'C')
{
scanf("%d %d %d %d", &x11, &y11, &x22, &y22);
getchar();
range_update(x11, y11, x22, y22);
}
else
{
scanf("%d %d", &x, &y);
getchar();
printf("%d\n", getval(x, y));
}
}
}
return 0;
}