CF1893B Neutral Tonality

· · 题解

CF1893B Neutral Tonality

首先肯定将 b 降序排序。

设 a 的后缀 \max 为 c，那么在放入 a_j 之前，将所有 b_i > c_j 的 b_i 全部加入序列。这样可以保证原序列的 LIS 长度不变：假设存在 b_i 让 LIS 长度增加，则 LIS 包含 b_i。假设 b_i 在 a_j 和 a_{j + 1} 之间。由于 b_i > c_{j + 1}，于是 b_i 是 LIS 的结尾。如果 j = 0，说明 b_i 是 LIS 的开头，原序列 LIS 长度小于 1，矛盾。因此 j > 0，那么 a_j \geq b_i，否则 b_i > c_j，b_i 会放在 a_j 前面。将新序列的 LIS 中的 b_i 替换为 a_j 可得原序列长度相等的 IS，与 LIS 长度增加矛盾。

时间复杂度 \mathcal{O}(m\log m + n)。

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdi = pair<double, int>;
using pdd = pair<double, double>;
using ull = unsigned long long;

#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;
// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd(1064);
int rd(int l, int r) {return rnd() % (r - l + 1) + l;}

constexpr int mod = 998244353;
void addt(int &x, int y) {x += y, x >= mod && (x -= mod);}
int add(int x, int y) {return x += y, x >= mod && (x -= mod), x;}
int ksm(int a, int b) {
  int s = 1;
  while(b) {
    if(b & 1) s = 1ll * s * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return s;
}

constexpr int Z = 1e6 + 5;
int fc[Z], ifc[Z];
int bin(int n, int m) {
  if(n < m) return 0;
  return 1ll * fc[n] * ifc[m] % mod * ifc[n - m] % mod;
}
void init_fac(int Z) {
  for(int i = fc[0] = 1; i < Z; i++) fc[i] = 1ll * fc[i - 1] * i % mod;
  ifc[Z - 1] = ksm(fc[Z - 1], mod - 2);
  for(int i = Z - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
}

// ---------- templates above ----------

constexpr int N = 2e5 + 5;

int n, m, a[N], b[N], c[N];
void mian() {
  cin >> n >> m;
  a[n + 1] = c[n + 1] = 0;
  for(int i = 1; i <= n; i++) cin >> a[i];
  for(int i = n; i; i--) c[i] = max(c[i + 1], a[i]); 
  for(int i = 1; i <= m; i++) cin >> b[i];
  sort(b + 1, b + m + 1);
  reverse(b + 1, b + m + 1);
  vector<int> ans;
  for(int i = 1, pt = 1; i <= n + 1; i++) {
    while(pt <= m && b[pt] >= c[i]) ans.push_back(b[pt++]);
    if(i <= n) ans.push_back(a[i]);
  }
  for(int it : ans) cout << it << " ";
  cout << "\n";
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T = 1;
  cin >> T;
  while(T--) mian();
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}