CDOJ1601 - 二维树状数组（2017 UESTC Training for Data Structures）

╰半橙微兮° 2022-06-13 09:19 95阅读 0赞

**传送门：[CDOJ1601][]**

**题目思路：**

题目可以抽象为在一个坐标系中初始时所有点都为0，然后有m次操作，有两种

1，将一个矩形中的所有点都异或1,0变1,1变0，

2，查询一个点的数

**题目思路：**

这种题可以是一个一维问题扩栈而来，一维就是在x轴上，矩形变成一段区间，对于一维我们只需在

a\[l\]+1,a\[r+1\]-1,当查询是质询查询改点左边的前缀和，因为在区间内左边有个+1区间外面抵消了，

而维护前缀和用个一维树状数组就可有，而这题我们可以用二维树状数组来维护，然后就是更新在那个

要变化，首先 (x1,y1) +1 ,因为在区间都要保证有个加一，所以我们可以想到在(x1,y2+1)和(x2+1,y1) -1

然后还要个加一来抵消，那就是(x2+1,y2+1)

**AC代码：**

#include<bits/stdc++.h>
    using namespace std;
    
    int a[1005][1005];
    
    int get(int x){return x&(-x);}
    
    void add(int x,int y,int v)
    {
        for(;x<=1000;x+=get(x))
        {
            for(int i=y;i<=1000;i+=get(i))
            {
                a[x][i]+=v;
            }
        }
    }
    
    int sum(int x,int y)
    {
        int res= 0;
        for(;x>0;x-=get(x))
        {
            for(int i=y;i>0;i-=get(i))
            {
                res+=a[x][i];
            }
        }
        return res;
    }
    
    int main()
    {
        int t;cin>>t;
        while(t--)
        {
            int q;scanf("%d",&q);
            memset(a,0,sizeof(a));
            while(q--)
            {
                char ch[5];
                int a,b,c,d;
                scanf("%s",ch);
                if(ch[0]=='C')
                {
                    scanf("%d%d%d%d",&a,&b,&c,&d);
                    add(a,b,1);
                    add(c+1,d+1,1);
                    add(a,d+1,-1);
                    add(c+1,b,-1);
                }
                else
                {
                    scanf("%d%d",&a,&b);
                    int ans = sum(a,b);
                    printf("%d\n",ans%2);
    
                }
            }
        }
        return 0;
    }

[CDOJ1601]: http://acm.uestc.edu.cn/#/problem/show/1601