2014
02-12

# Stars

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.

The first line contain a M(M <= 100000), then M line followed.
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.

The first line contain a M(M <= 100000), then M line followed.
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.

5
B 581 145
B 581 145
Q 0 600 0 200
D 581 145
Q 0 600 0 200

1
0

/************************************************
* By: chenguolin                               *
* Date: 2013-08-21                             *
***********************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1010;

int m;
int num[MAXN][MAXN];
int treeNum[MAXN][MAXN];

int lowbit(int x){
return x&(-x);
}

int getSum(int x , int y){
int sum = 0;
for(int i = x ; i > 0 ; i -= lowbit(i))
for(int j = y ; j > 0 ; j -= lowbit(j))
sum += treeNum[i][j];
return sum;
}

void add(int x , int y , int val){
for(int i = x ; i < MAXN ; i += lowbit(i))
for(int j = y ; j < MAXN ; j += lowbit(j))
treeNum[i][j] += val;
}

void solve(){
memset(num , 0 , sizeof(num));
memset(treeNum , 0 , sizeof(treeNum));
char c;
int x , y , val;
int x1 , x2 , y1 , y2;
int x3 , x4 , y3 , y4;
while(m--){
scanf("%c" , &c);
if(c == 'B'){
scanf("%d%d%*c" , &x , &y);
x++ , y++;
val = num[x][y] ? 0 : 1;
if(val)
num[x][y] = 1;
}
else if(c == 'D'){
scanf("%d%d%*c" , &x , &y);
x++ , y++;
if(num[x][y])
num[x][y] = 0;
}
else{
scanf("%d%d" , &x1 , &x2);
scanf("%d%d%*c" , &y1 , &y2);
x1++ , x2++ , y1++ , y2++;
x3 = min(x1 , x2) , y3 = min(y1 , y2);
x4 = max(x1 , x2) , y4 = max(y1 , y2);
int ans = getSum(x4 , y4);
ans -= getSum(x3-1 , y4);
ans -= getSum(x4 , y3-1);
ans += getSum(x3-1 , y3-1);
printf("%d\n" , ans);
}
}
}

int main(){
while(scanf("%d%*c" , &m) != EOF)
solve();
return 0;
}

1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

2. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

3. 如果两个序列的最后字符不匹配（即X [M-1]！= Y [N-1]）
L（X [0 .. M-1]，Y [0 .. N-1]）= MAX（L（X [0 .. M-2]，Y [0 .. N-1]），L（X [0 .. M-1]，Y [0 .. N-1]）
这里写错了吧。