CF1893B Neutral Tonality 题解

很巧妙的一道题。

为了让 \(\text{LIS}\) 长度最小，我们肯定先将 \(b\) 数组降序排序，这样 \(b\) 自身对 \(\text{LIS}\) 的贡献最小。

考虑是否存在一种插入方式使得最终 \(a\) 的 \(\text{LIS}\) 长度和最初 \(a\) 的 \(\text{LIS}\) 长度相等。这时我们会发现，如果我们插入 \(b\) 的时候形如：\(a_1,a_2,\dots,a_k,{\color{Red}b_1,b_2,\dots,b_p},a_{k+1}\)，且满足 \(\min_{1 \le i \le k}(a_i) > \max_{1 \le i \le p}(b_i) > a_{k+1}\)，那么 \(b\) 数组一定对答案没有影响（一定不会增加 \(\text{LIS}\) 的长度），因为选 \(b\) 中的任意一个数都不如选 \(a_{k+1}\)（\(a_{k+1}\) 更小，后面能选的更多）。

所以我们的构造方式为：对于一个数 \(a_i\)，把 \(b\) 的一段大于 \(a_i\) 的前缀全部放到 \(a_i\) 前面，最后剩下的数一定小于所有数，直接放到最后即可。