题目
给你一个二维矩阵，初始化为0，然后可以进行两次操作：
C:x,y,x1,y2 对该小矩阵内的数进行取反
Q:查询某个点是0还是1
题解：
C是区间修改，Q是单点查询，
我们将二维矩阵先简化成一维矩阵的情况，C是对一段区域[l,r]取反，我们没有必要对这段区域全部操作，我们只需要对点l和点（r+1）分别加1即可，然后查询k时，我们只需要求出k的前缀和，然后mod2即可
为什么？
如果，当k1在区间[l,r]里，k的前缀和比之前就了一个1，mod2之后就说明k1被改变了一次；当k2在[l,r]之前，没有影响；在[l,r]之后，k3的前缀和比原本多了2（l和r+1点分别多贡献一），mod 2之后就没影像了，相当于没改变
也就是当k的前缀和比原本多出奇数时，说明值比原先发生改变，否则就没有。
所以我们对于一个区间[L,R]，我们只需要改变点(L)和点(R+1),
同样回到本题，二维矩阵也是这样，
左上角是x1，y1，右下角是x2，y2
a[x1][y1]+1,
a[x2+1][y2]+1
a[x1][y2+1]+1,
a[x2+1][y1+1]+1
原理和上面一样
详细看图
然后用前缀和和二维树状数组来维护，单点更改，单点查询
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2000;
int a[maxn][maxn];
int n;
string s;
int lowbit(int x)
{
return x&(-x);
}
void add(int x,int y,int w)
{
for(int i=x;i<=n;i+=lowbit(x))
{
for(int j=y;j<=n;j+=lowbit(y))
{
a[i][j]+=w;
}
}
}
int sum(int x,int y)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))
{
for(int j=y;j;j-=lowbit(j))
{
ans+=a[i][j];
}
}
return ans;
}
int main()
{
int t;
cin>>t;
int x1,y1,x2,y2;
while(t--)
{
int k;
cin>>n>>k;
memset(a,0,sizeof(a));
for(int i=1;i<=k;i++)
{
cin>>s;
if(s[0]=='C')
{
cin>>x1>>y1>>x2>>y2;
add(x1,y1,1);
add(x2+1,y1,1);
add(x1,y2+1,1);
add(x2+1,y2+1,1);
}
else
{
int x,y;
cin>>x>>y;
cout<<sum(x,y)%2<<endl;
}
}
}
}
京公网安备 11010502036488号