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.
Sample Input
5 BLACK 1 1 2 BLACK 2 2 2 TEST 1 1 3 WHITE 2 1 1 TEST 1 1 3
Sample Output
7 6
我的代码
使用树状数组。需要稍微注意一下的是,这里的数组是二维的,在更新和求和时需要对两个维度同时更新,同样的求和的结果也是从原点开始的一块数组的和。
对于遍历每一个需要上色的点,如果颜色没有改变的话就不需要更新树状数组。由于上色的复杂度比暴力还要高(nlogn)^2>n^2,所以导致数据规模很小且查询操作不多时,效率被暴力完爆。
代码如下:
#include<stdio.h>
#include<string.h>
int map[101][101]={0};
int c[101][101]={0};
int t,x,y,l;
char ope[10];
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);
}
}
}
复杂度为:

暴力的复杂度为:

反思
这道题最开始的想法是用差分来做,然而差分并不可行,因为一共只有黑白两色,我可以对一个格子涂上黑色10次,但只要之后涂一次白色,它就变成白色了。差分记录的数据不存在意义。