poj 2352 stars 树状数组.txt

来自「包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题」· 文本 代码 · 共 96 行

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <iostream>
#include <algorithm>
using namespace std;

//POJ 2352 Stars 树状数组
#define NMAX 32110
typedef struct point
{
	int x;
	int y;
}point;

int c[NMAX];
point star[NMAX];
int level[NMAX];
int ans[NMAX];

int getlow(int k)
{
	return k & (k ^ (k-1));
}

void add(int s,int num)
{	//往c[star[i].y]以及以后的c[]加点（加1个点）
	while(s<=NMAX)
	{
		c[s]++;
		s+=getlow(s);
	}
}

int getsum(int s)
{	//统计y=1,2....start[i].y有几个点
	int sum=0;
	while(s>=1)
	{
		sum+=c[s];
		s-=getlow(s);
	}
	return sum;
}

int cmpx(const void *a,const void *b)
{
	if((*(point *)a).x-((*(point *)b).x)==0) return (*(point *)a).y-(*(point *)b).y;
	else return  (*(point *)a).x-(*(point *)b).x;
}

void print(int num)
{
	int i;
	for(i=1;i<=num;i++)
	{
		printf("%d %d\n",star[i].x,star[i].y);
	}
}

void solve(int num)
{
	int i;
	qsort(star+1,num,sizeof(point),cmpx);
	for(i=1;i<=num;i++) 
	{
		ans[i]=level[i]=c[i]=0;
		star[i].y++;
		star[i].x++;
	}
	for(i=1;i<=num;i++)
	{
		level[i]=getsum(star[i].y);
		add(star[i].y,num);
	}
	for(i=1;i<=num;i++)	ans[level[i]]++;
}

int main()
{
	int i,num;
	while(scanf("%d",&num)!=EOF)
	{
		for(i=1;i<=num;i++)
		{
			scanf("%d %d",&star[i].x,&star[i].y);
		}
		solve(num);
		for(i=0;i<=num-1;i++)
			printf("%d\n",ans[i]);
	}
//	system("pause");
	return 0;
}