#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;
}

• 好象求rank时复杂度高了些啊 (1140) daringQQ 2006-12-27 17:47:17
  • 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