树状数组 数星星 #10114. 「一本通 4.1 例 2」数星星 Stars Ural 1028

其实是道巧妙的题，如果你想到了的话。。。

每一颗星星需要统计它的左下方的星星个数。

我们发现题目是按照纵坐标从小到大输入的，对于相同的纵坐标是按照横坐标从小到大输入。

也就是说，我们可以不管纵坐标，按照它给出的横坐标依次插入，并统计当前星星之前的横坐标小于它的星星个数。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define N 15006
#define X 32006 

using namespace std;

inline int wread(){
	char c(getchar ());int wans(0),flag(1);
	while (c<'0' || c>'9'){if (c=='-') flag=-1;c=getchar ();}
	while (c>='0' && c<='9'){wans=wans*10+c-'0';c=getchar ();}
	return wans*=flag;
}

inline void OUT (int x){
	if (x>9)	OUT (x/10);
	putchar (x%10+'0');
}

inline void init (){
	freopen (" ","r",stdin);
	freopen (" ","w",stdout);
}

int n;
int s[X];
int pr[N];

inline int lowbit (int x){return x&(-x);}

inline void add (int pos){
	while (pos<=X-5){
		s[pos] += 1;
		pos += lowbit (pos);
	}
}

inline int fnd (int pos){
	int res(0);
	while (pos>=1){
		res += s[pos];
		pos -= lowbit (pos);
	}
	return res;
}

int main (){
//	init ();
	n=wread();
	for (int i(1);i<=n;++i){
		int x(wread()),y(wread());
		x++;
		pr[fnd (x)]++;
		add(x);
	}
	for (int i(0);i<n;++i){
		printf("%d\n",pr[i]);
	}
	return 0;
}