首页 > ACM题库 > HDU-杭电 > hdu 2642 Stars-树状数组-[解题报告]C++
2014
02-12

hdu 2642 Stars-树状数组-[解题报告]C++

Stars

问题描述 :

Yifenfei is a romantic guy and he likes to count the stars in the sky.
To make the problem easier,we considerate the sky is a two-dimension plane.Sometimes the star will be bright and sometimes the star will be dim.At first,there is no bright star in the sky,then some information will be given as "B x y" where ‘B’ represent bright and x represent the X coordinate and y represent the Y coordinate means the star at (x,y) is bright,And the ‘D’ in "D x y" mean the star at(x,y) is dim.When get a query as "Q X1 X2 Y1 Y2",you should tell Yifenfei how many bright stars there are in the region correspond X1,X2,Y1,Y2.

There is only one case.

输入:

The first line contain a M(M <= 100000), then M line followed.
each line start with a operational character.
if the character is B or D,then two integer X,Y (0 <=X,Y<= 1000)followed.
if the character is Q then four integer X1,X2,Y1,Y2(0 <=X1,X2,Y1,Y2<= 1000) followed.

输出:

The first line contain a M(M <= 100000), then M line followed.
each line start with a operational character.
if the character is B or D,then two integer X,Y (0 <=X,Y<= 1000)followed.
if the character is Q then four integer X1,X2,Y1,Y2(0 <=X1,X2,Y1,Y2<= 1000) followed.

样例输入:

5
B 581 145
B 581 145
Q 0 600 0 200
D 581 145
Q 0 600 0 200

样例输出:

1
0

点击打开hdu 2642

思路: 二维树状数组

分析: 裸题


代码:

 

/************************************************
 * By: chenguolin                               * 
 * Date: 2013-08-21                             *
 * Address: http://blog.csdn.net/chenguolinblog *
 ***********************************************/
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 1010;

int m;
int num[MAXN][MAXN];
int treeNum[MAXN][MAXN];

int lowbit(int x){
    return x&(-x);
}

int getSum(int x , int y){
    int sum = 0;
    for(int i = x ; i > 0 ; i -= lowbit(i))
        for(int j = y ; j > 0 ; j -= lowbit(j))
            sum += treeNum[i][j];
    return sum;
}

void add(int x , int y , int val){
    for(int i = x ; i < MAXN ; i += lowbit(i))
        for(int j = y ; j < MAXN ; j += lowbit(j))
            treeNum[i][j] += val;
}

void solve(){
    memset(num , 0 , sizeof(num));
    memset(treeNum , 0 , sizeof(treeNum));
    char c;
    int x , y , val;
    int x1 , x2 , y1 , y2;
    int x3 , x4 , y3 , y4;
    while(m--){
         scanf("%c" , &c); 
         if(c == 'B'){
             scanf("%d%d%*c" , &x , &y);
             x++ , y++;
             val = num[x][y] ? 0 : 1;
             if(val)
                 add(x , y , val);
             num[x][y] = 1;
         }
         else if(c == 'D'){
             scanf("%d%d%*c" , &x , &y);
             x++ , y++;
             if(num[x][y])
                add(x , y , -1);
             num[x][y] = 0;
         }
         else{
             scanf("%d%d" , &x1 , &x2);
             scanf("%d%d%*c" , &y1 , &y2);
             x1++ , x2++ , y1++ , y2++;
             x3 = min(x1 , x2) , y3 = min(y1 , y2);
             x4 = max(x1 , x2) , y4 = max(y1 , y2);
             int ans = getSum(x4 , y4);
             ans -= getSum(x3-1 , y4);
             ans -= getSum(x4 , y3-1);
             ans += getSum(x3-1 , y3-1);
             printf("%d\n" , ans);
         }
    }
}

int main(){
    while(scanf("%d%*c" , &m) != EOF)
          solve(); 
    return 0;
}

解题转自:http://blog.csdn.net/chenguolinblog/article/details/10147959


  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks

  2. I go through some of your put up and I uncovered a good deal of expertise from it. Many thanks for posting this sort of exciting posts

  3. 如果两个序列的最后字符不匹配(即X [M-1]!= Y [N-1])
    L(X [0 .. M-1],Y [0 .. N-1])= MAX(L(X [0 .. M-2],Y [0 .. N-1]),L(X [0 .. M-1],Y [0 .. N-1])
    这里写错了吧。