转载自 http://www.cnblogs.com/fenshen371/archive/2013/07/25/3214927.html
题意：已知n个星星的坐标。每个星星都有一个等级，数值等于坐标系内纵坐标和横坐标皆不大于它的星星的个数。星星的坐标按照纵坐标从小到大的顺序给出，纵坐标相同时则按照横坐标从小到大输出。 （0 <= x, y <= 32000） 要求输出等级0到n-1之间各等级的星星个数。详细信息点击进入传送门。
思路：这个题目数据的输出顺序给了很大的便利。由于是按照纵坐标从小到大输入，因此先输入的星星一定在后来的星星的下面。 根据等级的计算规则，每次输入一颗星星的坐标，只要计算出横坐标不超过它的星星个数。 在x轴上建线段树，范围从0到32000，统计横坐标出现在区间内的星星个数。假设当前输入的星星坐标为x, y， 首先查询[0, x]区间内的星星个数，即为它的等级； 然后将该星星插入线段树。
#include<stdio.h>
#include<string.h>
#define maxn 33333
#define lson l, m, rt << 1
#define rson m + 1, r, rt << 1 | 1
int sum[maxn<<], rank[maxn];
int query(int s,int l,int r,int rt)
{
if (r <= s) return sum[rt];
else if (s < l) return ;
int m = (l + r) >> ;
int ret = ;
if (s <= m) ret += query(s, lson);
else
{
ret += query(s, lson);
ret += query(s, rson);
}
return ret;
}
void PushUp(int rt)
{
sum[rt] = sum[rt<<] + sum[rt<<|];
}
void update(int s,int l,int r,int rt)
{
if (l == r && l == s)
{
sum[rt] ++;
return;
}
int m = (l + r) >> ;
if (s <= m) update(s, lson);
else update(s, rson);
PushUp(rt);
}
int main()
{
int n;
//freopen("data.in","r",stdin);
scanf("%d",&n);
memset(sum, , sizeof(sum));
memset(rank, , sizeof(rank));
for (int i = ; i < n; i++)
{
int x, y;
scanf("%d%d",&x,&y);
rank[query(x, , , )]++;
update(x, , , );
}
for (int i = ; i < n; i++)
printf("%d\n",rank[i]);
return ;
}