hdu 2642 Stars

题意：
二维平面上一开始所有星星都是暗淡的。

给出3种操作：

1.将x，y处的星星点亮；

2.将x，y处的星星灭掉；

3.统计x1,y1,x2,y2区间内有多少颗亮的星星。

思路：

二维树状数组裸题。

注意x1,x2,y1,y2数据给出的并不是有序的，这是一个坑点。

代码：

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <algorithm>
 4 using namespace std;
 5 const int N = 1005;
 6 int c[N][N];
 7 bool vis[N][N];
 8 int lowbit(int x)
 9 {
10     return x&(-x);
11 }
12 void add(int x,int y,int k)
13 {
14     //puts("hh");
15     for (int i = x;i <= 1001;i += lowbit(i))
16     {
17         for (int j = y;j <= 1001;j += lowbit(j))
18         {
19             c[i][j] += k;
20         }
21     }
22 }
23 int getsum(int x,int y)
24 {
25     int ans = 0;
26     for (int i = x;i > 0;i -= lowbit(i))
27     {
28         for (int j = y;j > 0;j -= lowbit(j))
29         {
30             ans += c[i][j];
31         }
32     }
33     return ans;
34 }
35 int main()
36 {
37     int m;
38     scanf("%d",&m);
39     while (m--)
40     {
41         char s[5];
42         scanf("%s",s);
43         if (s[0] == 'B')
44         {
45             int x,y;
46             scanf("%d%d",&x,&y);
47             x++,y++;
48             if (vis[x][y]) continue;
49             vis[x][y] = 1;
50             add(x,y,1);
51         }
52         if (s[0] == 'D')
53         {
54             int x,y;
55             scanf("%d%d",&x,&y);
56             x++,y++;
57             if (!vis[x][y]) continue;
58             vis[x][y] = 0;
59             add(x,y,-1);
60         }
61         if (s[0] == 'Q')
62         {
63             int x1,y1,x2,y2;
64             scanf("%d%d%d%d",&x1,&x2,&y1,&y2);
65             x1++,y1++,x2++,y2++;
66             if (x1 > x2) swap(x1,x2);
67             if (y1 > y2) swap(y1,y2);
68             int cnt1 = getsum(x2,y2);
69             int cnt2 = getsum(x2,y1-1);
70             int cnt3 = getsum(x1-1,y2);
71             int cnt4 = getsum(x1-1,y1-1);
72             int ans = cnt1 - cnt2 - cnt3 + cnt4;
73             //printf("%d*
",cnt1);
74             printf("%d
",ans);
75         }
76     }
77     return 0;
78 }