//x从0开始，树状数组要求从一开始，故x++
//getsum(x)，求xi<x的star数
//level(sum)++,level为sum的star数++
#include <iostream>
using namespace std;
#define M 32001
int level[32005];//原数组
int c[32005];//树状数组
//k&(k^(k-1))
int getsum(int k)
{
int sum;
for(sum=0; k>0; k-=((-k)&k) ) sum+=c[k];
return sum;
}
void modify(int k, int detal) //k:position ,detal:increase value
{
for(; k<=M; k+=((-k)&k) ) c[k]+=detal;
}
int main()
{
int x,y,n,i;
while(scanf("%d", &n)!=EOF)
{
memset(c, 0, sizeof(c));
memset(level, 0, sizeof(level));
for(i=0; i<n; i++)
{
scanf("%d%d", &x, &y);
level[ getsum(++x) ] ++;
modify( x, 1);
}
for(i=0; i<n; i++)
{
printf("%d\n", level[i]);
}
}
return 0;
}
posted on 2010-03-26 22:07
wyiu 阅读(274)
评论(0) 编辑 收藏 引用 所属分类:
POJ