题解 CF568E 【Longest Increasing Subsequence】

· · 题解

CF568E Longest Increasing Subsequence

题意

题解

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

设 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;
}