Counting Black
| Time Limit: 1000MS | Memory Limit: 10000K | |
| Total Submissions: 9655 | Accepted: 6225 |
Description
There is a board with 100 * 100 grids as shown below. The left-top gird is denoted as (1, 1) and the right-bottom grid is (100, 100). 
We may apply three commands to the board:
1. WHITE x, y, L // Paint a white square on the board, // the square is defined by left-top grid (x, y) // and right-bottom grid (x+L-1, y+L-1) 2. BLACK x, y, L // Paint a black square on the board, // the square is defined by left-top grid (x, y) // and right-bottom grid (x+L-1, y+L-1) 3. TEST x, y, L // Ask for the number of black grids // in the square (x, y)- (x+L-1, y+L-1)In the beginning, all the grids on the board are white. We apply a series of commands to the board. Your task is to write a program to give the numbers of black grids within a required region when a TEST command is applied.
Input
The first line of the input is an integer t (1 <= t <= 100), representing the number of commands. In each of the following lines, there is a command. Assume all the commands are legal which means that they won't try to paint/test the grids outside the board.
Output
For each TEST command, print a line with the number of black grids in the required region.
Sample Input
5BLACK 1 1 2BLACK 2 2 2TEST 1 1 3WHITE 2 1 1TEST 1 1 3
Sample Output
76
Source
1 #include2 #include 3 #include 4 5 using namespace std; 6 7 int a[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(col[x][y] == color)18 return;19 col[x][y] = color;20 for(int i = x; i < 105; i += lowbit(i))21 for(int j = y; j < 105; j += lowbit(j))22 a[i][j] += color;23 }24 25 int getSum(int x, int y)26 {27 int ans = 0;28 for(int i = x; i > 0; i -= lowbit(i))29 for(int j = y; j > 0; j -= lowbit(j))30 ans += a[i][j];31 return ans;32 }33 34 int main()35 {36 int T, x, y, len;37 char cmd[10];38 scanf("%d", &T);39 memset(a, 0, sizeof(a));40 memset(col, -1, sizeof(col));41 while(T--)42 {43 scanf("%s%d%d%d", cmd, &x, &y, &len);44 if(cmd[0] == 'B')45 {46 for(int i = x; i < x+len; ++i)47 for(int j = y; j < y+len; ++j)48 add(i, j, 1);49 }50 else if(cmd[0] == 'W')51 {52 for(int i = x; i < x+len; ++i)53 for(int j = y; j < y+len; ++j)54 add(i, j, -1);55 }56 else57 {58 printf("%d\n", getSum(x+len-1,y+len-1) + getSum(x-1,y-1) - getSum(x-1,y+len-1) - getSum(x+len-1,y-1));59 }60 }61 return 0;62 }