Stars
Time Limit: 1000MS Memory Limit: 65536K
Total Submissions: 60334 Accepted: 25685

Description

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.

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 file 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.

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.

Sample Input

5
1 1
5 1
7 1
3 3
5 5

Sample Output

1
2
1
1
0
Hint

This problem has huge input data,use scanf() instead of cin to read data to avoid time limit exceed.

题目大意：
给你n个坐标在直角坐标系中，且坐标先按y升序后按x升序，对于一个坐标如果它左下角的坐标个数给n，就定义这个坐标的级别为n，最终要从级别0到n-1分别输出它们的个数。

思路：
这个题，我看了几天，实在是不知道和树状数组有啥关系（鸟玩意啊！！！），然后今天在做 Japan 这道题没做出来，又转回来看了这道题，突然就会做了（难度是japan那道题开阔了我的思路？虽然那道题还没ac），这个题目中给出了一个很重要的信息就是y坐标是升序的，也就是说对于一个点(x,y)只要在他之前的点中x小于它，那么他们一定在当前这个点左下角，因为y是升序，这个点越来越高，那肯定只需要确定x坐标就行了，那么这个问题就变成了，给你n个点，要你分别统计小于每个点的x坐标的数量。拿样例说，(1,1)最小前面肯定没有比他小的x坐标,(5,1)前面有x=1,(7,1)前面有(5,1),(1,1)，然后等等，这个时候我们需要一个数据结构每次给我一个点我能在O(logn)的时间复杂度内求出这个点之前有多少个点，以及插入这个点在O(logn)时间复杂度以下，那么树状数组可以完成这个使命，来一个点我查询在它之前有多少个点，然后把这个点再***来，继续查询，并且复杂度都是O(logn)，然后这道题就可以ac了。值得注意的是因为x,y可以取0,而0&-0还是等于0,会导致add函数陷入死循环，所以可以将x全部偏移一个常量1就可以解决了。
AC代码：

#include<iostream>
#include<cstdio>
using namespace std;

const int maxn=1e5+10;
int N;
int ans[maxn];
int sum[32005];
int query(int x){
	int s=0;
	for(;x;x-=(x&-x)){
		s+=sum[x];
	}
	return s;
}
void add(int x,int v){
	for(;x<=32005;x+=(x&-x)){
		sum[x]+=v;
	}
}
int main(){
	int x,y;
	scanf("%d",&N);
	for(int i=1;i<=N;i++){
		scanf("%d%d",&x,&y);
		x++;
		ans[query(x)]++;
		add(x,1);
	}
	for(int i=0;i<N;i++){
		printf("%d\n",ans[i]);
	}
}