Matrix
| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 16950 | Accepted: 6369 |
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].
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.
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.
Sample Input
12 10C 2 1 2 2Q 2 2C 2 1 2 1Q 1 1C 1 1 2 1C 1 2 1 2C 1 1 2 2Q 1 1C 1 1 2 1Q 2 1
Sample Output
1001
Source
,Lou Tiancheng
代码：
采用树状数组第二种方法
采用更新向下，统计向上的方法....楼教主这道题出的还是比较新颖的......
代码：438ms
1 #include2 #include 3 #include 4 #define maxn 1005 5 #define lowbit(x) ((x)&(-x)) 6 int aa[maxn][maxn]; 7 int nn; 8 void ope(int x ,int y ,int val) 9 {10 for(int i=x ;i>0 ;i-=lowbit(i))11 {12 for(int j=y ;j>0 ;j-=lowbit(j))13 {14 aa[i][j]+=val;15 }16 }17 }18 int clac(int x,int y)19 {20 int ans=0;21 for(int i=x;i<=nn ;i+=lowbit(i))22 {23 for(int j=y ;j<=nn ;j+=lowbit(j))24 {25 ans+=aa[i][j];26 }27 }28 return ans;29 }30 struct node31 {32 int x;33 int y;34 };35 36 int main()37 {38 int tt,xx;39 char str[5];40 node sa,sb;41 scanf("%d",&xx);42 while(xx--)43 {44 memset(aa,0,sizeof(aa));45 scanf("%d%d",&nn,&tt);46 while(tt--)47 {48 scanf("%s",&str);49 if(str[0]=='C')50 {51 scanf("%d%d%d%d",&sa.x,&sa.y,&sb.x,&sb.y);52 sa.x--; //左上角全体加153 sa.y--;54 ope(sb.x,sb.y,1);55 ope(sa.x,sb.y,-1);56 ope(sb.x,sa.y,-1); 57 ope(sa.x,sa.y,1);58 }59 else60 {61 scanf("%d%d",&sa.x,&sa.y);62 printf("%d\n",clac(sa.x,sa.y)&1);63 }64 }65 printf("\n");66 }67 return 0;68 }
改进版..
代码： 1 #include2 #include 3 #include 4 #define maxn 1005 5 #define lowbit(x) ((x)&(-x)) 6 int aa[maxn][maxn]; 7 int nn; 8 void ope(int x ,int y ) 9 {10 for(int i=x ;i>0 ;i-=lowbit(i))11 {12 for(int j=y ;j>0 ;j-=lowbit(j))13 {14 aa[i][j]=aa[i][j]^1;15 }16 }17 }18 int clac(int x,int y)19 {20 int ans=0;21 for(int i=x;i<=nn ;i+=lowbit(i))22 {23 for(int j=y ;j<=nn ;j+=lowbit(j))24 {25 ans+=aa[i][j];26 }27 }28 return ans;29 }30 struct node31 {32 int x;33 int y;34 };35 36 int main()37 {38 int tt,xx;39 char str[5];40 node sa,sb;41 scanf("%d",&xx);42 while(xx--)43 {44 memset(aa,0,sizeof(aa));45 scanf("%d%d",&nn,&tt);46 while(tt--)47 {48 scanf("%s",&str);49 if(str[0]=='C')50 {51 scanf("%d%d%d%d",&sa.x,&sa.y,&sb.x,&sb.y);52 sa.x--; //左上角全体加153 sa.y--;54 ope(sb.x,sb.y);55 ope(sa.x,sb.y);56 ope(sb.x,sa.y); 57 ope(sa.x,sa.y);58 }59 else60 {61 scanf("%d%d",&sa.x,&sa.y);62 printf("%d\n",clac(sa.x,sa.y)&1);63 }64 }65 printf("\n");66 }67 return 0;68 }
采用树状数组第一种方法
传统的方法：
代码：435ms
1 #include2 #include 3 #include 4 #define maxn 1005 5 #define lowbit(x) ((x)&(-x)) 6 int aa[maxn][maxn]; 7 int nn; 8 void ope(int x ,int y ) 9 {10 for(int i=x ;i<=nn ;i+=lowbit(i))11 for(int j=y ;j<=nn ;j+=lowbit(j))12 aa[i][j]=aa[i][j]^1;13 }14 int clac(int x,int y)15 {16 int ans=0,i,j;17 for(i=x;i>0 ;i-=lowbit(i))18 for(j=y ;j>0 ;j-=lowbit(j))19 ans+=aa[i][j];20 return ans;21 }22 struct node23 {24 int x,y;25 };26 int main()27 {28 int tt,xx;29 char str[5];30 node sa,sb;31 scanf("%d",&xx);32 while(xx--)33 {34 memset(aa,0,sizeof(aa));35 scanf("%d%d",&nn,&tt);36 while(tt--)37 {38 scanf("%s",&str);39 if(str[0]=='C')40 {41 scanf("%d%d%d%d",&sa.x,&sa.y,&sb.x,&sb.y);42 sb.x++; //左上角全体加143 sb.y++;44 ope(sb.x,sb.y);45 ope(sa.x,sb.y);46 ope(sb.x,sa.y);47 ope(sa.x,sa.y);48 }49 else50 {51 scanf("%d%d",&sa.x,&sa.y);52 printf("%d\n",clac(sa.x,sa.y)&1);53 }54 }55 printf("\n");56 }57 return 0;58 }