2352_stars.cpp

来自「各种算法」· C++ 代码 · 共 40 行

// 树状数组
//　输入数据己按（y->x）做基数排序
#include"iostream"
#define MAXN 15000
#define MAX	32002
using namespace std;

int c[MAX] = {0};//C[x] = A[x – 2^k + 1] + ... + A[x]
int lev[MAXN] = {0};

int lowbit(int n)
{	return n&(-n);
}
int sum(int n)//sum[n] = a[1]+ ... + a[n]
{	int r = 0;
	while(n != 0)
	{	r += c[n];
		n -= lowbit(n);
	}
	return r;
}
void change(int n,int k)
{	while(n < MAX)
	{	c[n] += k;
		n += lowbit(n);
	}
}
int main()
{	int n,x,y,i;
	scanf("%d",&n);
	for(i = 0;i < n;i++)
	{	scanf("%d%d",&x,&y);
		lev[sum(x+1)]++;
		change(x+1,1);
	}//因为按y非递减处理数据，y1<y2时，若x1>x2不会影响sum(x2,1),因为没计算到a[x1],只计算c[x1]
	for(i = 0;i < n;i++)
		printf("%d\n",lev[i]);//各level有多少个星星
	return 0;
}