题解 CF568E 【Longest Increasing Subsequence】

> [CF568E Longest Increasing Subsequence](https://codeforces.com/contest/568/problem/E) ## 题意 - 给定一个长度为 $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)$。 ## 代码 ```cpp 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; } ```