#include<iostream>
#include<string>
#include<cstring>
using namespace std;

int c[101][101];
int b[101][101];
int Row,Col;


inline int Lowbit(const int &x)
{
    return x&(-x);
}

int Sum(int i,int j)
{
    int tempj,sum=0;
	while(i > 0)
	{
		tempj=j;
		while(tempj > 0){
		    sum+=c[i][tempj];
			tempj-=Lowbit(tempj);
		}
		i-=Lowbit(i);
	}
	return sum;
}

void Update(int i,int j,int num)
{
    int tempj;
	while(i<=Row)
	{
	    tempj=j;
		while(tempj<=Col){
		    c[i][tempj]+=num;
			tempj+=Lowbit(tempj);
		}
		i+=Lowbit(i);
	}
}

void whiteUpdate(int x,int y,int L)
{
    for(int i=x;i<x+L;++i)
		for(int j=y;j<y+L;++j)
		{
		    if(b[i][j]==1) {b[i][j]=0;Update(i,j,-1);}
			else continue;
		}
}

void blackUpdate(int x,int y,int L)
{
    for(int i=x;i<x+L;++i)
		for(int j=y;j<y+L;++j)
		{
		    if(b[i][j]==1) continue;
			else {b[i][j]=1;Update(i,j,1);};
		}
}

int blackSum(int x,int y,int L)
{
   return Sum(x+L-1,y+L-1)+Sum(x-1,y-1)-Sum(x-1,y+L-1)-Sum(x+L-1,y-1); 
}

int main()
{
    int x,y,L,N;
	string str;
	Row=Col=100;
	memset(c,0,sizeof(c));
	memset(b,0,sizeof(b));
	cin>>N;
	while(N--)
	{
	    cin>>str>>x>>y>>L;
		switch(str[0])
		{
		    case 'W':
				whiteUpdate(x,y,L);
				break;
			case 'B':
				blackUpdate(x,y,L);
				break;
			case 'T':
				cout<<blackSum(x,y,L)<<endl;
				break;
			default: break;
		}
	}
	return 0;
}

• Re:二维树状树组 (573) yinxmm 2012-05-24 14:06:56
• 有个P用，O(n3) (0) lxc902 2012-07-30 16:04:50