HDU 5465 Clarke and puzzle

Problem Description

a and 

b, they are playing a game. 

There is a 

n∗m matrix, each grid of this matrix has a number 

ci,j. 

a wants to beat 

b every time, so 

a ask you for a help. 

There are 

q operations, each of them is belonging to one of the following two types: 

1. They play the game on a 

(x1,y1)−(x2,y2) sub matrix. They take turns operating. On any turn, the player can choose a grid which has a positive integer from the sub matrix and decrease it by a positive integer which less than or equal this grid's number. The player who can't operate is loser. 

a always operate first, he wants to know if he can win this game. 

2. Change 

ci,j to 

b. 

Input

T(1≤T≤5), the number of test cases. 

For each test case: 

The first line contains three integers 

n,m,q(1≤n,m≤500,1≤q≤2∗105) 

Then 

n∗m matrix follow, the 

i row 

j column is a integer 

ci,j(0≤ci,j≤109) 

Then 

q lines follow, the first number is 

opt. 

if 

opt=1, then 

4 integers 

x1,y1,x1,y2(1≤x1≤x2≤n,1≤y1≤y2≤m) follow, represent operation 

1. 

if 

opt=2, then 

3 integers 

i,j,b follow, represent operation 

2.

Output

1, print 

Yes if 

a can win this game, otherwise print 

No.

Sample Input

1

1 2 3

1 2

1 1 1 1 2

2 1 2 1

1 1 1 1 2

Sample Output

Yes

No

Hint:

The first enquiry: $a$ can decrease grid $(1, 2)$'s number by $1$. No matter what $b$ operate next, there is always one grid with number $1$ remaining . So, $a$ wins.

The second enquiry: No matter what $a$ operate, there is always one grid with number $1$ remaining. So, $b$ wins.

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
using namespace std;
typedef long long LL;
const int maxn = 505;
int T, n, m, q, cs, x, y, X, Y, z, a[maxn][maxn], f[maxn][maxn];

int main()
{
  scanf("%d", &T);
  while (T--)
  {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 1; i <= n; i++)
    {
      f[i][0] = 0;
      for (int j = 1; j <= m; j++)
      {
        scanf("%d", &a[i][j]);
        f[i][j] = a[i][j] ^ f[i][j - 1];
      }
    }
    while (q--)
    {
      scanf("%d", &cs);
      if (cs == 1)
      {
        scanf("%d%d%d%d", &x, &y, &X, &Y);
        int flag = 0;
        for (int i = x; i <= X; i++) flag ^= f[i][y - 1] ^ f[i][Y];
        if (flag) printf("Yes\n"); else printf("No\n");
      }
      else
      {
        scanf("%d%d%d", &x, &y, &z);
        a[x][y] = z;
        for (int i = y; i <= m; i++) f[x][i] = a[x][i] ^ f[x][i - 1];
      }
    }
  }
  return 0;
}