poj2182

首先容易知道，最后一个数是最容易确定的，于是从后往前确定

对于位置j，它的数就是1~n中剩余数的第a[j]+1小的数

这当然可以用平衡数做，复杂度为O(nlogn)

有没有更简洁得算法？树状数组+二分

var v:array[0..8010] of boolean;
    c,ans,a:array[0..8010] of longint;
    i,j,n:longint;
function lowbit(x:longint):longint;
  begin
    exit(x and (-x));
  end;

function sum(x:longint):longint;
  begin
    sum:=0;
    while x>0 do
    begin
      sum:=sum+c[x];
      x:=x-lowbit(x);
    end;
  end;

function kth(t:longint):longint;
  var l,r,m,p:longint;
  begin
    l:=1;
    r:=n;
    while l<=r do
    begin
      m:=(l+r) shr 1;
      p:=sum(m);       //统计二分得到的这个数前面有几个比它小的
      if (p=t) and not v[m] then exit(m);   //注意不要忘记判断这个数是否存在
      if p<t then l:=m+1 else r:=m-1;
    end;
  end;

procedure add(x,w:longint);
  begin
    while x<=n do
    begin
      c[x]:=c[x]+w;
      x:=x+lowbit(x);
    end;
  end;

begin
  readln(n);
  for i:=2 to n do
    readln(a[i]);
  for i:=1 to n do    //初始化
    add(i,1);
  fillchar(v,sizeof(v),false);
  for i:=n downto 1 do
  begin
    ans[i]:=kth(a[i]+1);  //确定当前位置
    v[ans[i]]:=true;      //删除这个数
    add(ans[i],-1);
  end;
  for i:=1 to n do
    writeln(ans[i]);
end.

总的复杂度为O(n*logn*logn）虽然慢了一点，但是编程复杂度大大下降