1046: [HAOI2007]上升序列

Description

对于一个给定的S={a1,a2,a3,…,an},若有P={ax1,ax2,ax3,…,axm},满足(x1 < x2 < … < xm)且（ ax1 < ax2 < … < axm)。那么就称P为S的一个上升序列。如果有多个P满足条件，那么我们想求字典序最小的那个。任务给出S序列，给出若干询问。对于第i个询问，求出长度为Li的上升序列，如有多个，求出字典序最小的那个（即首先x1最小，如果不唯一，再看x2最小……），如果不存在长度为Li的上升序列，则打印Impossible.
Input

第一行一个N，表示序列一共有N个元素第二行N个数，为a1,a2,…,an 第三行一个M，表示询问次数。下面接M行每行一个数L，表示要询问长度为L的上升序列。
Output

对于每个询问，如果对应的序列存在，则输出，否则打印Impossible.
Sample Input
6
3 4 1 2 3 6
3
6
4
5
Sample Output
Impossible
1 2 3 6
Impossible
数据范围
N<=10000
M<=1000

先nlogn倒着做完最长上升，然后用一个数组b存以i为开头的最长上升子序列的长度

每个询问，从前往后扫一遍，能用就用，就是字典序最小的了（MD，一开始以为是数字最小，还排了一个序，原来是下标）

const
    maxn=10010;
var
    f,a,b:array[0..maxn]of longint;
    n,m,max:longint;
 
procedure find(x:longint);
var
    l,r,mid:longint;
begin
    l:=1;
    r:=max+1;
    while l<>r do
      begin
        mid:=(l+r)>>1;
        if f[mid]>a[x] then l:=mid+1
        else r:=mid;
      end;
    if l>max then max:=l;
    if f[l]<a[x] then f[l]:=a[x];
    b[x]:=l;
end;
 
procedure init;
var
    i:longint;
begin
    read(n);
    for i:=1 to n do
      begin
        f[i]:=-100000000;
        read(a[i]);
      end;
    for i:=n downto 1 do
      find(i);
end;
 
procedure work;
var
    i,j,x,lasta:longint;
begin
    read(m);
    for i:=1 to m do
      begin
        read(x);
        lasta:=-1000;
        if x>max then write('Impossible')
        else
          for j:=1 to n do
            if (b[j]>=x) and (a[j]>lasta) then
            begin
              dec(x);
              lasta:=a[j];
              if x>0 then write(a[j],' ')
              else write(a[j]);
              if x=0 then break;
            end;
        writeln;
      end;
end;
 
begin
    init;
    work;
end.