【例题】

【题解】很明显对于50个物品分奇偶性状压即可，然后用异或维护。剩下的就是二维维护问题了。

简单的二维树状数组，能维护单点的修改和区间的求和。

比如如下代码

struct BIT_2D {
	ll c[M][M];
	inline void init() {
		memset(c, 0, sizeof(c));
	}
	inline void change(int x, int y, ll del) {
		for (int i=x; i<=n; i+=lowbit(i))
			for (int j=y; j<=n; j+=lowbit(j))
				c[i][j] ^= del;
	}
	inline ll sum(int x, int y) {
		ll ret=0;
		for (int i=x; i>0; i-=lowbit(i))
			for (int j=y; j>0; j-=lowbit(j))
				ret ^= c[i][j];
		return ret;
	}
};

相信大家如果学过一维树状数组的都能理解。

然后考虑如何拓展成二维情况。

我们先回顾下一维的时候是怎么做的：$b_i$表示$[i,n]$整体加了多少，然后通过维护$b_i$和b_i\times i$来维护区间修改与求和。

那么二维呢？一样的！

设$b_{i,j}$表示$(i,j)-(n,n)$这块矩形区域整体加了多少，那么设面积前缀和为$S'(x,y)$，则

$S'(x,y)=\sum_{i\leq x~and~j \leq y} a_{i,j} + \sum_{i\leq x~and~j\leq y}(b_{i,j} \times (x-i+1) \times(y-j+1))$。

展开可得

$S'(x,y)=\sum_{i\leq x~and~j \leq y} a_{i,j} + \sum_{i\leq x~and~j\leq y} b_{i,j} \times (x-i+1) \times(y-j+1) $

$~~~~~~~~~~~~~~~~- \sum_{i\leq x~and~j\leq y}(b_{i,j} \times i)\times (y+1)- \sum_{i\leq x~and~j\leq y}(b_{i,j} \times j) \times (x+1) $

我们发现，可以类似于一维树状数组维护四个值即可：$b_{i,j}$，$b_{i,j} \times j$，$b_{i,j} \times i$，$b_{i,j}\times i\times j$。

那么考虑对于区间$(x_1, y_1)$到$(x_2,y_2)$的查询，就可以写出如下式子：

$S = S'(x_2, y_2) - S'(x_2, y_1-1) - S'(x_1-1, y_2) + S'(x_1-1, y_1-1)$。

所以我们会写查询辣！

然后发现区间修改不会？？？

听说你不会？？？

再次考虑$b_{i,j}$的含义：表示$(i,j)-(n,n)$这块矩形区域整体加了多少。

那么对于区间$(x_1, y_1)$到$(x_2,y_2)$的增加，就可以转化成四个$b_{i,j}$的分别变化啦

啥？你问我哪四个？$b_{x2+1, y2+1}$，$b_{x1, y2+1}$，$b_{x2+1,y1}$，$b_{x1,y1}$。

啥？你问我怎么变化？四个树状数组相应变化，所以一共要改16次，查询也一样。

啥？你问我这题怎么做？加和减全替换成异或就行了！

贴代码

# include <stdio.h>
# include <algorithm>
# include <string.h>

# define lowbit(x)  ((x)&(-x))

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int M = 3010;
char opt[10];
int n, m;

struct BIT_2D {
	ll c[M][M];
	inline void init() {
		memset(c, 0, sizeof(c));
	}
	inline void change(int x, int y, ll del) {
		for (int i=x; i<=n; i+=lowbit(i))
			for (int j=y; j<=n; j+=lowbit(j))
				c[i][j] ^= del;
	}
	inline ll sum(int x, int y) {
		ll ret=0;
		for (int i=x; i>0; i-=lowbit(i))
			for (int j=y; j>0; j-=lowbit(j))
				ret ^= c[i][j];
		return ret;
	}
};

struct BIT2D {
	BIT_2D b, bi, bj, bij;
	void init() {
		b.init(); bij.init();
		bi.init(); bj.init();
	}
	inline void change(int posx, int posy, ll del) {
		b.change(posx, posy, del);
		if(posx&1) bi.change(posx, posy, del);
		if(posy&1) bj.change(posx, posy, del);
		if((posx*posy) & 1) bij.change(posx, posy, del);
	}
	inline void Change(int x1, int y1, int x2, int y2, ll del) {
		change(x2+1, y2+1, del);
		change(x2+1, y1, del);
		change(x1, y2+1, del);
		change(x1, y1, del);
	}
	inline ll sum(int posx, int posy) {
		ll ret = 0;
		if(((posx+1)*(posy+1))&1) ret ^= b.sum(posx, posy);
		if((posy+1)&1) ret ^= bi.sum(posx, posy);
		if((posx+1)&1) ret ^= bj.sum(posx, posy);
		ret ^= bij.sum(posx, posy);
		return ret;
	}
	inline ll Sum(int x1, int y1, int x2, int y2) {
		ll ret = 0;
		ret ^= sum(x2, y2);
		ret ^= sum(x1-1, y2);
		ret ^= sum(x2, y1-1);
		ret ^= sum(x1-1, y1-1);
		return ret;
	}
}T;

int main() {
	freopen("treasure.in", "r", stdin);
	freopen("treasure.out", "w", stdout);
	
	scanf("%d%d", &n, &m);
	
	T.init();
	
	while(m--) {
		scanf("%s", opt);
		if(opt[0] == 'P') {
			int X1, X2, Y1, Y2, k;
			ll res = 0;
			scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2);
			scanf("%d", &k);
			while(k--) {
				int a, b;
				scanf("%d%d", &a, &b);
				if(b&1) res ^= 1ll<<(a-1);
			}
			T.Change(X1, Y1, X2, Y2, res);
		} else {
			int X1, X2, Y1, Y2, op[50];
			scanf("%d%d%d%d", &X1, &Y1, &X2, &Y2);
			ll res = T.Sum(X1, Y1, X2, Y2);
			for (int i=0; i<50; ++i)
				op[i] = (res&(1ll<<i)) ? 2 : 1;
			printf("%d", op[0]);
			for (int i=1; i<50; ++i) 
				printf(" %d", op[i]);
			puts("");
		}
	}

	
	return 0;
}