| Time Limit: 3000MS | Memory Limit: 65536K | |
| Total Submissions: 16950 | Accepted: 6369 |
Description
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 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
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
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 1005
#define lowbit(x) ((x)&(-x))
int aa[maxn][maxn];
int nn;
void ope(int x ,int y ,int val)
{
for(int i=x ;i> ;i-=lowbit(i))
{
for(int j=y ;j> ;j-=lowbit(j))
{
aa[i][j]+=val;
}
}
}
int clac(int x,int y)
{
int ans=;
for(int i=x;i<=nn ;i+=lowbit(i))
{
for(int j=y ;j<=nn ;j+=lowbit(j))
{
ans+=aa[i][j];
}
}
return ans;
}
struct node
{
int x;
int y;
}; int main()
{
int tt,xx;
char str[];
node sa,sb;
scanf("%d",&xx);
while(xx--)
{
memset(aa,,sizeof(aa));
scanf("%d%d",&nn,&tt);
while(tt--)
{
scanf("%s",&str);
if(str[]=='C')
{
scanf("%d%d%d%d",&sa.x,&sa.y,&sb.x,&sb.y);
sa.x--; //左上角全体加1
sa.y--;
ope(sb.x,sb.y,);
ope(sa.x,sb.y,-);
ope(sb.x,sa.y,-);
ope(sa.x,sa.y,);
}
else
{
scanf("%d%d",&sa.x,&sa.y);
printf("%d\n",clac(sa.x,sa.y)&);
}
}
printf("\n");
}
return ;
}
改进版..
代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 1005
#define lowbit(x) ((x)&(-x))
int aa[maxn][maxn];
int nn;
void ope(int x ,int y )
{
for(int i=x ;i> ;i-=lowbit(i))
{
for(int j=y ;j> ;j-=lowbit(j))
{
aa[i][j]=aa[i][j]^;
}
}
}
int clac(int x,int y)
{
int ans=;
for(int i=x;i<=nn ;i+=lowbit(i))
{
for(int j=y ;j<=nn ;j+=lowbit(j))
{
ans+=aa[i][j];
}
}
return ans;
}
struct node
{
int x;
int y;
}; int main()
{
int tt,xx;
char str[];
node sa,sb;
scanf("%d",&xx);
while(xx--)
{
memset(aa,,sizeof(aa));
scanf("%d%d",&nn,&tt);
while(tt--)
{
scanf("%s",&str);
if(str[]=='C')
{
scanf("%d%d%d%d",&sa.x,&sa.y,&sb.x,&sb.y);
sa.x--; //左上角全体加1
sa.y--;
ope(sb.x,sb.y);
ope(sa.x,sb.y);
ope(sb.x,sa.y);
ope(sa.x,sa.y);
}
else
{
scanf("%d%d",&sa.x,&sa.y);
printf("%d\n",clac(sa.x,sa.y)&);
}
}
printf("\n");
}
return ;
}
采用树状数组第一种方法
传统的方法：
代码：435ms
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define maxn 1005
#define lowbit(x) ((x)&(-x))
int aa[maxn][maxn];
int nn;
void ope(int x ,int y )
{
for(int i=x ;i<=nn ;i+=lowbit(i))
for(int j=y ;j<=nn ;j+=lowbit(j))
aa[i][j]=aa[i][j]^;
}
int clac(int x,int y)
{
int ans=,i,j;
for(i=x;i> ;i-=lowbit(i))
for(j=y ;j> ;j-=lowbit(j))
ans+=aa[i][j];
return ans;
}
struct node
{
int x,y;
};
int main()
{
int tt,xx;
char str[];
node sa,sb;
scanf("%d",&xx);
while(xx--)
{
memset(aa,,sizeof(aa));
scanf("%d%d",&nn,&tt);
while(tt--)
{
scanf("%s",&str);
if(str[]=='C')
{
scanf("%d%d%d%d",&sa.x,&sa.y,&sb.x,&sb.y);
sb.x++; //左上角全体加1
sb.y++;
ope(sb.x,sb.y);
ope(sa.x,sb.y);
ope(sb.x,sa.y);
ope(sa.x,sa.y);
}
else
{
scanf("%d%d",&sa.x,&sa.y);
printf("%d\n",clac(sa.x,sa.y)&);
}
}
printf("\n");
}
return ;
}