poj 2352 Stars

题意：
在坐标上有n个星星，如果某个星星左下位置有a个星星，就表示这个星星属于level a
星星坐标输入按照y递增，如果y相同则x递增，求出所有level水平的星星数量

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int Maxn=32005;
const int N=15005;
int Tree[Maxn*4],level[N];//分别存储每个节点区间内星星的个数以及每个等级星星的个数
void update(int l,int r,int index,int x)//更新线段树，所有包含x的区间结点值+1
{
    Tree[index]++;
    if(l==r)
        return;//找到叶子结点后返回
    else
    {
        int mid=(l+r)>>1;
        if(x<=mid)
            update(l,mid,index<<1,x);//更新左子树
        else
            update(mid+1,r,index<<1|1,x);//更新右子树
    }
}
int query(int l,int r,int index,int left,int right)//查询并返回横坐标不超过x的星星个数，即[0-x]区间内的星星个数
{
    if(l==left&&r==right)//查询区间与当前结点表示区间相同，返回当前结点值
        return Tree[index];
    else
    {
        int mid=(l+r)>>1;
        if(right<=mid)//当前结点区间大于查询区间
            return query(l,mid,index<<1,left,right);//查询左子树
        else if(left>mid)
            return query(mid+1,r,index<<1|1,left,right);//查询右子树
        else//当前结点区间与查询区间有重叠部分，分别查询左、右子树并相加（注意，查询区间也要从mid分开）
            return query(l,mid,index<<1,left,mid)+query(mid+1,r,index<<1|1,mid+1,right);
    }
}
int main()
{
    int n,y,x,m;
    cin>>n;
    memset(Tree,0,sizeof(Tree));
    memset(level,0,sizeof(level));
    for(int i=0;i<n;i++)
    {
        scanf("%d%d",&x,&y);
        update(0,Maxn,1,x);
        m=query(0,Maxn,1,0,x);
        level[m-1]++;//m-1为等级比自己低的星星个数，注意减去自身

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