题解 P1801 【黑匣子_NOI导刊2010提高（06）】

lwhllw · 2016-11-13 21:20:57 · 题解

数结渣表示不会平衡树，不知道怎么用堆处理。

然后用数组模拟双向链表弄了一下。

正难反易，把加节点过程当成删点就很容易了。

1.离线处理，先读入所有数据。

2.排序并维护每一个节点排序后的位置。

3.最开始指向最后一个访问节点，然后用双向链表删除操作删除节点，判断一下删除的节点和当前查找的（第i小）的节点的大小关系，如果删除节点小的话，将当前查找节点指针指向更大的下一个节点(有点抽象，看代码也可以)，倒序保存答案。

const maxn=200010;
var i,j,k,l,m,n,now,link:longint;
    del,dx,d:array[1..maxn]of longint;
    a,next,pre:array[0..maxn]of longint;
    v,sp:array[1..maxn]of int64;
procedure swap(i,j:longint);
var k:int64;
begin
    k:=dx[i];dx[i]:=dx[j];dx[j]:=k;
    k:=v[i];v[i]:=v[j];v[j]:=k;
end;
procedure qsort(l,r:longint);
var i,j,x:longint;
begin
    i:=l;j:=r;x:=v[(l+r)shr 1];
    repeat
      while v[i]<x do inc(i);
      while v[j]>x do dec(j);
      if(i<=j)then
      begin
        swap(i,j);
        inc(i);
        dec(j);
      end;
    until(i>j);
    if i<r then qsort(i,r);
    if j>l then qsort(l,j);
end;
procedure init;
begin
    readln(n,m);
    for i:=1 to n do
    begin
      read(v[i]);
      dx[i]:=i;
      pre[i]:=i-1;
      next[i]:=i+1;
    end;
    for i:=1 to m do read(del[i]);
    qsort(1,n);
    for i:=1 to n do d[dx[i]]:=i;
end;
procedure work;
var i,j,k,l,r,p:longint;
begin
    now:=n;link:=m;
    for i:=m downto 1 do
    begin
      j:=del[i];
      for k:=now downto j+1 do
      begin
        l:=d[k];
        next[pre[l]]:=next[l];
        pre[next[l]]:=pre[l];
        if(v[l]<v[link])and(l<link) then link:=next[link];
        if(v[l]=v[link])and(l=link) then link:=next[link];
      end;
      now:=j;
      sp[i]:=v[link];
      link:=pre[link];
    end;
    for i:=1 to m do writeln(sp[i]);
end;
begin
    init;
    work;
end.