CF1894D Neutral Tonality-526互联

退役之后啥也不会了/kk
首先容易想到 \(b_i\) 递减插入更优。考虑答案的下界显然是 \(LCA(a)\) ，答案的上界为 \(LCA(a)+1\)，因为我们总是可以在任意位置插入递减的 \(b_i\) 来得到。因此我们只需要考虑怎么判断当前答案取上界还是下界即可。
实际上，答案的下界是始终可以取到的。我们既然已经确定了 \(b_i\) 的插入顺序，不妨只考虑 \(m=1\) 的情况。我们有以下策略：
- 若 \(x<\min a_i\) ，我们直接把 \(x\) 插在原序列的末尾不会产生任何影响
- 否则我们可以找到第一个 \(x\geq a_i\) 的位置 \(i\)，然后把 \(x\) 插入在 \(i\) 的前面，也不会产生任何影响
拓展到 \(m \neq 1\) 的情况发现我们要干的是即使用两个指针便利 \(a_i\) 和 \(b_j\)，每次选择两者较小的插入。最终复杂度 \(O(n+m\log m)\)，瓶颈在排序