NYOJ172 小珂的图表

小珂的图表

时间限制：1000 ms | 内存限制：65535 KB

难度：2

描述

小珂最近有一个麻烦,就是要统计一下指定区域中有几个方格被染黑了.表格的布局及表格各个位置的坐标如下所示.

有三种操作命令,

BLACK x,y,l 表示把以坐标（x,y）为左上角顶点，（x+l-1,y+l-1）为右下角顶点的矩形染黑。

WHITE x,y,l 表示吧指定区域染白。

TEST x,y,l 表示计算指定区域的黑块的个数。

说明：如果 x,y,x+l-1 ,y+l-1超出图表的范围，就只计算图表内部的。

输入

第一行有一个整数n(0<n<100)，表示有n条命令，随后的n行有n个指令。

输出

遇到TEST命令，把结果输出并换行。

样例输入

5
BLACK 1 1 2
BLACK 2 2 2
TEST 1 1 3
WHITE 2 1 1
TEST 1 1 3

样例输出

7
6

来源

POJ

 1 #include <cstdio>
 2 #include <iostream>
 3 #include <cstring>
 4 
 5 using namespace std;
 6 
 7 int map[105][105];
 8 int col[105][105];
 9 
10 int lowbit(int i)
11 {
12     return i & (-i);
13 }
14 
15 void add(int x, int y, int color)
16 {
17     if(color == col[x][y])
18         return ;
19     col[x][y] = color;
20     for(int i = x; i <= 100; i += lowbit(i))
21         for(int j = y; j <= 100; j += lowbit(j))
22             map[i][j] += color;
23 }
24 
25 int getSum(int x, int y)
26 {
27     int tot = 0;
28     for(int i = x; i > 0; i -= lowbit(i))
29         for(int j = y; j > 0; j -= lowbit(j))
30             tot += map[i][j];
31     return tot;
32 }
33 
34 int main()
35 {
36     int T, x, y, x1, y1, len;
37     char cmd[10];
38     memset(map, 0, sizeof(map));
39     memset(col, -1, sizeof(col));  // 初始标记每个格子都是白色 
40     
41     scanf("%d", &T);
42     while(T--)
43     {
44         scanf("%s%d%d%d", cmd, &x, &y, &len);
45         
46         x1 = x+len-1 > 100 ? 100 : x+len-1;
47         y1 = y+len-1 > 100 ? 100 : y+len-1;
48         
49         if(cmd[0] == 'B')
50         {
51             for(int i = x; i <= x1; ++i)
52                 for(int j = y; j <= y1; ++j)
53                     add(i, j, 1);
54         }
55         else if(cmd[0] == 'W')
56         {
57             for(int i = x; i <= x1; ++i)
58                 for(int j = y; j <= y1; ++j)
59                     add(i, j, -1);
60         }
61         else
62         {
63             printf("%d\n", getSum(x1,y1)+getSum(x-1,y-1)-getSum(x-1,y1)-getSum(x1,y-1));
64         }
65     }
66     return 0;
67 }