题目大意

由于本题输入数据很特殊，所以其实等价于求一下，到目前的输入为止，有多少个星星的 x 值小于等于该星星的 x 就可以了，这就代表该星星的等级。

由于该题y不递减的输入特性，导致了y在题目中毫无作用。

所以我们只需要实时更新一下我们的树状数组就可以了。

如何更新？

这个题目本身就是一道利用前缀和思想做的题目。就和开头所说过的一样，只要求出有多少个星星的 x 值不小于该星星的 x 值就可以了，而这个过程就是利用的前缀和。

那让我们先用前缀和的思想来看一下这道题目。

假设现在存在一个前缀和数组 sum ，那么每当我们输入一个 x 的时候，我们都需要把 x 后面（包含x）的所有前缀和都加上 1 ，(因为在 x 后面的数都比 x 大，所以需要更新后面所有的前缀和)。然后我们在每次输入 x 的时候都实时更新一下前缀和并且实时计算一下我们的星星的等级就可以了。

这里为什么要强调实时计算星星等级的值呢？

因为我们这种操作方法是忽略了 y 的，之所以可以忽略 y 是因为题目输入的原因，所以其实我们是利用了这一特性来简化我们的算法的。其实如果这道题目输入的 y 并不按照不降原则来输入的话，那么这种算法就不对了。

现在说明一下为什么要实时计算，因为后面输入的 x 值很可能比我们前面输入的 x 值要小，因为数据输入的是按y不降输入的，而 x 可以是任意的，如果我们不实时计算，而是等到全部处理完再计算的话，会导致 “x 虽然比你大但是 y 比你小的情况”，而这种情况是显然不符合我们的题意的，所以说我们这种利用前缀和的算法是很特殊的，是仅仅针对于这个题目的。

正如 y 总所说的，能用到数据结构的算法的题目，往往是根据数据结构的特性来决定的。比如这个题目我们为什么要用树状数组来处理？是因为我们这里要运用前缀和，以及更新前缀和，而这恰好符合树状数组的特性，所以我们利用了它。

所以本题的思考思路总结应该是：

1、分析题目，通过输入特性判断解题方法

2、想想暴力解法怎么做？利用前缀和，每次用O(n)的时间复杂度更新前缀和

3、想想是否能优化？

4、想到树状数组优化

5、利用树状数组解决题目

本题最应该收获的东西

其实这道题目对于我们这些刚入门数据结构相关算法的同学，不光是对于树状数组算法的一种训练，更多的是对于数据结构算法的理解运用，我们该如何运用数据结构？我们什么时候利用数据结构？

数据结构算法不是说我们拿到一个题目就往数据结构算法想，而往往是通过传统暴力的思路分析，然后再想到用我们的数据结构能够优化我们的暴力算法。

其实每一个题目都是这样，重要的不是这个题目的答案，而是解决的这道题的算法思想，以及思维方式。

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>

using namespace std;

const int N=50010;//个人喜欢开大一点数组

int n;

int ans[N];//这个数组使用来存各个等级的星星数的，而不是之前的那个原始数组哦！

int c[N];//树状数组

int lowbit(int x)//-x=(~x+1) 也就是x的每一位二进制数先取反，然后再加上 1
{
    return x&-x;
}

void add(int x,int v)//这个函数用于更新 c 数组
{
    for(int i=x;i<=32001;i+=lowbit(i))c[i]+=v;//更新一下树状数组
}

int query(int x)//这个函数用于计算前缀和
{
    int res=0;

    for(int i=x;i>0;i-=lowbit(i))res+=c[i];//计算一下前缀和

    return res;
}

int main()
{
     scanf("%d",&n);

    for(int i=1;i<=n;i++)
    {
         int x,y;

        scanf("%d%d",&x,&y);//其实这里 y 并没有什么用

        x++;/*为了防止出现0的情况，给它全体横坐标加上 1 就好了。
        这其实是一个很小的细节，作者但是做的时候没考虑到然后就wa了，而给每个 x 都加上 1 并不会影响结果*/


         add(x,1);//更新一下树状数组，每次都给 x 后面的数据加上 1 

         ans[query(x)]++;/*然后查一下它的前缀和是多少，前缀和是多少就意味着是多少级
         这是一个动态变化的过程，而且后面的一定比前面高
         所以要实时计算*/


     }

     for(int i=1;i<=n;i++)
     {
         printf("%d\n",ans[i]);//输出每一个等级的数量
     }

    return 0;
}