[原创]HDU 2642 Stars [二维树状数组]【数据结构】

2016-11-09 21:26:29 Tabris_ 阅读数：312

博客爬取于2020-06-14 22:42:41
以下为正文

版权声明：本文为Tabris原创文章，未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/53106292

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2642

-----------------------------------------------------------------------------------------.
Stars

Time Limit: 5000/2000 MS (Java/Others) Memory Limit: 32768/65536 K (Java/Others)
Total Submission(s): 1675 Accepted Submission(s): 706

Problem Description
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.

Input
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.

Output
For each query,output the number of bright stars in one line.

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

Sample Output
1
0

Author
teddy

Source
百万秦关终属楚

-----------------------------------------------------------------------------------------.

题目大意：
就是一共有M个操作
操作一共有3种
1）B x y （x，y）位置上出现星星
2）D x y （x，y）位置的星星消失了
3）Q x1 x2 y1 y1 查询矩形范围内的星星有多少个

解题思路：

思路上没有什么可说的，因为是动态的 所以必须是二维树状数组，维护即可

注意的是 ，同一坐标下最多只能有一个星星，删除的话这个坐标就没有星星了

注意 做题的时候注意下坐标的范围 ，因为是从0开始那么计算的时候所有坐标都要加1 否则的话会无限TLE

附本题代码
---------------------------------------------------------------------------------------------.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
# include <bits/stdc++.h>

# define abs(x)          (((x)>0)?(x):-(x))
# define lalal           puts("*********")
# define Rep(a,b,c)      for(int a=(b);a<=(c);a++)
# define Req(a,b,c)      for(int a=(b);a>=(c);a--)
# define Rop(a,b,c)      for(int a=(b);a<(c);a++)
# define s1(a)           scanf("%d",&a)
typedef long long int LL;
using namespace std;
/**************************************/
const int N = 1000+5;
# define lowbit(x) (x&-x)
LL sum[N][N];
bool h[N][N];

void update(int xi,int yi,int val){
    for(int i=xi;i<=N;i+=lowbit(i))
        for(int j=yi;j<=N;j+=lowbit(j))
            sum[i][j]+=val;
    return;
}

int getSum(int xi,int yi){
    int ans = 0;
    for(int i=xi;i>0;i-=lowbit(i))
        for(int j=yi;j>0;j-=lowbit(j))
            ans+=sum[i][j];
    return ans ;
}

int main(){
    int n;
    while(~s1(n)){
        memset(sum,0,sizeof(sum));
        memset(h,0,sizeof(h));
        char ch;
        int x1,y1,x2,y2;
        int tem;
        while(n--){
            getchar();
            scanf("%c",&ch);
            if('B'==ch){
                s1(x1),s1(y1);
                x1++,y1++;
                if(h[x1][y1]) continue;
                update(x1,y1,1);
                h[x1][y1]=1;
            }
            else if('D'==ch){
                s1(x1),s1(y1);
                x1++,y1++;
                if(h[x1][y1]) update(x1,y1,-1);
                h[x1][y1]=0;
            }
            else {
                s1(x1),s1(x2),s1(y1),s1(y2);
                x1++,y1++,x2++,y2++;
                if(x1>x2) swap(x1,x2);
                if(y1>y2) swap(y1,y2);
                tem=getSum(x2,y2)-getSum(x2,y1-1)-getSum(x1-1,y2)+getSum(x1-1,y1-1);
                printf("%d\n",tem);
            }
        }
    }
    return 0;
}