题目 数星星

题目来源 《信息学奥赛一本通》 , Ural 1028

算法标签 树状数组

题目描述

天空中有一些星星，这些星星都在不同的位置，每个星星有个坐标。

如果一个星星的左下方（包含正左和正下）有 k 颗星星，就说这颗星星是 k 级的。

例如，上图中星星 5 是 3 级的（1,2,4 在它左下），星星 2,4 是 1 级的。

例图中有 1 个 0 级，2 个 1 级，1 个 2 级，1 个 3 级的星星。

给定星星的位置，输出各级星星的数目。

换句话说，给定 N 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

输入格式

第一行一个整数 N，表示星星的数目；

接下来 N 行给出每颗星星的坐标，坐标用两个整数 x,y 表示；

不会有星星重叠。星星按 y 坐标增序给出，y 坐标相同的按 x 坐标增序给出。

输出格式

N 行，每行一个整数，分别是 0 级，1 级，2 级，……，N−1 级的星星的数目。

数据范围

1≤N≤15000,
0≤x,y≤32000

输入样例：

5
1 1
5 1
7 1
3 3
5 5

输出样例：

1
2
1
1
0

时间复杂度

o(nlogn)

思路

给定星星的位置，输出各级星星的数目。

换句话说，给定 N 个点，定义每个点的等级是在该点左下方（含正左、正下）的点的数目，试统计每个等级有多少个点。

意思就是，给出每个级星星的数目，那我们就需要统计不同星星的级别。

不会有星星重叠。星星按 y 坐标增序给出，y 坐标相同的按 x 坐标增序给出。

又因为 Y，x靠y增序，不重合，则相当于一层一层堆砌。
从这种方式来说，我查询当前star(x,y)等级，相当于查询1到x的区间内一共有多少个star，不用考虑y的高度，因为一定是当前最高的!

问题转换为了求1—x一共有多少个star！
且这种方式其实同时满足树状数组的区域查询和点状更改。

C++ 代码

#include<iostream>

using namespace std;
const int N=1e5+10;
int s[N],level[N];

int n;
int lowbit(int x){return x&-x;}
int add(int x,int y){for(int i=x;i<=N;i+=lowbit(i))s[i]+=y;}//注意到N
int sum(int x){
    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=s[i];
    return res;
}
int main()
{
    cin>>n;

    int x,y;
    for(int i=0;i<n;i++)
        {
            cin>>x>>y;

            x++;//树状数组必须从1开始
            level[sum(x)]++;//统计范围内有多少星星然后加上自身
            add(x,1);
        }

    for(int i=0;i<n;i++)cout<<level[i]<<endl;//输出每个等级的情况

    return 0;
}