# POJ1656总结

## Counting Black

### Description

There is a board with 100 * 100 grids as shown below. The left-top gird is denoted as (1, 1) and the right-bottom grid is (100, 100).

We may apply three commands to the board:

```1.	WHITE  x, y, L     // Paint a white square on the board,
// the square is defined by left-top grid (x, y)
// and right-bottom grid (x+L-1, y+L-1)

2.	BLACK  x, y, L     // Paint a black square on the board,
// the square is defined by left-top grid (x, y)
// and right-bottom grid (x+L-1, y+L-1)

3.	TEST     x, y, L    // Ask for the number of black grids
// in the square (x, y)- (x+L-1, y+L-1) ```

In the beginning, all the grids on the board are white. We apply a series of commands to the board. Your task is to write a program to give the numbers of black grids within a required region when a TEST command is applied.

### Input

The first line of the input is an integer t (1 <= t <= 100), representing the number of commands. In each of the following lines, there is a command. Assume all the commands are legal which means that they won’t try to paint/test the grids outside the board.

### Output

For each TEST command, print a line with the number of black grids in the required region.

```5
BLACK 1 1 2
BLACK 2 2 2
TEST 1 1 3
WHITE 2 1 1
TEST 1 1 3
```

```7
6```

### 我的代码

``````#include<stdio.h>
#include<string.h>
int map={0};
int c={0};
int t,x,y,l;
char ope;
inline int lowbit(int x)
{
return x&-x;
}
void update(int x,int y,int value)
{
for (int i=x;i<=100;i+=lowbit(i))
{
for (int j=y;j<=100;j+=lowbit(j))
{
c[i][j]+=value;
}
}
}
int getSum(int x,int y)
{
int res=0;
for (int i=x;i>0;i-=lowbit(i))
{
for (int j=y;j>0;j-=lowbit(j))
{
res+=c[i][j];
}
}
return res;
}
int main()
{
scanf("%d",&t);
while (t--)
{
scanf("%s%d%d%d",ope,&x,&y,&l);
if (strcmp(ope,"BLACK")==0)
{
for (int i=x;i<=x+l-1;i++)
{
for (int j=y;j<=y+l-1;j++)
{
if (map[i][j]==0)
{
map[i][j]=1;
update(i,j,1);
}
}
}
}
else if (strcmp(ope,"WHITE")==0)
{
for (int i=x;i<=x+l-1;i++)
{
for (int j=y;j<=y+l-1;j++)
{
if (map[i][j]==1)
{
map[i][j]=0;
update(i,j,-1);
}
}
}
}
else if (strcmp(ope,"TEST")==0)
{
int ans=getSum(x+l-1,y+l-1)-getSum(x-1,y+l-1)-getSum(x+l-1,y-1)+getSum(x-1,y-1);
printf("%d\n",ans);
}
}
}``````