HDU 5465 Clarke and puzzle （二维树状数组维护区间异或）

忘是亡心i 2022-08-09 00:36 167阅读 0赞

题目链接：[http://acm.hdu.edu.cn/showproblem.php?pid=5465][http_acm.hdu.edu.cn_showproblem.php_pid_5465]

解题思路:  
因为要对大量的区间进行异或，所以考虑用二维树状数组就行维护。

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<queue>
    #include<algorithm>
    #include<stack>
    #include<cstring>
    #include<vector>
    #include<list>
    #include<set>
    #include<string>
    #include<map>
    using namespace std;
    int ma[510][510],n,m,q,original[510][510];
    void add(int x,int y,int t)
    {
        for(int i=x; i<=n; i+=(i&-i))
            for(int j=y; j<=m; j+=(j&-j))
            {
                ma[i][j]^=t;
            }
            return ;
    }
    
    int sum(int x,int y)
    {
        int xx=0;
        for(int i=x; i>0; i-=(i&-i))
            for(int j=y; j>0; j-=(j&-j))
            {
                xx^=ma[i][j];
            }
        return xx;
    }
    int main()
    {
        int _;
        cin>>_;
        while(_--)
        {
            memset(ma,0,sizeof(ma));
            memset(original,0,sizeof(original));
            scanf("%d%d%d",&n,&m,&q);
            for(int i=1; i<=n; i++)
                for(int j=1; j<=m; j++)
                {
                    scanf("%d",&original[i][j]);
                    add(i,j,original[i][j]);
                }
            for(int i=1;i<=q;i++)
            {
                int choose;
                scanf("%d",&choose);
                if(choose==1)
                {
                    int x1,x2,y1,y2;
                    scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
                    if(sum(x2,y2)^sum(x2,y1-1)^sum(x1-1,y2)^sum(x1-1,y1-1)) printf("Yes\n");
                    else printf("No\n");
                }
                else
                {
                    int x1,y1,change;
                    scanf("%d%d%d",&x1,&y1,&change);
                    add(x1,y1,original[x1][y1]^change);
                    original[x1][y1]=change;
                }
            }
        }
        return  0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_5465]: http://acm.hdu.edu.cn/showproblem.php?pid=5465