| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 25080 | Accepted: 9293 |
Description
Given an N*N matrix A, whose elements are either 0 or 1. A[i, j] means the number in the i-th row and j-th column. Initially we have A[i, j] = 0 (1 <= i, j <= N).
We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using "not" operation (if it is a '0' then change it into '1' otherwise change it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).
2. Q x y (1 <= x, y <= n) querys A[x, y].
We can change the matrix in the following way. Given a rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2), we change all the elements in the rectangle by using "not" operation (if it is a '0' then change it into '1' otherwise change it into '0'). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.
1. C x1 y1 x2 y2 (1 <= x1 <= x2 <= n, 1 <= y1 <= y2 <= n) changes the matrix by using the rectangle whose upper-left corner is (x1, y1) and lower-right corner is (x2, y2).
2. Q x y (1 <= x, y <= n) querys A[x, y].
Input
The first line of the input is an integer X (X <= 10) representing the number of test cases. The following X blocks each represents a test case.
The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format "Q x y" or "C x1 y1 x2 y2", which has been described above.
The first line of each block contains two numbers N and T (2 <= N <= 1000, 1 <= T <= 50000) representing the size of the matrix and the number of the instructions. The following T lines each represents an instruction having the format "Q x y" or "C x1 y1 x2 y2", which has been described above.
Output
For each querying output one line, which has an integer representing A[x, y].
There is a blank line between every two continuous test cases.
There is a blank line between every two continuous test cases.
Sample Input
1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1
Sample Output
1
0
0
1
Source
POJ Monthly,Lou Tiancheng
二维树状数组果然比二维线段树简单多了讲一下二维树状数组其实我也不清楚多出来的一维怎么做但既然多套了一重循环就算作是二维了文字说不清，自己仿照一维画一个图就明白了再说这道题假设只有一维，我们可以用树状数组维护一个差分数组，区间首尾打标记+1，求和即可那么推广到二维，把维护差分数组的方式看成打一个标记四个点+1，对询问求一遍和模2尹神的办法zrl说可以推广，而这种办法只对01有效就是说对于正常的差分数组，区间修改应该是首加尾减到了二维应该这样维护-1 +1+1 -1就这样吧——by隔壁老司机RLQ
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 using namespace std; 8 const int mxn=1200; 9 int t[mxn][mxn]; 10 int n,m; 11 int lowbit(int x){return x&-x;} 12 int an; 13 void add(int x,int y,int v){ 14 while(x<=n){ 15 int tmp=y; 16 while(tmp<=n){ t[x][tmp]+=v; tmp+=lowbit(tmp);} 17 x+=lowbit(x); 18 } 19 } 20 int sum(int x,int y){ 21 int res=0; 22 while(x){ 23 int tmp=y; 24 while(tmp){ res+=t[x][tmp]; tmp-=lowbit(tmp);} 25 x-=lowbit(x); 26 } 27 return res; 28 } 29 int ask(int x1,int y1,int x2,int y2){ 30 return sum(x2,y2)+sum(x1-1,y1-1)-sum(x2,y1-1)-sum(x1,y2-1); 31 } 32 int main(){ 33 int T; 34 scanf("%d",&T); 35 int i,j; 36 char ch[5]; 37 int x1,y1,x2,y2; 38 while(T--){ 39 memset(t,0,sizeof t); 40 scanf("%d%d",&n,&m); 41 an=n+5; 42 for(i=1;i<=m;i++){ 43 scanf("%s",ch); 44 if(ch[0]=='C'){ 45 scanf("%d%d%d%d",&x1,&y1,&x2,&y2); 46 add(x1,y1,1); 47 add(x1,y2+1,-1); 48 add(x2+1,y1,-1); 49 add(x2+1,y2+1,1); 50 } 51 else{ 52 scanf("%d%d",&x1,&y1); 53 printf("%d ",sum(x1,y1)%2); 54 } 55 } 56 printf(" "); 57 } 58 return 0; 59 }