Counting Black

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

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

Sample Output

7
6

C++版本一

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <math.h>
int X,n,t;
using namespace std;
const int N=110;
int tree[N][N],color[N][N];
void init(){
    for(int i=1;i<=100;i++)
        for(int j=1;j<=100;j++)
            tree[i][j]=0;

}
int lowbit(int x){

    return x&(-x);
}
void updata(int x, int y, int c)
{
    int i, j;
    int val=0;
    if(color[x][y] == c)
        return;
    if(c == 1) val = 1;
    else if(color[x][y] == 1)
        val = -1;
    color[x][y] = c;
    if(val == 0)
        return;

    for(i = x; i <= 100; i += lowbit(i))
        for(j = y; j <= 100; j += lowbit(j))
            tree[i][j] += val;
}

int query(int x,int y){
    int res=0;
    for(int i=x;i>0;i-=lowbit(i))
        for(int j=y;j>0;j-=lowbit(j))
            res+=tree[i][j];
    return res;
}
int main()
{

        scanf("%d",&n);
        init();
        char tmp[10];
        int x,y,l;

        while(n--){
            scanf("%s",tmp);

            scanf("%d%d%d",&x,&y,&l);
            if(tmp[0]=='W'){
                for(int i = x; i < x + l; i++)
                for(int j = y; j < y + l; j++)
                    updata(i,j,0);
            }else if(tmp[0]=='B'){
                for(int i = x; i < x + l; i++)
                for(int j = y; j < y + l; j++)
                    updata(i,j,1);

            }else{
                printf("%d\n",query(x+l-1,y+l-1)+query(x-1,y-1)-query(x+l-1,y-1)-query(x-1,y+l-1) );
                //cout << query(x,y) << endl;
            }

        }

    //cout << "Hello world!" << endl;
    return 0;
}

C++版本二

#include <iostream>
#define MAXNUM 101
using namespace std;

int point[MAXNUM][MAXNUM];//标记格子颜色

int main()
{
    int t;//t种情况
    //（x y）左上坐标 （x1,y1）右下坐标 num:记录黑色数目
    int x,y,x1,y1,l,num;
    string s;//命令cmd
    cin>>t;//命令数目
    while(t--)
    {
        num = 0;
        cin>>s>>x>>y>>l;
        x1 = x+l-1;
        y1 = y+l-1;
        //黑色命令，把区域内的块设置为黑色：1
        if(s.compare("BLACK")==0)
        {
            for(int i = x; i <= x1; ++i)
            for(int j = y; j <= y1; ++j)
            {
                point[i][j] = 1;
            }
        }
        //白色命令，把区域内的块设置为白色：0
        else if(s.compare("WHITE")==0)
        {
            for(int i = x; i <= x1; ++i)
            for(int j = y; j <= y1; ++j)
            {
                point[i][j] = 0;
            }
        }
        //测试命令，输出黑色块的数目
        else if(s.compare("TEST")==0)
        {
            for(int i = x; i <= x1; ++i)
            for(int j = y; j <= y1; ++j)
            {
                if(point[i][j]==1)num++;
            }
            cout<<num<<endl;
        }
    }
    return 0;
}