//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 閱讀(348)
評論(0) 編輯 收藏 引用 所屬分類:
POJ