思路

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

由于我们要找长度为$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，可以去看一下，这样维护的就是前缀的最大值，然后直接取就好了