「题解」数星星 Stars

(未完待续)

题目链接:Ural 1028/POJ 2352/LibreOJ 10114/信息学奥赛一本通 T1536

题目

题目描述

给定 $n$ 个点,定义每个点的等级是在该点左下方(含正左、正下)的点的数目,试统计每个等级有多少个点。

数据范围

变量数据范围
$N$$1\leq N\leq 1.5\times 10^4$
$x,y$$0\leq x,y\leq 3.2\times 10^4$

题解

思路

显然,我们把每一个点的贡献设为 $1$,那么贡献数组的前缀和就是左边有多少星星,可用树状数组求。

时间复杂度为 $\Theta(n\log _ 2n)$。

代码

注意一个实现细节,树状数组不能使用数组的零下标,而本题的坐标从零开始。

#include<cstdio>
#include<algorithm>
using std::max;
//以上为头文件
const int MAXN=15000+5; //N 最大的范围
const int MAXXY=32000+5; //坐标的最大范围
struct TreeArray{//树状数组模板
    #define lowbit(x) ( (x) & ( - (x) ) ) //宏定义 lowbit(x)
    int n,unit[MAXXY];
    void Update(int ID,int val){
        while(ID<=n){
            unit[ID]+=val;
            ID+=lowbit(ID);
        }
        return;
    }
    int Query(int ID){
        register int sum=0;
        while(ID){
            sum+=unit[ID];
            ID-=lowbit(ID);
        }
        return sum;
    }
    #undef lowbit //取消宏定义 lowbit(x)
};
int n,Max;
int x[MAXN];
int ans[MAXN];
TreeArray T;
int main(void){
    register int i;
    scanf("%d",&n);
    for(i=1;i<=n;++i){
        scanf("%d%*d",&x[i]);
        ++x[i]; //树状数组不能使用数组的零下标
        Max=max(Max,x[i]);
    }
    T.n=Max;
    for(i=1;i<=n;++i){
        ++ans[T.Query(x[i])];
        T.Update(x[i],1);
    }
    for(i=0;i<n;++i)
        printf("%d\n",ans[i]); //输出答案
    return 0;
}