Stars |
| Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/65536 K (Java/Others) |
| Total Submission(s): 111 Accepted Submission(s): 54 |
|
Problem Description
Yifenfei is a romantic guy and he likes to count the stars in the sky.
To make the problem easier,we considerate the sky is a two-dimension plane.Sometimes the star will be bright and sometimes the star will be dim.At first,there is no bright star in the sky,then some information will be given as "B x y" where 'B' represent bright and x represent the X coordinate and y represent the Y coordinate means the star at (x,y) is bright,And the 'D' in "D x y" mean the star at(x,y) is dim.When get a query as "Q X1 X2 Y1 Y2",you should tell Yifenfei how many bright stars there are in the region correspond X1,X2,Y1,Y2. There is only one case. |
|
Input
The first line contain a M(M <= 100000), then M line followed.
each line start with a operational character. if the character is B or D,then two integer X,Y (0 <=X,Y<= 1000)followed. if the character is Q then four integer X1,X2,Y1,Y2(0 <=X1,X2,Y1,Y2<= 1000) followed. |
|
Output
For each query,output the number of bright stars in one line.
|
|
Sample Input
5 |
|
Sample Output
1 |
|
Author
teddy
|
|
Source
百万秦关终属楚
|
|
Recommend
teddy
|
/*
题意：二维坐标，然后三种操作，B x y 坐标(x,y)处的星星亮了，D x y坐标(x,y)处的星星灭了 Q X1 X2 Y1 Y2询问矩形内有多少颗
亮的星星 初步思路：二维树状数组，但是操作的时候先要查询一下当前位置星星的状态,还有就是查询的坐标可能不是x1<x2 y1<y2
*/
#include<bits/stdc++.h>
#define N 1010
#define lowbit(x) x&(-x)
using namespace std;
int t,X1,X2,Y1,Y2;
int n1,n2,m1,m2;
char op[];
int c[N][N];
void update(int x,int y,int val)
{
for(int i=x;i<N;i+=lowbit(i))
{
for(int j=y;j<N;j+=lowbit(j))
{
c[i][j]+=val;
}
}
// return val;//返回你实际搬运的东西
}
int getsum(int x,int y)
{
int s=;
for(int i=x;i>;i-=lowbit(i))
{
for(int j=y;j>;j-=lowbit(j))
{
s+=c[i][j];
}
}
return s;
}
void init(){
memset(c,,sizeof c);
}
int main(){
// freopen("in.txt","r",stdin);
init();
scanf("%d",&t);
while(t--){
scanf("%s",op);
if(op[]=='B'){
scanf("%d%d",&X1,&Y1);
X1++;
Y1++;
//先查询一下当前位置的星星是不是亮着的
if(getsum(X1,Y1)-getsum(X1-,Y1)-getsum(X1,Y1-)+getsum(X1-,Y1-)==){
// cout<<"有星星亮的"<<endl;
continue;
} update(X1,Y1,); }else if(op[]=='D'){
scanf("%d%d",&X1,&Y1);
X1++;
Y1++;
//先查询一下当前位置的星星是不是没亮
if(getsum(X1,Y1)-getsum(X1-,Y1)-getsum(X1,Y1-)+getsum(X1-,Y1-)==){
// cout<<"星星已经灭了"<<endl;
continue;
}
update(X1,Y1,-); }else{
scanf("%d%d%d%d",&X1,&X2,&Y1,&Y2);
X1++;X2++;
Y1++;Y2++;
// cout<<X1<<" "<<Y1<<" "<<X2<<" "<<Y2<<endl;
// cout<<getsum(X2,Y2)<<" "<<getsum(X1-1,Y2)<<" "<<getsum(X2,Y1-1)<<" "<<getsum(X1-1,Y1-1)<<endl;
n1=min(X1,X2),m1=min(Y1,Y2),n2=max(X1,X2),m2=max(Y1,Y2);
printf("%d\n",getsum(n2,m2)-getsum(n1-,m2)-getsum(n2,m1-)+getsum(n1-,m1-));
}
}
return ;
}