CF1883G2 Dances (Hard Version)-526互联

Hint1: 对于 \(C[i]\) 的答案上界和下界分别是多少？
Hint1.1: 记 \(C[i]_1\) 时的答案 \(ans\)，答案范围显然是 \([ans,ans+1]\)
Hint2: 答案是否单调递增？
Hint2.1: Of course it is.
因此我们可以二分答案在哪个地方开始变化，二分后里面的部分就是跑 Easy Version 的做法，复杂度 \(O(n \log m)\)
还有一种方法：我们不妨现设 \(a_1=+\infty\)，跑一边 Easy Version 可以得到若干个被删除的 \(b_i\)，记这些 \(b_i\) 的集合为 \(S\)
下面假设 \(\max\{x|x \in S\} \geq m\)，否则我们可以让他和 \(m+1\) 取 \(\min\)。发现如果 \(a_1 < \max\{x|x \in S\}\)，那可以从 \(S\) 中抽出最大的和 \(a_1\) 匹配，答案 \(-1\)；否则没人和他匹配，答案不变
因此答案为 \((ans-1)(\max\{x|x \in S\}-1)+ans(m-\max\{x|x \in S\}+1)\)，可以做到 \(O(n \log n)\)，瓶颈复杂度在排序