HDU5465/BestCoder Round #56 (div.2) 二维树状数组

Clarke and puzzle

问题描述

克拉克是一名人格分裂患者。某一天，有两个克拉克（aa和bb）在玩一个方格游戏。

这个方格是一个n*mn∗m的矩阵，每个格子里有一个数c_{i, j}ci,j。

aa想开挂，想知道如何打败bb。

他们要玩qq次游戏，每一次做一次操作：

1. 取出当中的一个子矩阵(x_1, y_1)-(x_2, y_2)(x1,y1)−(x2,y2)玩游戏。两个人轮流行动，每一次只能从这个子矩阵中的一个方格c_{i, j}ci,j中减掉一个的数d(1 \le d \le c_{i, j})d(1≤d≤ci,j)，当一个格子的数为00时则不能减。如果操作完后另一者无法操作，那么胜利。否则失败。现在aa作为先手，想知道是否存在一种方案使得自己胜利。

2. 将c_{i, j}ci,j的数改成bb

输入描述

第一行一个整数T(1 \le T \le 5)T(1≤T≤5)，表示数据的组数。

每组数据第一行为三个整数n, m, q(1 \le n, m \le 500, 1 \le q \le 2*10^5)n,m,q(1≤n,m≤500,1≤q≤2∗105)。

接下来是一个nn行mm列的矩阵，其中第ii行第jj列的数为c_{i, j}(0 \le c_{i, j} \le 10^9)ci,j(0≤ci,j≤109)。

接下来时qq行，第一个数为optopt。当opt=1opt=1时，后面接着四个整数，依次表示x_1, y_1, x_2, y_2(1 \le x_1 \le x_2 \le n, 1 \le y_1 \le y_2 \le m)x1,y1,x2,y2(1≤x1≤x2≤n,1≤y1≤y2≤m)，表示一个询问；当opt=2opt=2时，后面接着三个整数x, y, z(1 \le x \le n, 1 \le y \le m, 0 \le z \le 10^9)x,y,z(1≤x≤n,1≤y≤m,0≤z≤109)，表示将c_{x, y}cx,y更改为zz。

输出描述

对于每组数据，每个询问输出aa是否能胜利，如果能，输出YesYes，否则输出NoNo。

输入样例

输出样例

Yes

No

Hint

第一个询问：一开始aa可以在(1, 2)(1,2)的格子上减掉11，则接下来无论bb怎么选，都还剩一个11，所以aa胜利。

第二个询问：无论aa怎么选，都还剩下一个11，所以bb胜利。

题解：用一个二维bit维护区间异或和，比赛的时候想到了，套了模板没改好  日....

///

#include<iostream>

#include<cstdio>

#include<cstring>

#include<string>

#include<algorithm>

#include<queue>

#include<cmath>

#include<map>

#include<bitset>

#include<set>

#include<vector>

using namespace std ;

typedef long long ll;

#define mem(a) memset(a,0,sizeof(a))

#define meminf(a) memset(a,127,sizeof(a));

#define TS printf("111111\n");

#define FOR(i,a,b) for( int i=a;i<=b;i++)

#define FORJ(i,a,b) for(int i=a;i>=b;i--)

#define READ(a,b,c) scanf("%d%d%d",&a,&b,&c)

#define mod 1000000007

#define inf 100000

inline ll read()

{

    ll x=,f=;

    char ch=getchar();

    while(ch<''||ch>'')

    {

        if(ch=='-')f=-;

        ch=getchar();

    }

    while(ch>=''&&ch<='')

    {

        x=x*+ch-'';

        ch=getchar();

    }

    return x*f;

}

//****************************************

const int maxn = ;

int s[maxn][maxn],xx[maxn][maxn];

int n,m,op;

int lowbit(int x)

{

    return x&(-x);

}

void modify(int a,int b,int val)

{

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

    {

        for(int j=b; j<=m; j+=lowbit(j))

            s[i][j]^=val;

    }

}

int sum(int x,int y)

{

    int ans=;

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

    {

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

            ans^=s[i][j];

    }

    return ans;

}

int getsum(int x1,int y1,int x2,int y2)

{

    return sum(x2,y2)^sum(x1-,y2)^sum(x2,y1-)^sum(x1-,y1-);

}

int main()

{    int op;

    int T=read();

    while(T--)

    {

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

        FOR(i,,n)FOR(j,,m)s[i][j]=;

        FOR(i,,n)FOR(j,,m)scanf("%d",&xx[i][j]),modify(i,j,xx[i][j]);

        int order;

        int a,b,c,d;

        for(int i=; i<=op; i++)

        {

            scanf("%d",&order);

            if(order==)

            {

                scanf("%d%d%d",&a,&b,&c);

                modify(a,b,c^xx[a][b]);

                xx[a][b]=c;

            }

            else

            {

                scanf("%d%d%d%d",&a,&b,&c,&d);

                int ans = getsum(a,b,c,d);

                if(!ans)cout<<"No"<<endl;

                else cout<<"Yes"<<endl;

            }

        }

    }

    return ;

}

代码

HDU5465/BestCoder Round #56 (div.2) 二维树状数组

Clarke and puzzle