HDU - 2642 Stars

題意：就是求每個矩形內的亮的星星的個數

思路：二維的樹狀數組，相當於優化了的矩陣求和的題目

#include 
#include 
#include 
#include 
using namespace std;
const int MAXN = 1005;

int arr[MAXN][MAXN];
int vis[MAXN][MAXN];

int lowbit(int x){
	return x & (-x);
}

void update(int i,int j,int d){
	int tmpj;
	while (i < MAXN){
		tmpj = j;
		while (tmpj < MAXN){
			arr[i][tmpj] += d;
			tmpj += lowbit(tmpj);
		}
		i += lowbit(i);
	}
}

int sum(int i,int j){
	int tmpj,sum = 0;
	while (i > 0){
		tmpj = j;
		while (tmpj > 0){
			sum += arr[i][tmpj];
			tmpj -= lowbit(tmpj);
		}
		i -= lowbit(i);
	}
	return sum;
}

int main(){
	memset(vis,0,sizeof(vis));
	memset(arr,0,sizeof(arr));
	int t,a,b,c,d;
	char op;
	scanf("%d",&t);
	while (t--){
		getchar();
		scanf("%c",&op);
		if (op == 'B'){
			scanf("%d%d",&a,&b);
			a++,b++;
			if (!vis[a][b]){
				vis[a][b] = 1;
				update(a,b,1);
			}
		}
		else if (op == 'D'){
			scanf("%d%d",&a,&b);
			a++,b++;
			if (vis[a][b]){
				vis[a][b] = 0;
				update(a,b,-1);
			}
		}
		else {
			scanf("%d%d%d%d",&a, &b, &c, &d);
			a++,b++,c++,d++;
			if (b > a)
				swap(a,b);
			if (d > c)
				swap(c,d);
			int ans = sum(a,c)+sum(b-1,d-1)-sum(a,d-1)-sum(b-1,c);
			printf("%d\n",ans);	
		}
	}
	return 0;
}