> #include <stdio.h>
> #include <string.h>
> 
> #define N 2<<18
> 
> struct item
> {
>   int pos;
>   int value;
> };
> 
> struct item input[N];
> int c[N];
> int a[N];
> int n;
> 
> void init()
> {
>   memset(a,0,sizeof(a));
>   memset(c,0,sizeof(c));
> }
> 
> int low_bit(int x)
> {
>   return x&(x^(x-1));
> }
> 
> int get_sum(int x)
> {
>   int res=0;
>   
>   while (x>0) {
>     res+=c[x];
>     x-=low_bit(x);
>   }
>   return res;
> }
> 
> void add(int x)
> {
>   while (x<=n) {
>     c[x]+=1;
>     x+=low_bit(x);
>   }
> }
> 
> void solve()
> {
>   int i,v;
>   int t,temp;
> 
>   for (i=n-1;i>-1;--i) {
>     v=input[i].pos;
>     t=get_sum(v);
>     while (v+t<=n && a[v+t]) t=get_sum(v+t);
>     a[v+t]=input[i].value;
>     add(v+t);
>   }
>   for (i=1;i<=n;++i)
>     printf("%d ",a[i]);
>   putchar('\n');
> }
> 
> int main()
> {
>   int i;
> 
>   while (scanf("%d",&n)!=EOF) {
>     init();
>     for (i=0;i<n;++i) {
>       scanf("%d %d",&input[i].pos,&input[i].value);
>       input[i].pos++;
>     }
>     solve();
>   }
> 
>   return 0;
> }

• Re:好象求rank时复杂度高了些啊 (45) richardxx 2006-12-27 22:53:08
  • 你这样不是log(n)的. (47) daringQQ 2006-12-27 22:57:10
    • Re:你这样不是log(n)的. (40) richardxx 2006-12-28 20:19:55
      • 树状数组虽然方便,但是不如线段树灵活,可以用树状数组的地方都能用线段树,反之不然 (46) achilles 2006-12-28 20:21:47
        • Re:树状数组虽然方便,但是不如线段树灵活,可以用树状数组的地方都能用线段树,反之不然 (27) richardxx 2006-12-28 21:03:02
        • Re:线段树真是很灵活 (0) ecjtuxsyuan 2008-05-27 23:21:41