这道题的题意就是，告诉你一些点，然后你要在这些中计算一个题目定义的level值。所谓level值就是它左边和左下角和正下边点的颗数。然后分别输出每个level级对应的点的个数。

现在告诉我们若干颗星星的坐标，题目输入描述中明确告诉我们，输入的坐标是按Y的升序、如果Y相等，则按X的升序。所以我们发现我们可以完全忽略Y，只要统计小于本身X的level值，就是level了。对于每一颗星，它的等级数等于它左边和左下角和正下边的星星的颗数。最后问每一颗星星的等级。把星星按照给我们的顺序（就是y坐标从小到大的顺序），依次把一个数组中下标为x的元素加1（上面因为树状数组是从1开始计数的，而坐标有可能为0，所以我们统一都加1）。对于某一颗星，坐标为x，那么把数组中下标为x及之前的所有元素相加，就是求了这颗星左边及左下角及正下边的星星数（read函数就是把1~n(左+左下+正下)的值都加起来了），然后再把下标为x的元素加1。（这颗星星本身不能算进去）因为每个x,y都是按升序输入的，因此当前输入只与之前输入有关而无需等输入完再进行处理，单点更新等特性符合树状数组的一类用法。

这样对于X坐标为j的star，他得level为：level=a[0]+a[1]+a[2]+…+a[j]。如果这样计算的话，每个level最坏时间要用O(m)，计算n-1个level，这样要用O(mn)的时间复杂度，对于这题的数据而言，这无疑是无法接受的。我们发现，对于计算level，这是个查询区间问题sum[0,j], 如果没有元素的变更(既数组a是不变的),我们完全可以存储sum[0,k](k=0,2,……),然后对任意给定的查找区间[i,j],都可以方便的用ans=sum[1,j]-sum[1,i-1],当然这只是没有元素改变的情况下的比较优化的解法.那么对于有元素变更的问题是否有更高效的方法呢?这让我们想到的树状数组。套用模版即可。也可以用线段树做。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
#define MAX 32000+5
int n;
int tree[MAX];
int level[MAX];

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

void add(int k,int num)    
{    
    while(k<=MAX-4)  //n是树状数组的大小  
    {    
        tree[k]+=num;    
        k+=lowbit(k);    
    }    
}   

int read(int k)//1~k的区间和    
{    
    int sum=0;    
    while(k)    
    {    
        sum+=tree[k];    
        k-=lowbit(k);    
    }    
    return sum;    
}   


int main()
{
	//freopen("in.txt","r",stdin);  
    while (~scanf("%d", &n))  
    {
    	int x,y;
    	memset(tree,0,sizeof(tree));
    	memset(level,0,sizeof(level));
    	for(int i=1;i<=n;i++)
    	{
    		scanf("%d%d",&x,&y);
    		x++;
            int ans = read(x); 
			//求这颗星左边及左下角及正下边的星星数
            level[ans]++; // 
            add(x, 1);   		
    	} 
	    for (int i = 0; i < n; i++)  
        printf("%d\n", level[i]);  
 
    }
	return 0;	
}