poj2828

很容易想到一种动态的做法：平衡树……

或者是二分+树状数组

但，前者编程复杂度较大，而且据说会被卡（没试过）；后者理论上超时（据说可以擦边过？）；

所以要尝试新的算法；

倒着考虑，显然最后一个对象的位置是最容易确定，顺带着，容易发现，

在第i个人后插入，就是在当前队列中前面有i个空位的空位置；

于是还是可以用平衡数……

当然更简单快捷的方法是线段树，每个节点表示这个区间还有的空位数；

然后类比平衡树的查找k大，很快就能写成

var tree:array[0..600010] of longint;
    p,a,w:array[0..600010] of longint;
    n,i:longint;

procedure build(i,l,r:longint);
  var m:longint;
  begin
    tree[i]:=r-l+1;
    m:=(l+r) shr 1;
    if l<>r then
    begin
      build(i*2,l,m);
      build(i*2+1,m+1,r);
    end;
  end;

function ask(i,l,r,k:longint):longint;
  var m:longint;
  begin
    if l=r then
    begin
      tree[i]:=0;
      exit(l);
    end;
    m:=(l+r) shr 1;
    if tree[i*2]>k then
    begin
      dec(tree[i*2]);      //在查找的过程中顺便把区间空位数更新
      exit(ask(i*2,l,m,k));
    end
    else begin
      dec(tree[i*2+1]);
      exit(ask(i*2+1,m+1,r,k-tree[i*2]));   //有没有觉得很平衡树找区间k值神似
    end;
  end;

begin
  while not eoln do
  begin
    readln(n);
    fillchar(tree,sizeof(tree),0);
    build(1,1,n);
    for i:=1 to n do
      readln(p[i],a[i]);
    for i:=n downto 1 do
      w[i]:=ask(1,1,n,p[i]);     //w代表每个点的位置
    for i:=1 to n do
      p[w[i]]:=a[i];
    for i:=1 to n do
    begin
      write(p[i]);
      if i<>n then write(' '); //注意别PE了
    end;
    writeln;
  end;
end.