本文共 1947 字，大约阅读时间需要 6 分钟。
裸二维树状数组，题义就是求一块面积内处于发亮状态的星星的个数。
代码如下：
#include #include #include #include #include #define MAXN 1005 using namespace std; int c[MAXN+5][MAXN+5], N; bool B[MAXN][MAXN]; inline int lowbit(int x) { return x & -x; } inline void modify(int posx, int posy, int val) { for (int i = posx; i <= MAXN; i += lowbit(i)) { for (int j = posy; j <= MAXN; j += lowbit(j)) c[i][j] += val; } } inline int getsum(int posx, int posy) { int s = 0; for (int i = posx; i > 0; i -= lowbit(i)) { for (int j = posy; j > 0; j -= lowbit(j)) s += c[i][j]; } return s; } inline void swap(int &a, int &b) { int t = a; a = b; b = t; } inline int deal(int x1, int y1, int x2, int y2) { if (x1 > x2) swap(x1, x2); if (y1 > y2) swap(y1, y2); return getsum(x2, y2) - getsum(x1-1, y2) - getsum(x2, y1-1) + getsum(x1-1, y1-1); } int main() { char op[5]; int x, y, a, b; while (scanf("%d", &N) == 1) { memset(c, 0, sizeof (c)); memset(B, 0, sizeof (B)); for (int i = 1; i <= N; ++i) { scanf("%s", op); if (op[0] == 'B') { scanf("%d %d", &x, &y); x++, y++; if (!B[x][y]) { B[x][y] = true; modify(x, y, 1); } } else if (op[0] == 'D') { scanf("%d %d", &x, &y); x++, y++; if (B[x][y]) { B[x][y] = false; modify(x, y, -1); } } else { scanf("%d %d %d %d", &a, &x, &b, &y); x++, y++, a++, b++; printf("%d\n", deal(a, b, x, y)); } } } return 0; }
转载于:https://www.cnblogs.com/Lyush/archive/2012/02/26/2368569.html