题意分析

本题要求我们计算每个恒星的等级，其中等级定义为满足以下条件的恒星数量：

1. 该恒星的$Y$坐标不大于当前恒星的$Y$坐标
2. 该恒星的$X$坐标不大于当前恒星的$X$坐标

由于题目保证输入数据已按$Y$坐标升序排列，$Y$相同时按$X$升序排列，因此我们可以简化计算过程。对于第$i$个恒星，其等级等于之前所有$X$坐标不超过当前$X$的恒星数量。

解题思路

关键观察

1. 输入顺序特性：由于恒星已按$Y$升序排列，处理到第$i$颗恒星时，只需要考虑前面所有恒星的$X$坐标是否小于等于当前$X$即可
2. 高效查询：需要一种数据结构，能够高效地：
   • 查询$X$坐标小于等于当前$X$的恒星数量
   • 插入新的$X$坐标

解决方案

使用树状数组（Fenwick Tree）或线段树来维护$X$坐标的前缀和：

1. 初始化一个足够大的树状数组（考虑到$X$坐标最大为$32000$）
2. 按输入顺序处理每个恒星：
   • 查询当前$X$坐标的前缀和，即为该恒星的等级
   • 更新等级计数数组
   • 将当前$X$坐标插入树状数组

算法选择

选择树状数组的原因：

• 时间复杂度为$O(N \log M)$，其中$M$是$X$坐标的最大值（$32000$）
• 空间复杂度为$O(M)$
• 实现简单高效，适合本题数据规模

代码实现

#include<cstdio>
#include<cstring>
#define mid ((left+right)>>1)
#define lson rt<<1,left,mid
#define rson rt<<1|1,mid+1,right
using namespace std;
 
const int MAXN = 32005;
 
int sum[MAXN<<2],level[MAXN<<2];
 
void update(int rt,int left,int right,int data){
    ++sum[rt];
    if(left==right) return;
    if(data <= mid) update(lson,data);
    else update(rson,data);
}
int query(int rt,int left,int right,int l,int r){
    if(left==l && right==r) {
        return sum[rt];
    }
    int m = mid;
    if(r <= m) return query(lson,l,r);
    else if(l > m) return query(rson,l,r);
    else return query(lson,l,m)+query(rson,m+1,r);
}
 
int main(){
    int n,x,y;
    while(~scanf("%d",&n)){
        memset(sum, 0, sizeof(sum));
        memset(level, 0, sizeof(level));
        for(int i=0; i<n; ++i){
            scanf("%d%d",&x,&y);
            ++x;
            ++level[query(1,1,MAXN,1,x)];
            update(1,1,MAXN,x);
        }
        for(int i=0; i<n; ++i)
            printf("%d\n",level[i]);
    }
    return 0;
}