主席树

procedure makentree(l,r:longint);
  var
   mid,t:longint;
    begin
      inc(cnt);
      tr[cnt].z:=l;tr[cnt].y:=r;
      mid:=(l+r) div 2;
      t:=cnt;

      if l=r then exit;

      if l<=mid then
        begin
          tr[t].lc:=cnt+1;
          makentree(l,mid);
        end;
      if r>mid then
        begin
          tr[t].rc:=cnt+1;
          makentree(mid+1,r);
        end;
    end;

  procedure exptree(po,va:longint);
  var
   mid,t:longint;
    begin
      inc(cnt);
      tr[cnt].z:=tr[fol].z;
      tr[cnt].y:=tr[fol].y;
      tr[cnt].sum:=tr[fol].sum+1;
      mid:=(tr[fol].z+tr[fol].y) div 2;

      if tr[fol].z=tr[fol].y then exit;

      if va<=mid then
        begin
          tr[cnt].rc:=tr[fol].rc;
          tr[cnt].lc:=cnt+1;
          t:=fol;
          fol:=tr[fol].lc;
          exptree(tr[t].lc,va);
        end;
      if va>mid then
        begin
          tr[cnt].lc:=tr[fol].lc;
          tr[cnt].rc:=cnt+1;
          t:=fol;
          fol:=tr[fol].rc;
          exptree(tr[t].rc,va);
        end;
    end;

 cnt:=0;
    makentree(1,m);
    root[0]:=1;

    for i:=1 to n do
      begin
        root[i]:=cnt+1;
        fol:=root[i-1];
        exptree(fol,a[rk[i]]);
      end;