POJ-2352-Stars

POJ-2352-Stars
http://poj.org/problem?id=2352
n個の星の座標を与え、1つの星の左下(正左と正下を含む)にk個の星がある場合、この星はk級で、各等級に何個の点があるかを統計します.この問題は木状の配列を使用して、各星に対してy座標で小さいから大きいまで並べ替えて、同じy座標はx座標で小さいから大きいまで並べ替えます(タイトルのデータは順序付けされている)、入力順序が順序付けされている場合、星iの前のx座標がi.xに等しい星より小さいか、すなわち星iのレベルを順次統計すればよい.

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define N 35000
#define M 16000
int c[N],ans[M];
int n;
int lowbit(int x)
{
	return x&(x^(x-1));
}
void update(int p,int x)
{
	while(p<=32001)
	{
		c[p]+=x;
		p+=lowbit(p);
	}
}
int sum(int p)  //  p         
{
	int sum=0;
	while(p>0)
	{
		sum+=c[p];
		p-=lowbit(p);
	}
	return sum;
}
int main()
{
	int i,x,y;
	scanf("%d",&n);
	memset(c,0,sizeof(c));
	memset(ans,0,sizeof(ans));
	for(i=1;i<=n;i++)
	{
		scanf("%d%d",&x,&y);
		++ans[sum(x+1)];
		update(x+1,1);
	}
	for(i=0;i<n;i++)
    printf("%d
",ans[i]);
	return 0;
}