1541s stars.cpp

威士忌的HDU题解.大概有260多题的源码。对于学习非常有好处。

//线段树 或者 树状数组 ， 减少统计次数  
#include <stdio.h>
#include <memory.h>
const int MAXX = 32000;	//最大范围

int f[(MAXX + 1000) * 2];		//f值 //数组范围要开大点，不然就是RE或者WA 
int level[15001];		//记录各个level的星星个数

int main()
{
	int i, k, l, r, s, n, x, y, mid;
	
	while(scanf("%d", &n)==1)
	{
		memset(f, 0, sizeof(f));
		memset(level,0,sizeof(level));
		for (i = 0; i < n; i++)
		{
			scanf("%d %d", &x, &y);
			s = 0; k = 1; l = 0; r = MAXX;
			while (l < r)
			{
				mid = (l + r) / 2;			
				if (x > mid)		// 如果在右侧
					l = mid + 1 , s += f[k] , k *= 2 , k++;
				else			// 否则在左侧
					r = mid , f[k]++ , k = k * 2;
			}
			s += f[k]; f[k]++;		// 叶结点
			level[s]++;
		}
		for (i = 0; i < n; i++)		//输出
			printf("%d\n", level[i]);
	}
	return 0;
}