一開始想，总感觉是DP，但是最后什么都没想到。还暴力的交了一发。

然后開始写线段树，结果超时。感觉自己线段树的写法有问题。改天再写。先把树状数组的写法贴出来吧。

~~~~~~~~~~~~~~~~~~~~~~~~

树状数组不懂的去看刘汝佳的大白书，那个图画得非常清楚。

题目大意：星星的坐标以y递增的顺序给出，这些点的左下方的点数代表这个点的级数，问0~N-1的级数有多少个？事实上y根本木实用。

题目链接：http://poj.org/problem?id=2352

http://acm.hdu.edu.cn/showproblem.php?pid=1541

树状数组的思路在于：每一次询问，就相当于询问在1~x（包含x）间有多少个点。那么我们边读入，边更新就好。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define N 32000+10

using namespace std;

int a[N],ans[N>>1];

int lowbit(int x)

{

    return x&(-x);

}

int Sum(int x)

{

    int tot=0;

    while(x>0)

    {

        tot+=a[x];

        x-=lowbit(x);

    }

    return tot;

}

void update(int x,int v)

{

    while(x<=N)

    {

        a[x]+=v;

        x+=lowbit(x);

    }

}

int main()

{

    int n;

    while(scanf("%d",&n)!=EOF)

    {

        int x,y;

        memset(a,0,sizeof(a));

        memset(ans,0,sizeof(ans));

        for(int i=0;i<n;i++)

        {

            scanf("%d%d",&x,&y);

            x++;    //1~x的区间。

            ans[ Sum(x) ]++;

            update(x,1);  //用1来更新。

        }

        for(int i=0;i<n;i++)

            printf("%d\n",ans[i]);

    }

    return 0;

}