HDU1541 Stars【树状数组板子题】

Stars

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

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

Recommend

LL | We have carefully selected several similar problems for you: 1166 1394 3450 1542 1255

题意 ： 按照y的从小到大给你一些点的坐标，让你求除本身外包含在和坐标轴包含的矩形中点的个数的映射值.

分析： 怎么说呢，例如样例，那里面1个点包含0个点，有1个点包含1个点，然后有两个点包含2个点的。。，暴力维护前缀和的话复杂度是O(n^2)，我们恰好利用树状数组的特性，记录下sum数组，因为里面有包含x等于0的点，但是树状数组是从坐标1开始的，我们将所有点向右平移一位即可

参考代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

int a[maxn],sum[maxn];

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

int down(int x) {
    int res = 0;
    while(x > 0) {
        res += a[x];
        x -= lowbit(x);
    }
    return res;
}

void up(int x) {
    while(x < maxn) {
        a[x]++;
        x += lowbit(x);
    }
}
void init() {
    memset(a,0,sizeof a);
    memset(sum,0,sizeof sum);
}
int main(){
    ios_base::sync_with_stdio(0);
    int n;
    while (cin>>n) {
        init();
        for(int i = 0;i < n;i++) {
            int x,y;cin>>x>>y;
            x++;
            sum[down(x)]++;
            up(x);
        }
        for(int i = 0;i < n;i++) {
            cout<<sum[i]<<endl;
        }
    }
    return 0;
}

• 如有错误或遗漏，请私聊下UP，thx

最后

以上就是仁爱白开水为你收集整理的HDU1541 Stars【树状数组板子题】的全部内容，希望文章能够帮你解决HDU1541 Stars【树状数组板子题】所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。