设 $mx$ 为最长上升子序列长度，如果输入的 $k$ 比它还大那就无解。然后如果有解，因为他要求下标字典序最小，所以只要能选靠前的就选上。因此我们需要知道每一个位置以他为开头的最长上升子序列长度。

然后每一次查询的时候，如果 $dp_i \le k$ 并且 $a_i>last$ 那么输出 $a_i$ 然后 $k$ 减一。

然后这个 $mx$ 可以直接使用二分优化的最长上升子序列。然后你发现 $dp_i$ 其实就是 $a$ 序列翻转之后以 $i$ 为结尾的最长下降子序列长度，依然使用二分来求。

代码非常丑陋，仅供参考。

#include<bits/stdc++.h>
#define int long long
#define R(x) x=read()
using namespace std;
inline int read() {
	int x=0;
	char e=getchar();
	while(e<'0'||e>'9') {
		e=getchar();
	}
	while(e>='0'&&e<='9') {
		x=(x<<1)+(x<<3)+(e^'0');
		e=getchar();
	}
	return x;
}
int n,m,a[30005];
int len[30005];
int dp[300005];
/*
dp[i]:以i为开头的往后最长的长度是多少

这个等价于求a翻转之后的以i为结尾的最长下降子序列长度。
*/
int mx;
int getmx() {
	mx=1;
	len[1]=a[1];
	for(int i=2; i<=n; ++i) {
		if(a[i]>len[mx]) len[++mx]=a[i];
		else len[lower_bound(len+1,len+1+mx,a[i])-len]=a[i];
	}
	return mx;
}
int b[30005];
void initdp() {
	int mxx=1;
	reverse(a+1,a+1+n);
	len[1]=a[1],dp[1]=1;
	for(int i=2; i<=n; ++i) {
		if(a[i]<len[mxx]) {
			len[++mxx]=a[i],dp[i]=mxx;
		} else {
			int l=1,r=mxx,mid,u=0;
			while(l<=r){
				mid=l+r>>1;
				if(len[mid]<=a[i]){
					r=mid-1;
				}else{
					u=mid;
					l=mid+1;
				}
			}
			dp[i]=u+1;
			len[u+1]=a[i];
		}
	}
	reverse(dp+1,dp+n+1);
	reverse(a+1,a+1+n);

}
signed main() {
//	freopen("ain.txt","r",stdin);
//	freopen("out.txt","w",stdout);
	R(n);
	for(int i=1; i<=n; ++i) {
		R(a[i]);
	}
	R(m);
	getmx();
	initdp();
	for(int M=1; M<=m; ++M) {
		int R(k);
		if(k>mx) {
			cout<<"Impossible\n";
			continue;
		}
		int lst=0;
		for(int i=1; i<=n; ++i) {
			if(k==0)break;
			if(dp[i]>=k&&a[i]>lst) {
				cout<<a[i]<<" ";
				lst=a[i];
				--k;
			}
		}
		cout<<"\n";
	}
	return 0;
}

思路

这个题的思路应该是比较简单

由于我们要找长度为$K$的严格上升子序列，所以我们可以想到求每个点为开头的最长严格上升子序列。

我们设$f[i]$为以$i$为开头的最长严格上升子序列的长度。

$f[n] = 0$

$f[i] = max(f[j]+1)$

$a[j] >= a[i]$

$j > i$

这个直接模拟就是$O(n^2)$的$dp$

但是显然过不去

然后考虑优化

这个应该是一个比较板的思路，就是将$a[i]$离散化，然后用树状数组维护前缀最大值即可

然后当我们有这个$f$数组之后，从前往后查就可以了

code

#include <bits/stdc++.h>
using namespace std;

const long long N = 3e4 + 10;

long long n, a[N], m, k, f[N], b[N], w;

void read() {
	cin >> n;
	a[0] = INT_MIN;
	for(long long i = 1; i <= n; i++) cin >> a[i];
	for(long long i = 1; i <= n; i++) b[i] = a[i];
	sort(b+1,b+1+n);
	w = unique(b+1,b+1+n)-b-1;
	for(long long i = 1; i <= n; i++) a[i] = lower_bound(b+1,b+1+w,a[i])-b;
}

long long t[N];

long long lb(long long x) {
	return (x & (-x));
}

void add(long long i,long long v) {
	for(; i ; i -= lb(i)) t[i] = max(t[i],v);
}

long long qry(long long i) {
	long long res = 0;
	for(; i <= w; i += lb(i)) res = max(res,t[i]);
	return res;
}

void compute() {
	for(long long i = n; i >= 1; i--) {
		f[i] = qry(a[i]+1)+1;
		add(a[i],f[i]);
	}
	cin >> m;
	for(long long i = 1; i <= m; i++) {
		cin >> k;
		for(long long i = 1, l = 0; i <= n; i++) {
			if(f[i] >= k && a[i] > a[l]) {
				l = i;
				k--;
				cout << b[a[i]] << ' ';
				if(k == 0) break;
			}
		}
		if(k) cout << "Impossible";
		cout << '\n';
	}
}

int main() {
	read();
	compute();
	return 0;
}

警钟

当时调这个题调了半天。

离散化板子

这个可以把$a$离散化

for(long long i = 1; i <= n; i++) b[i] = a[i];
	sort(b+1,b+1+n);
	w = unique(b+1,b+1+n)-b-1;
	for(long long i = 1; i <= n; i++) a[i] = lower_bound(b+1,b+1+w,a[i])-b;

树状数组

对于经典的树状数组，我们所做的修改是将点i及以后的所有点都加一个值或者说取max/min之类的，但是这个题需要将点i及以前的所有点都取max。这里给出两种做法

第一种是我们使用经典的树状数组，然后我们add的时候去add(mxn-a[i],val)，然后qry的时候qry(mxn-a[i])即可

第二种是我们更改树状数组，就是上面的code，可以去看一下，这样维护的就是前缀的最大值，然后直接取就好了

下标字典序

f[i] 表示以 a[i] 开头的最长上升子序列的长度

因为 n 最大可达 30000，所以需要 O(nlogn) 求解 f[i]