2016-09-27

HDU 5892 Resident Evil【二维树状数组】

题目链接:

http://acm.hdu.edu.cn/showproblem.php?pid=5892

题意：

给定$n \times n$的矩阵，初始全为0，有50种怪物，$m$个操作，两种操作，一是子矩阵中的每个方格中都放入给定数量的$k$种怪物，二是查询子矩阵中$50$种怪物数量的奇偶。
数据规模：$0 \le n\le 3000, 1 \le m \le 100000, 1 \le k \le 50$

分析：

最直接的想法是直接拿$50$个二维树状数组（4维），然后分别更新分别查询，算了一下果断T，
转化一下，由于我们只在乎每种怪物数量的奇偶，只有$50$个，正好可以状压一下，将他们的奇偶情况压成一个最大为$2^{50}$的数，用$1$表示奇数，$0$表示偶数，每个方格都保存$50$种怪物的奇偶情况。增加的怪物数量也压成一个数，那么对于一个方格来说两个数异或一下即可。
因为每次更新都是子矩阵中所有元素都加上相应个数，那么即转化成二维数组解决区间修改区间查询问题了= = ，然后就是套路了。【感觉自己最近做的都是模板题QAQ

代码:


/*************************************************************************
    > File Name: 5892.cpp
    > Author: jiangyuzhu
    > Mail: 834138558@qq.com 
    > Created Time: 2016/9/24 11:12:42
 ************************************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
const int maxn = 3e3 + 5;
typedef long long ll;
ll bit[2][2][maxn][maxn];
int n;
void Add(int x, int y, ll val) 
{
	for (int i = x; i <= n; i += i & (-i)) {
		for (int j = y; j <= n; j += j & (-j)){
			bit[x & 1][y & 1][i][j] ^= val;
		}
	}
}
ll Query(int x, int y)
{
	ll res = 0;
	for(int i = x; i; i -= i & (-i)){
		for(int j = y; j; j -= j & (-j)){
			res ^= bit[x & 1][y & 1][i][j];
		}
	}
	return res;
}
char s[10 + 5];
int main (void)
{
	int m;scanf("%d%d", &n, &m);
	int a, b, c, d;
	int k;
	int x, y;
	memset(bit, 0 ,sizeof(bit));
	for(int i = 0; i < m; ++i){
		scanf("%s", s);
		if(s[0] == 'P'){
			ll dt = 0;
			scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
			for(int j = 0; j < k; ++j){
				scanf("%d%d", &x, &y);
				if(y & 1) dt ^= 1ll << (x - 1);
			}
			Add(a, b, dt);
			Add(a, d + 1, dt); 
			Add(c + 1, b, dt);
			Add(c + 1, d + 1, dt);
		}else{
			scanf("%d%d%d%d", &a, &b, &c, &d);
			ll res = Query(c, d) ^ Query(a - 1, d) ^ Query(c, b - 1) ^ Query(a - 1, b - 1);
			for(int i = 0; i < 50; i++){
				if((res >> i) & 1) printf("2 ");
				else printf("1 ");
			}
			puts("");
		}
	}
	return 0;
}