Description：

给一个 $n\times n$ 的矩阵，子矩阵异或，子矩阵求异或和。

$1\leqslant n\leqslant 1000$

Solution：

异或最重要的一条性质： $x\text{ xor }x=0$ 。

首先暴力用什么二维数据结构来搞肯定是可以的，但是有更优美的做法。

首先把子矩阵异或变成 $(x_1,y_1),(x_2+1,y_1),(x_1,y_2+1),(x_2+1,y_2+1)$ 四个点异或，这样 $(x,y)$ 的二维前缀和就是 $(x,y)$ 这个点的值，但是这样求和不好计算，分析一下发现有很多都会被消掉，计算一下会发现 $(x,y)$ 这个位置会被二次二维前缀和 $(x_0,y_0)$ 计算 $(x_0-x+1)\times(y_0-y+1)$ 次，也就是说只有 $(x_0-x+1)\times(y_0-y+1)$ 为奇数，也就是 $x$ 与 $x_0$ ， $y$ 与 $y_0$ 都同奇偶的时候才会产生这个点的值的贡献，于是我们根本不用二次二维前缀和，对于每个 $x$ 和 $y$ 的奇偶性维护共 $4$ 个二维树状数组就可以支持询问了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 1010

typedef long long ll;

struct BIT

{

	ll c[MAXN][MAXN];

	int lowbit(int x){return x & (-x);}

	void add(int x,int y,ll v)

	{

		for(int i = x;i <= n;i += lowbit(i))

			for(int j = y;j <= n;j += lowbit(j))

				c[i][j] ^= v;

		return;

	}

	ll query(int x,int y)

	{

		ll res = 0;

		for(int i = x;i >= 1;i -= lowbit(i))

			for(int j = y;j >= 1;j -= lowbit(j))

				res ^= c[i][j];

		return res;

	}

}s[2][2];

void add(int x,int y,ll k)

{

	s[x & 1][y & 1].add(x,y,k);

	return;

}

ll query(int x,int y)

{

	return s[x & 1][y & 1].query(x,y);

}

ll calc(int r1,int c1,int r2,int c2)

{

	ll a = query(r1 - 1,c1 - 1);

	ll b = query(r1 - 1,c2);

	ll c = query(r2,c1 - 1);

	ll d = query(r2,c2);

	return (a ^ b ^ c ^ d);

}

void change(int r1,int c1,int r2,int c2,ll k)

{

	add(r1,c1,k);

	add(r2 + 1,c1,k);

	add(r1,c2 + 1,k);

	add(r2 + 1,c2 + 1,k);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	int opt,r1,c1,r2,c2;

	ll x;

	for(int i = 1;i <= m;++i)

	{

		scanf("%d%d%d%d%d",&opt,&r1,&c1,&r2,&c2);

		if(opt == 1)printf("%d\n",calc(r1,c1,r2,c2));

		else

		{

			scanf("%lld",&x);

			change(r1,c1,r2,c2,x);

		}

	}

	return 0;

}