bestcoder #56 div 2 C Clarke and puzzle (nim游戏 树状数组)
比赛的时候没过．还以为是树状数组写残了． 但实际上是有自己不知道的东西． 这种博弈叫 nim游戏 所以这是一个二维的nim游戏． **nim游戏的性质是xor 和为0必败，否则必胜． xor和也有前缀和性质，所以可以用树状数组维护．
1/*************************************************************************
2 > File Name: code/bc/#56/r1003.cpp
3 > Author: 111qqz
4 > Email: rkz2013@126.com
5 > Created Time: 2015年09月22日 星期二 11时10分06秒
6 ************************************************************************/
7#include<iostream>
8#include<iomanip>
9#include<cstdio>
10#include<algorithm>
11#include<cmath>
12#include<cstring>
13#include<string>
14#include<map>
15#include<set>
16#include<queue>
17#include<vector>
18#include<stack>
19#include<cctype>
20#define y1 hust111qqz
21#define yn hez111qqz
22#define j1 cute111qqz
23#define ms(a,x) memset(a,x,sizeof(a))
24#define lr dying111qqz
25using namespace std;
26#define For(i, n) for (int i=0;i<int(n);++i)
27typedef long long LL;
28typedef double DB;
29const int inf = 0x3f3f3f3f;
30const int N=5E2+5;
31int c[N][N];
32int a[N][N];
33int n,m,q;
34int lowbit ( int x)
35{
36 return x&(-x);
37}
38void update (int x,int y,int delta)
39{
40 for ( int i = x ; i <= n ; i = i + lowbit(i))
41 {
42 for ( int j = y ; j <= m ; j = j + lowbit(j))
43 {
44 c[i][j]^=delta;
45 }
46 }
47}
48int sum( int x,int y)
49{
50 int res = 0;
51 for ( int i = x; i >= 1 ; i = i - lowbit(i))
52 {
53 for ( int j = y ; j >= 1 ; j = j - lowbit(j))
54 {
55 res ^= c[i][j];
56 }
57 }
58 return res;
59}
60int main()
61{
62 #ifndef ONLINE_JUDGE
63 freopen("in.txt","r",stdin);
64 #endif
65 int T;
66 scanf("%d",&T);
67 while (T--)
68 {
69 scanf("%d %d %d",&n,&m,&q);
70 for ( int i = 1 ; i <= n ; i++)
71 {
72 for ( int j = 1 ; j <= m ; j++)
73 {
74 scanf("%d",&a[i][j]);
75 update (i,j,a[i][j]);
76 }
77 }
78 for (int i = 0 ; i < q ; i++)
79 {
80 int opt;
81 scanf("%d",&opt);
82 if (opt==1)
83 {
84 int x1,x2,y1,y2;
85 scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
86 int tmp = sum(x2,y2)^sum(x2,y1-1)^sum(x1-1,y2)^sum(x1-1,y1-1);
87 if (tmp>0)
88 {
89 puts("Yes");
90 }
91 else
92 {
93 puts("No");
94 }
95 }
96 else
97 {
98 int x,y,z;
99 scanf("%d %d %d",&x,&y,&z);
100 update (x,y,a[x][y]); //清零
101 a[x][y] = z;
102 update (x,y,a[x][y]);
103 }
104 }
105 }
106 #ifndef ONLINE_JUDGE
107 fclose(stdin);
108 #endif
109 return 0;
110}