树状数组 HDOJ 1541 Stars

#include <iostream>
#include <sstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <bitset>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <climits>
#define maxn 32005
#define eps 1e-7
#define mod 1000000007
#define INF 99999999
#define lowbit(x) (x&(-x))
typedef long long LL;
using namespace std;

int tree[maxn];
int hash[maxn];
int n;
void add(int x)
{
	for(int i=x;i<maxn;i =lowbit(i)) tree[i] =1;
}
int sum(int x)
{
	int i, ans=0;
	for(i=x;i>0;i-=lowbit(i)) ans =tree[i];
	return ans;
}
int get(void)
{
	int tmp=0;
	char ch=getchar();
	while(ch!=' ' && ch!='\n')
		tmp=tmp*10 ch-'0', ch=getchar();
	return tmp;
}
int main(void)
{
	int i, x, y;
	while(scanf("%d",&n)!=EOF){
		getchar();
		memset(tree, 0, sizeof tree);
		memset(hash, 0, sizeof hash);
		for(i=0;i<n;i  ){
			//scanf("%d%d",&x,&y);
			x=get();
			y=get();
			x  , y  ;
			hash[sum(x)]  ;
			add(x);
		}
		for(i=0;i<n;i  ) printf("%d\n", hash[i]);
	}
}