Stars（线段树）

Stars

Time Limit: 1000MS		Memory Limit: 65536K
Total Submissions: 27333		Accepted: 11958

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（1到15000）颗星星，给出每颗星星的x,y（0到32000）坐标。星星以y的递增顺序输入，如果y相等就以x递增的顺序输入。每颗星星都有一个等级，这个等级数是这颗星星左下位置的星星数量，最终统计每一层等级（0到N-1）的数量。

 

       思路：

       有一个关键的条件，星星以y的递增顺序输入，如果y相等就以x递增的顺序输入。这样的话，就是说明每输入一颗星星A，这个星星A一定是最高的，但是不一定是最右边的，在以后的每次输入中，不会再有一颗星星B会出现在这颗星星A的左下位置处，因为星星B一定要比A高，但是比A高不一定会在A的右边，但是无论B在左边还是右边，可以确定的一定是B肯定要比A高，那么就可以确定以后的每一颗星星B都不会出现在A的左下位置处，这就说明A的等级不会因为后面出现的星星而改变。

        所以，先找出全部星星x坐标的最小值min和最大值max，以[min，max]为界来建立线段树。每次输入一颗星星之前，先统计在[min,x]中有几颗星星，这个星星数就是它的等级数，统计之后再插入这颗星星的x坐标于线段树中。

 

       AC：

#include<stdio.h>
#include<string.h>
#define M (32000+5) //易错点
typedef struct
{
	int l;
	int r;
	int sum;
}node;
node no[M*4];
int x[M],y[M];
int fin[M],t;

void build(int from,int to,int i)
{
	int mid=(from+to)/2;
	no[i].l=from;
	no[i].r=to;
	no[i].sum=0;
	if(from==to) return;
	build(from,mid,2*i);
	build(mid+1,to,2*i+1);
}

void add(int i,int a)
{
	int mid=(no[i].l+no[i].r)/2;
	if(no[i].l==no[i].r)
	{
		no[i].sum++;
		return;
	}
	if(a<=mid)	 add(2*i,a);
	if(a>=mid+1) add(2*i+1,a);
	no[i].sum=no[2*i].sum+no[2*i+1].sum;
}

void find(int from,int to,int i)
{
	int mid=(no[i].l+no[i].r)/2;
	if(from==no[i].l&&to==no[i].r)
	{
		t+=no[i].sum;
		return;
	}
	if(from>=mid+1) find(from,to,2*i+1);
	if(to<=mid)		find(from,to,2*i);
	if(from<=mid&&to>=mid+1)
	{
		find(from,mid,2*i);
		find(mid+1,to,2*i+1);
	}
}

int main()
{
	int n;
	int min,max;
	while(scanf("%d",&n)!=EOF)
	{
		min=M,max=-1;
		for(int i=1;i<=n;i++)
		{
		 scanf("%d%d",&x[i],&y[i]);
		 if(x[i]>max) max=x[i];
		 if(x[i]<min) min=x[i];
		}
		
		build(min,max,1);
		memset(fin,0,sizeof(fin));
		
		for(int i=1;i<=n;i++)
		{
		 t=0;
		 find(min,x[i],1);
		 fin[t]++;
		 add(1,x[i]);
		}
		for(int i=0;i<=n-1;i++)
		 printf("%d\n",fin[i]);
    }
	return 0;
}

       

       总结：

       1.题目是多输入；

       2.RE了N次，是因为#define M (32000+5)。一开始写成了#define M 32000+5，因为后面数组的大小是M*4，这样的话就是32000+5*4。而事实上我想要的结果是（32000+5）*4，所以要加括号。要细心。