题目描述

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

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

1.png

例如，上图中星星 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

#include <iostream>

using namespace std;

const int X = 32000;

struct node{
    int sum, leftn, rightn;
    node *left, *right;
    node(int leftn, int rightn): sum(0), leftn(leftn), rightn(rightn), left(NULL), right(NULL){};
};

node* build(int left, int right){
    node *p = new node(left, right);
    if(left == right) return p;
    int mid = (left+right)/2;
    p->left = build(left, mid);
    p->right = build(mid+1, right);
    return p;
}

void add(node *head, int ind){
    if(head->left == head->right){
        head->sum++;
        return;
    }else if(head->left->leftn <= ind && head->left->rightn >= ind) add(head->left, ind);
    else add(head->right, ind);
    head->sum = head->left->sum + head->right->sum;
}

int sum(node *head, int ind){
    if(head->leftn == head->rightn) return head->sum;

    int ans = 0;
    if(head->left->rightn <= ind){
        ans += head->left->sum;
        if(head->right->leftn <= ind) ans += sum(head->right, ind);
    }else ans += sum(head->left, ind);

    return ans;
}

int main(){
    int n, x, y, ans[15010] = {0};
    node *head = build(0, X);
    cin >>n;
    for(int i = 0; i < n; i++){
        cin >>x >>y;
        //cout <<sum(head, x) <<endl;
        ans[sum(head, x)]++;
        add(head, x);
    }

    for(int i = 0; i < n; i++) cout <<ans[i] <<endl;
    return 0;
}