CF568E Longest Increasing Subsequence 题解

CF568E Longest Increasing Subsequence

题意

• 给定一个长度为 $n$ 的有 $k$ 个空缺的序列。
• 你有 $m$ 个数可以用于填补空缺。
• 要求最大化最长上升子序列的长度。
• $n, m \le 10^5$，$k \le 10^3$。

题解

首先，由于多次填同一个数并不会在同一个上升子序列中，因此对答案没有贡献，所以我们可以先不考虑每个数只能填一次的条件。

设 $l_i, p_i$ 分别表示在 $i$ 不是空缺的位置时，$1\sim i$ 中包含 $i$ 的最长上升子序列的长度和上一项的位置。

设 $f_i, g_i$ 分别表示长度为 $i$ 的上升子序列的最后一项的最小值和它所在的位置。

从前往后考虑每一个位置，设此时考虑到位置 $i$。

若该位置不是空缺的，设该位置上的数为 $x$，那么可以在 $f$ 上二分找到 $<x$ 的最大的 $f_j$，然后依次更新 $l_i = j + 1$，$p_i = g_j$，$f_{j+1} = x$，$g_{j+1} = i$。

若该位置是空缺的，考虑从大到小枚举用于填补空缺的数，设枚举到的数为 $x$，同样可以在 $f$ 上二分找到 $<x$ 的最大的 $f_j$，然后依次更新 $f_{j+1} = x$，$g_{j+1} = i$。这样的时间复杂度为 $\mathcal O(mk\log n)$，但显然可以一个指针代替二分，时间复杂度优化为 $\mathcal O((n+m)k)$。

这样就可以直接算出最长上升子序列的长度了，接下来的问题是如何还原这个序列。

显然需要倒序还原，设此时已经还原了最长上升子序列中的第 $i$ 个数 $x$，它在原序列的位置为 $j$。

若该位置不是空缺的，可以直接用 $p_j$ 找到上一项的位置。

若该位置是空缺的，则先在它前面的不是空缺的位置里找到位置 $s$ 满足 $l_s = i - 1$ 同时 $s$ 上的数 $< x$。如果找到了，那么上一项的位置就是 $s$；否则，上一项的位置就是上一个空缺的位置，且这个空缺上的数为用于填补的数中 $<x$ 的最大的数。

总时间复杂度 $\mathcal O(n \log n + m \log m + (n + m)k)$。

代码

const int N = 1e5 + 7, inf = INT_MAX >> 1;
int n, m, a[N], b[N], l[N], p[N], f[N], g[N], v[N], ans[N];

inline void get(int i, int k, int &x) {
	int o = lower_bound(b + 1, b + m + 1, k) - b - 1;
	v[o] = 1, x = ans[i] = b[o];
}

int main() {
	rd(n);
	for (int i = 1; i <= n; i++) rd(a[i]), f[i] = inf;
	++n, a[n] = f[n] = inf;
	rd(m);
	for (int i = 1; i <= m; i++) rd(b[i]);
	sort(b + 1, b + m + 1);
	for (int i = 1; i <= n; i++)
		if (~a[i]) {
			int j = lower_bound(f + 1, f + n + 1, a[i]) - f - 1;
			l[i] = j + 1, p[i] = g[j], f[j+1] = a[i], g[j+1] = i;
		} else
			for (int j = n, o = m; o; o--) {
				while (f[j] >= b[o]) --j;
				f[j+1] = b[o], g[j+1] = i;
			}
	int i = l[n], j = n, x = a[n];
	while (i--)
		if (~a[j]) {
			if (!~a[p[j]]) get(p[j], a[j], x);
			else x = a[p[j]];
			j = p[j];
		} else {
			bool ok = 0;
			for (int s = j - 1; s; s--)
				if (~a[s] && l[s] == i && a[s] < x) {
					x = a[j=s], ok = 1;
					break;
				}
			if (ok) continue;
			for (int s = j - 1; s; s--)
				if (!~a[s]) {
					get(s, x, x), j = s;
					break;
				}
		}
	for (int i = 1, j = 1; i <= n; i++)
		if (!~a[i]) {
			if (ans[i]) continue;
			while (v[j]) ++j;
			v[j] = 1, ans[i] = b[j];
		} else ans[i] = a[i];
	for (int i = 1; i < n; i++) print(ans[i], " \n"[i==n]);
	return 0;
}