nlogn求出最长上升子序列长度。
对每次询问，贪心地回答。设输入为x。当前数a[i]可能成为答案序列中的第k个，则若 f[i]>=x-k && a[i]>ans[k-1] 即可。
f[i]表示以a[i]开头的最长上升子序列长度。
但这个东西难以统计。so 我们将原序列反序，求f[i] 表示以 a[i]为结尾的最长下降子序列长度即可。最后再将f、a reverse一下。
#include<cstdio>
#include<algorithm>
using namespace std;
int a[],n,m,en=,len,last;
int b[];//b[i]:将a翻转后,长度为i的最长下降子序列的末尾
int c[];//c[i]:将a翻转后,以a[i]开头的最长下降子序列的长度
bool cmp(const int &a,const int &b){return a>b;}
int main()
{
scanf("%d",&n);
for(int i=;i<=n;i++) scanf("%d",&a[n-i+]);
scanf("%d",&m);
b[]=a[]; c[]=;
for(int i=;i<=n;i++)
{
int *p=lower_bound(b+,b+en+,a[i],cmp);
if(!(*p)) ++en;
*p=a[i];
c[i]=p-b;
}
for(int i=;i<=(n>>);i++) swap(c[i],c[n-i+]),swap(a[i],a[n-i+]);
for(int i=;i<=m;i++)
{
scanf("%d",&len);
if(len>en)
{
puts("Impossible");
continue;
} last=;
for(int j=;j<=n;++j)
if(c[j]>=len&&a[j]>last)
{
printf("%d",last=a[j]);
if(!(--len))
{
puts("");
break;
} putchar(' ');
}
}
return ;
}