「POJ2352」Stars

这道题没想象那么难，其实就是一个极其简单的对树状数组的运用。

可能一开始看到题目要求的是左下方的星星，你可能会立刻想到用二维树状数组，但是请你不要像我这么浮躁，认真看完题目。

注意，每一个点上只有一个星星，按 $Y$ 的升序给出坐标，如果 $Y$ 相同，则按照 $X$ 的升序给出！！！

这就说明，后面的星星等级肯定比前面的星星等级高 $1$ 级，因为后面的星星的左下角的星星是包含前面的星星左下方的星星的，但是后面的星星要多一颗，因为前面的星星在后面的星星的左下方。

这就可以直接用一维的树状数组处理了。

直接按次序插入，因为 $Y$ 是按升序给出，所以不管 $Y$，将 $X$ 插入到树状数组中，进行一次求前缀和，就可以知道它的等级，然后用一个数组记录一下每个等级的星星数，就完了。

这道题很有趣，它通过排序将一个用二维的题降到了一维，这其实是一个很重要的思想。CDQ 分治也可以做这道题，但这里不再多讲。

如果这道题不按 $Y$ 的升序来输入，则就是一个裸的二维偏序问题，是三维偏序问题的基础，而三维偏序又是 CDQ 算法的板子题，所以这道题当然可以用 CDQ 分治秒解了

#include<stdio.h>
#include<string.h>
int e[50001],a[50001],n;
int lowbit(int x)
{
    return (-x)&x;
}
void add(int x,int t)
{
    while(x<=50001)
    {
        e[x]+=t;
        x=x+lowbit(x);
    }
}
int sum(int x)
{
    int s=0;
    while(x>0)
    {
        s+=e[x];
        x-=lowbit(x);
    }
    return s;
}
int main()
{
    int i,j;
    int x,y;
    scanf("%d",&n);
    for(i=1;i<=n;i++)
    {
        scanf("%d%d",&x,&y);
        add(x+1,1);
        a[sum(x+1)]++;//这里加1是因为如果x输入为0，lowbit(0)=0，则在更新时更新不了，所以加1
    }
    for(i=1;i<=n;i++)
        printf("%d\n",a[i]);
    return 0;
}