CF568E Longest Increasing Subsequence 题解

Description

给定一个长度为 \(n\) 的有 \(k\) 个空缺的序列。

你有 \(m\) 个数可以用于填补空缺。

要求最大化最长上升子序列的长度。

\(n, m \le 10^5\)，\(k \le 10^3\)。

Solution

容易发现只需要先构造出 LIS 上的位置的值，对于其余未填位置随便填，所以构造 LIS 时就不需要考虑出现重复的问题。

考虑先求出最长上升子序列长度。

有一个显然的做法是维护一个数据结构，对于已经填了的位置就正常转移，对于没填的位置暴力枚举填的数然后转移，可以做到 \(O\left((n+m)k\right)\)，但是常数会比较大。

有另一个求 LIS 的方法是维护 \(f_i\) 表示当前长度为 \(i\) 的上升子序列的最小末尾值，\(g_i\) 表示这个末尾的位置。每次加入一个 \(x\)，就二分求出 \(f_j<x\) 的最大的 \(j\)，说明以 \(x\) 结尾的 LIS 长度为 \(j+1\)。又由于 \(f_{j+1}\geq x\)，就用 \(x\) 更新 \(f_{j+1}\) 。对于没填的位置可以维护一个指针，从大往小枚举填的数同时更新指针即可。这样做常数就很小了。

然后考虑构造方案。

先在求 LIS 的过程中求出 \(len_i\) 表示以 \(i\) 结尾的 LIS 长度，\(pre_i\) 表示以 \(i\) 结尾的 LIS 中 \(i\) 的前驱的位置。这时会发现对于 \(a_i=-1\) 的位置这两个东西是维护不了的，构造方案时需要特殊处理。

为了方便构造方案，先在数组末尾加入 \(+\infty\)。然后找到 LIS 的末尾位置 \(n+1\)，每次往前跳，可以在跳的过程中更新 \(-1\) 的位置的 \(len\) 值。设当前在 \(i\)，如果 \(a_i\) 初始不为 \(-1\)，有两种情况：

1. \(a_{pre_i}\) 为 \(-1\)，就让 \(a_{pre_i}\) 填 \(<a_i\) 的最大可填值。
2. \(a_{pre_i}\) 不为 \(-1\)，就不用管。

然后就是 \(a_i\) 初始为 \(-1\)（由于是从后往前构造的，所以 \(a_i\) 此时已经填了数了），如果前面存在一个位置 \(j\)，使得 \(a_j\neq -1,a_j<a_i,len_j=len_i-1\)，那么 \(i\) 的前驱就为 \(j\)。否则一定是一个 \(-1\) 的位置，这里贪心选取最靠近 \(i\) 的那个 \(-1\)，同时填上 \(<a_i\) 的最大可填值。填完往前跳即可。

时间复杂度：\(O\left((n+m)k\right)\)。

Code

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 1e5 + 5;

int n, m;
int a[kMaxN], b[kMaxN], pre[kMaxN], len[kMaxN], f[kMaxN], g[kMaxN];
bool vis[kMaxN];

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) std::cin >> a[i];
  std::cin >> m;
  for (int i = 1; i <= m; ++i) std::cin >> b[i];
  std::sort(b + 1, b + 1 + m);
  a[n + 1] = 1e9 + 1;
  memset(f, 0x3f, sizeof(f)), memset(pre, -1, sizeof(pre));
  f[0] = g[0] = 0;
  for (int i = 1; i <= n + 1; ++i) {
    if (~a[i]) {
      int j = std::lower_bound(f, f + 2 + n, a[i]) - f - 1;
      len[i] = j + 1, pre[i] = g[j], f[j + 1] = a[i], g[j + 1] = i;
    } else {
      for (int j = m, k = n + 1; j; --j) {
        for (; ~k && f[k] >= b[j]; --k) {}
        f[k + 1] = b[j], g[k + 1] = i;
      }
    }
  }
  for (int i = n + 1; len[i] > 1;) {
    assert(~a[i]);
    if (!~pre[i]) {
      for (int j = i - 1; j; --j) {
        if (~a[j] && len[j] == len[i] - 1 && a[j] < a[i]) {
          pre[i] = j; break;
        }
      }
      if (!~pre[i]) {
        for (int j = i - 1; j; --j) {
          if (!~a[j]) {
            pre[i] = j; break;
          }
        }
      }
    }
    if (!~a[pre[i]]) {
      int j = std::lower_bound(b + 1, b + 1 + m, a[i]) - b - 1;
      a[pre[i]] = b[j], vis[j] = 1, len[pre[i]] = len[i] - 1;
    }
    i = pre[i];
  }
  for (int i = 1, j = 1; i <= n; ++i) {
    if (!~a[i]) {
      for (; vis[j]; ++j) {}
      a[i] = b[j], vis[j] = 1;
    }
  }
  for (int i = 1; i <= n; ++i) std::cout << a[i] << ' ';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}