[原创]HDU 1542 Stars [树状数组]【数据结构】

2016-11-07 21:24:45 Tabris_ 阅读数：404

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

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

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1541
-----------------------.
Stars

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 8916 Accepted Submission(s): 3547

Problem Description
Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.

For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it’s formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.

You are to write a program that will count the amounts of the stars of each level on a given map.

Input
The first line of the input file contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.

Output
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.

Sample Input
5
1 1
5 1
7 1
3 3
5 5

Sample Output
1
2
1
1
0

Source
Ural Collegiate Programming Contest 1999

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

题目大意 ：
就是求左下角有多少个星星的星星的个数

解题思路 ：
就是一个基本的数据结构
树状数组和线段树都可做
我用的树状数组AC的 闲来无事复习一下也是有收获的 维护的时候i<=maxn 而不是树状数组的长度 。。 很强势 也怪当初没有好好学习树状数组就去搞线段树了。。然后做了几天就放弃数据结构了 看来这的要好好学习数据结构了。。。

仔细读题 发现y是递增的 这样的话 y值就没什么用了 我们只要维护x就可以了 维护前用桶记录一下就可以了;;

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

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
# include <bits/stdc++.h>
using namespace std;
/**************************************/
const int N = 50000 + 5;
# define lowbit(x)  (x&(-x))
int sum[N],cnt,nnn[N];
void update(int index,int val){
    for(int i=index;i<=N;i+=lowbit(i)){
        sum[i]+=val;
    }
}

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

int main()
{
    while(~scanf("%d",&cnt)){
        int x,y;
        memset(sum,0,sizeof(sum));
        memset(nnn,0,sizeof(nnn));
        for(int i=0;i<cnt;i++){
            scanf("%d%d",&x,&y);
            nnn[getSum(x+1)]++;
            update(x+1,1);
        }
        for(int i=0;i<cnt;i++){
            printf("%d\n",nnn[i]);
        }
    }
    return 0;
}