算法1

思路：树状数组做法，三个函数背过!!

这个题第一遍读的时候想着二维数组，但是发现用树状数组做更简单，在直角坐标系下，求出小于等于某一列的所有行数存在的星星，比如图示在第五行，下标为5的星星，他的列数是3，用tr[i] 表示这一行有星星就自加，一个求前缀和的过程，level[query(x)];求出每一级相加之后的和，这里处理的是相当妙啊

C++ 代码

#include<iostream>
#include<cstdio>

using namespace std;

const int N=32010;

int n;
int tr[N],level[N];//level表示每一级里面星星的个数
int lowbit(int x){
    return x&-x;

}

void add(int x){
    for(int i=x;i<N;i+=lowbit(i))tr[i]++;
}
int query(int x){

    int res=0;
    for(int i=x;i;i-=lowbit(i))res+=tr[i];
    return res;
}
int main(){

    scanf("%d",&n);
    for(int i=0;i<n;i++){
        int x,y;

        scanf("%d%d",&x,&y);//因为树状数组的下标是从1开始的，但是题目上面x是从0开始的，所以要x++
        x++;
        level[query(x)]++;//!!
        add(x);
    }
    for(int i=0;i<n;i++)printf("%d\n",level[i]);

    return 0;
}