Stars

5B 581 145B 581 145Q 0 600 0 200D 581 145Q 0 600 0 200 Sample Output
10  題目大意：  二維空間里，初始時(shí)一片空白，有如下幾種操作：  1.B x y  ：將坐標(biāo)為（x，y）的地方點(diǎn)亮  2.D x y  ：將坐標(biāo)為（x，y）的地方熄滅  3. Q x x1 y y1 ：查詢該矩形區(qū)域內(nèi)點(diǎn)亮的星星個(gè)數(shù) 題解：樹狀數(shù)組模板 唯一坑點(diǎn)：當(dāng)點(diǎn)（x，y）處已經(jīng)點(diǎn)亮，則不再點(diǎn)亮 熄滅操作雷同。
#include<stdio.h>#include<string.h>#include<algorithm>using namespace std;#define maxn 1005int a[maxn][maxn],b[maxn][maxn];int lowbit(int x){	return x&-x;}void update(int x,int y,int z){	int i,j;	for(i=x;i<=maxn;i+=lowbit(i))		for(j=y;j<=maxn;j+=lowbit(j))			a[i][j]+=z;}int query(int x,int y){	int sum=0,i,j;	for(i=x;i>0;i-=lowbit(i))		for(j=y;j>0;j-=lowbit(j))			sum+=a[i][j];	return sum;}int  main(){	int n,i,x,y,xx,yy;	scanf("%d",&n);	for(i=1;i<=n;i++)	{		char c[5];		scanf("%s",c);		if(c[0]=='B')		{			scanf("%d%d",&x,&y);			x++;y++;			if(b[x][y])				continue;			update(x,y,1);			b[x][y]=1;		}		else if(c[0]=='D')		{			scanf("%d%d",&x,&y);			x++;y++;			if(!b[x][y])				continue;			update(x,y,-1);			b[x][y]=0;		}		else		{			scanf("%d%d%d%d",&x,&xx,&y,&yy);			x++;y++;			xx++;yy++;			if(x<xx)				swap(x,xx);			if(y<yy)				swap(y,yy);			int ans=query(x,y)-query(x,yy-1)-(query(xx-1,y)-query(xx-1,yy-1));			printf("%d/n",ans);		}	}}