思路与算法

输入已经按 y 升序、同 y 时按 x 升序排列。处理一个点时，前面的点都不会在它上方；其中横坐标不大于当前 x 的点，恰好就是它左下方的点。用树状数组维护已出现横坐标的次数，先查询前缀计数作为等级，再把当前横坐标加入，最后输出各等级的数量。

正确性说明

任何应计入的点都有更小的 y，或相同 y 且更小的 x，因此一定已被处理。反之，已处理且 x 不大于当前值的点满足两坐标均不大于当前点，必在其左下方。树状数组返回的正是这些点的数量；查询先于插入，所以不会把当前星星自身算进去。

复杂度

横坐标上限为32000，时间 O(32001+N log 32001)，空间 O(N+32001)。

易错点

x 可以为0，树状数组下标要整体加1。同 x 和同 y 的点需要按题意计入。输出的是等级直方图，而不是每颗星星各自的等级。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> bit(32002), answer(n);
    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        ++x;
        int level = 0;
        for (int j = x; j; j -= j & -j)
            level += bit[j];
        answer[level]++;
        for (int j = x; j < (int)bit.size(); j += j & -j)
            bit[j]++;
    }
    for (int v : answer)
        cout << v << '\n';
}