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.

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次，但只要之后涂一次白色，它就变成白色了。差分记录的数据不存在意义。