POJ 2155 - Matrix 二维树状数组..区间更新..单点查询

2019-04-14 21:24发布

站内文章 / 模拟电子
12629 0 1715
               题意:                        给了一个N*N的矩阵(1<=N<=1000)..初始时每个格子里都是0...而对一个格子进行操作是将其0变1~或1变0...现在不断地对其一些子矩阵进行操作.并且不断询问某个格子是0还是1....                题解:                        首先想到要知道该格子是0还是1只要知道它被操作了几次就好..模2是1答案就是1..模2是0答案就是0..                        对于连续二维区域进行维护...用二维的线段树或者树状数组..写起来也挺简单的..相当于update嵌套一个update..query嵌套一个query...                        对于区间更新拆成4次更新.....单点查询直接查...
Program: #include #include #include #include #include #include #include #include #include #include #define ll long long #define oo 1000000009 #define MAXN 1005 #define pi acos(-1.0) #define esp 1e-30 #define MAXD 4 using namespace std; int sum[MAXN][MAXN],N; void updateX(int x,int y,int d) { while (x<=N) { sum[y][x]+=d; x+=x&(-x); } } void update(int x,int y,int d) { if (!y || !x) return; while (y<=N) { updateX(x,y,d); y+=y&(-y); } } int queryX(int x,int y) { int ans=0; while (x) { ans+=sum[y][x]; x-=x&(-x); } return ans; } int query(int x,int y) { if (!y || !x) return 0; int ans=0; while (y) { ans+=queryX(x,y); y-=y&(-y); } return ans; } int main() { int T,Q,cases,x1,y1,x2,y2,x,y; char c; scanf("%d",&T); for (cases=1;cases<=T;cases++) { scanf("%d%d",&N,&Q); memset(sum,0,sizeof(sum)); while (Q--) { do { c=getchar(); } while (c!='C' && c!='Q'); if (c=='C') { scanf("%d%d%d%d",&x1,&y1,&x2,&y2),x2++,y2++; update(x1,y1,1),update(x2,y2,1); update(x1,y2,-1),update(x2,y1,-1); }else { scanf("%d%d",&x,&y); x1=query(x,y); printf("%d ",x1&1); } } if (cases!=T) printf(" "); } return 0; }

热门文章