学步园

题目分析：一个数组中，求某个元素左边小于等于它的数的个数，记为level,  ans[level]++,按level 从0到输出他们出现次数，

代码：

#include<iostream>
#include<cstdio>
#include<memory.h>
using namespace std;

const int MAX=100000;
int ans[MAX],tree[MAX],n;
int LowBit(int x)
{
	return x&(-x);
}
int GetSum(int x)
{
	int temp=0;
	for(int i=x;i>=1;i-=LowBit(i))
		temp+=tree[i];
	return temp;
}
void UpDate(int x,int c)
{
	for(int i=x;i<=MAX;i+=LowBit(i))
        tree[i]+=c;
}
int main()
{
	while(scanf("%d",&n)!=EOF)
	{
		int x,y;
		memset(tree,0,sizeof(tree));
		memset(ans,0,sizeof(ans));
		for(int i=1;i<=n;i++)
		{
			scanf("%d %d",&x,&y);
                    ans[GetSum(x+1)]++;//因为0<=x<=32000，注意x==0，否则死循环
			UpDate(x+1,1);
		}
		for(int i=0;i<n;i++)
			printf("%d\n",ans[i]);
	}
	system("pause");
	return 0;
}