题目链接：传送门
题目大意：有50种动物，给你n*n的矩阵，m次操作，P代表加入操作，在左上角 x1,y1 到右下角 x2,y2,的矩形范围内加入
种类为x，数量为y的动物。
Q代表询问操作，在左上角 x1,y1 到右下角 x2,y2，对于1~50种动物，如果数量之和为偶数，输出1，否则输出2。
题目思路：树状数组 区间异或，区间查询。
/*--------------------------------------------------分割线-------------------------------------------------------------*/
以下均考虑树状数组维护异或值
我们首先要知道树状数组都是向后更新，向前查询的。
首先考虑简单的问题
如果要求一维空间，单点修改，区间查询，那这个就直接像普通树状数组那样，修改和查询时把+改成^就行了。
如果要求一维空间，区间修改，区间查询，这时候就不能像普通树状数组那么改了。不信可以试试。:)
如果异或更新 [x,y] ^v
我们知道这样一个性质，假如对于位置 x，那么x+1，x+3，x+7...这些位置上的值是不会被V影响的。
因为更新时这些位置上的数异或V偶数次，值不会受影响。只有与 x 奇偶性相同的位置 x+2，x+4...才会被更新。
因此，我们可以开个二维数组tree[2][maxn]，只修改 x奇偶性对应的那一维，比如可以写成 x&1，偶数修改0，奇数修改1
查询时对应奇偶性查询。
本题要求二维空间，区间修改，区间查询，那么扩展一下，开4个数组即可。
然后我们把对应的50种动物状态压缩 1<<50，开LL tree[4][3001][3001],这样不会爆空间。
然后对于加入的动物数量，首先不用去管面积，直接用给的数量值（因为 偶*奇==偶，偶*偶==偶）
所以只要加入偶数数量就不用管，因为数量永远是偶数，而初始值0也是偶数，也就是对答案没影响。
对于加入奇数的情况，就必须老老实实加入（奇*奇==奇，奇*偶==偶），面积会对奇数情况有影响。
之后只需按上诉方法异或即可。
1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <algorithm> 6 #include <cstring> 7 #include <stack> 8 #include <cctype> 9 #include <queue> 10 #include <string> 11 #include <vector> 12 #include <set> 13 #include <map> 14 #include <climits> 15 #define lson rt<<1,l,mid 16 #define rson rt<<1|1,mid+1,r 17 #define fi first 18 #define se second 19 #define ping(x,y) ((x-y)*(x-y)) 20 #define mst(x,y) memset(x,y,sizeof(x)) 21 #define mcp(x,y) memcpy(x,y,sizeof(y)) 22 using namespace std; 23 #define gamma 0.5772156649015328606065120 24 #define mod 1000000007 25 #define inf 0x3f3f3f3f 26 #define N 1005050 27 #define maxn 3001 28 typedef pair<int,int> PII; 29 typedef long long LL; 30 31 int n,m,k,x,y,v; 32 LL tree[2][2][3001][3001]; 33 int x1,y1,x2,y2; 34 LL mon[50]; 35 void add(int x,int y,LL v){ 36 for(int i=x;i<=n;i+=(i&-i)) 37 for(int j=y;j<=n;j+=(j&-j)) 38 tree[x&1][y&1][i][j]^=v; 39 } 40 LL query(int x,int y){ 41 LL res=0; 42 for(int i=x;i;i-=(i&-i)) 43 for(int j=y;j;j-=(j&-j)) 44 res^=tree[x&1][y&1][i][j]; 45 return res; 46 } 47 int main(){ 48 //freopen("in.txt","r",stdin); 49 int i,j,group; 50 char ch; 51 while(scanf("%d%d",&n,&m)!=EOF){ 52 mst(tree,0); 53 while(m--){ 54 scanf(" %c%d%d%d%d",&ch,&x1,&y1,&x2,&y2); 55 if(ch=='P'){ 56 mst(mon,0); 57 scanf("%d",&k); 58 while(k--){ 59 scanf("%d%d",&x,&y); 60 --x; 61 mon[x]+=y; 62 } 63 LL temp=0; 64 for(i=0; i<50; ++i){ 65 if(mon[i]&1) 66 temp|=(1ll<<i); 67 } 68 ++x2;++y2; 69 add(x1,y1,temp); 70 add(x2,y2,temp); 71 add(x1,y2,temp); 72 add(x2,y1,temp); 73 } 74 else{ 75 --x1,--y1; 76 LL temp=query(x1,y1)^query(x2,y2)^query(x1,y2)^query(x2,y1); 77 for(i=0;i<50;++i) 78 if(temp&(1ll<<i))printf("2 "); 79 else printf("1 "); 80 printf(" "); 81 } 82 } 83 } 84 return 0; 85 }