真是的，别人开了6个30001的int数组AC了，我开了相当于7个3010的longint数组。。正常的话应该是RE的，结果MLE了。。开成30010显然MLE了。。
话说，我写的Treap。

嗯，代码风格应该不错的吧，如果POJ不吃空格的话。
const maxn=3010;
type node=record
    d,l,r:longint;
    aux,num,cnt:integer;
  end;
var root,size:longint;
  n,m,i,j,index,u:longint;
  t:array[0..maxn]of node;
  c:array[0..maxn]of longint;
procedure update(i:longint); inline;
  begin
    t[i].num:=t[t[i].l].num+t[t[i].r].num+t[i].cnt;
  end;
procedure lrot(var i:longint); inline;
  var j:longint;
  begin
    j:=t[i].r; t[i].r:=t[j].l; t[j].l:=i; i:=j;
    update(i); update(j);
  end;
procedure rrot(var i:longint); inline;
  var j:longint;
  begin
    j:=t[i].l; t[i].l:=t[j].r; t[j].r:=i; i:=j;
    update(i); update(j);
  end;
procedure ins(var i:longint; x:longint);
  begin
    if i=0 then begin
      inc(size); i:=size;
      with t[size] do begin
        d:=x; l:=0; r:=0; num:=1; cnt:=1; aux:=random(maxint);
      end;
    end else if t[i].d=x then begin
      inc(t[i].cnt)
    end else if x<t[i].d then begin
      ins(t[i].l,x);
      if t[t[i].l].aux<t[i].aux then rrot(i);
    end else if x>t[i].d then begin
      ins(t[i].r,x);
      if t[t[i].r].aux<t[i].aux then lrot(i);
    end;
    update(i);
  end;
function askk(i,k:longint):longint;
  begin
    if k<=t[t[i].l].num then exit(askk(t[i].l,k));
    if k<=t[t[i].l].num+t[i].cnt then exit(t[i].d);
    exit(askk(t[i].r,k-t[t[i].l].num-t[i].cnt));
  end;
begin
  randomize;
  read(n,m); root:=0; size:=0;
  for i:=1 to n do read(c[i]);
  index:=0;
  for i:=1 to m do begin
    read(u);
    for j:=index+1 to u do ins(root,c[j]);
    index:=u;
    writeln(askk(root,i));
  end;
end.

• Re:不知道为什么，平衡树总是MLE >_<!! (17) skywalker_z 2012-01-31 00:30:22
• Re:不知道为什么，平衡树总是MLE >_<!! (32) HTwood 2013-04-24 21:39:34