Astronomers often examine star maps where stars are represented by points on a plane and each star has Cartesian coordinates. Let the level of a star be an amount of the stars that are not higher and not to the right of the given star. Astronomers want to know the distribution of the levels of the stars.
天文学家时常调查星图，星图在一个平面上表示出所有星星，而且每个星星都有笛卡尔坐标。星星的级别是不在它上面且不在它右面的星星的总数。 天文学家想知道每个星星的级别
For example, look at the map shown on the figure above. Level of the star number 5 is equal to 3 (it's formed by three stars with a numbers 1, 2 and 4). And the levels of the stars numbered by 2 and 4 are 1. At this map there are only one star of the level 0, two stars of the level 1, one star of the level 2, and one star of the level 3.
举例来说,看上面的图。 5号星星的级别是3(由 1,2 和 4 号而得)。2 点和 4 号星星的级别是 1. 在这个图里只有一个级别为 0 的星星,两个级别为 1 的星星，一个级别为 2 的星星和一个级别为 3 的星星。
You are to write a program that will count the amounts of the stars of each level on a given map.
你的任务是计算每个级别的星星总数
input：
The first line of the input contains a number of stars N (1<=N<=15000). The following N lines describe coordinates of stars (two integers X and Y per line separated by a space, 0<=X,Y<=32000). There can be only one star at one point of the plane. Stars are listed in ascending order of Y coordinate. Stars with equal Y coordinates are listed in ascending order of X coordinate.
第一行包含一个数 N (1<=N<=15000)。一下 N 行描述相应的星星(每行两个用空格隔开的整数 X 和 Y, 0<=X,Y<=32000)。平面上每个坐标最多只有一个星星。星星按 Y 的升序排列，Y 相等则按 X 的升序排列
output：
The output should contain N lines, one number per line. The first line contains amount of stars of the level 0, the second does amount of stars of the level 1 and so on, the last line contains amount of stars of the level N-1.
输出包含 N 行，每行一个数。第一行包含级别为 0 的星星的总数，第二行是级别为 1 的星星的总数，如此类推，最后一行是级别为 N-1 的星星的总数
input：
5
1 1
5 1
7 1
3 3
5 5
output：
1
2
1
1
0
【参考程序】：
#include<iostream>
using namespace std;
struct node
{
int x,y;
} point[15001];
int c[32002],level[32002];
int n;
int cmp(const void *s,const void *t)
{
node i=*(node *)s,j=*(node *)t;
if (i.x!=j.x) return i.x-j.x;
else return i.y-j.y;
}
int lowbit(int x)
{
return x^(x & (x-1));
}
int getsum(int x)
{
int sum=0;
while (x)
{
sum+=c[x];
x-=lowbit(x);
}
return sum;
}
void modify(int x)
{
while (x<=32001)
{
c[x]++;
x+=lowbit(x);
}
}
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
scanf("%d%d",&point[i].x,&point[i].y);
qsort(point+1,n,sizeof(node),cmp);
memset(c,0,sizeof(c));
memset(level,0,sizeof(level));
for (int i=1;i<=n;i++)
{
int k=getsum(point[i].y+1);
level[k]++;
modify(point[i].y+1);
}
for (int i=0;i<n;i++)
printf("%d\n",level[i]);
return 0;
}