题目大意:给定一个初始时全部为0的n*n的矩阵,然后将一个子矩阵中的全部元素取反,询问一个元素当前是什么 思路:将取反操作当成转化为操作次数,容易得到若操作次数为偶数则为0否则为1.将问题转化为区间修改+单点查询.对于区间修改用差分实现,则答案为所有前缀和.用树状数组维护即可 PS:这题输入很恶心,数后还有一个空格
#include<iostream> #include<cstdio> #include<cmath> #include<cstring> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fod(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=1e3+10; int n,q,tr[N][N]; #define lowbit(x) ((x)&(-x)) void update(int idx,int idy,int val) { for(int i=idx;i<=n;i+=lowbit(i)) for(int j=idy;j<=n;j+=lowbit(j)) tr[i][j]+=val; } int query(int idx,int idy) { int ret=0; for(int i=idx;i;i-=lowbit(i)) for(int j=idy;j;j-=lowbit(j)) ret+=tr[i][j]; return ret; } int main() { int T;scanf("%d",&T); while(T--) { scanf("%d%d ",&n,&q); memset(tr,0,sizeof(tr)); for(int x1,x2,y1,y2,i=1;i<=q;i++) { char op[2]; scanf("%s",op); if(op[0]=='C') { scanf("%d%d%d%d",&x1,&y1,&x2,&y2); update(x2+1,y2+1,1); update(x1,y2+1,-1); update(x2+1,y1,-1); update(x1,y1,1); } else { scanf("%d%d",&x1,&y1); printf("%d\n",query(x1,y1)%2); } } if(T) puts(""); } return 0; }