题解 AT_arc201_d Match, Mod, Minimize

为了方便叙述，下文的下标从 $0$ 开始。

令 $a$ 降序排列，$b$ 升序排列。在 $a$ 上选取一个分界点，使得分界点前面的 $a_i+b_i\ge m$，这时候前面的 $a_i$ 的贡献就变成了 $a_i-m$。

再考虑 $b_i$ 的配对，感性理解，越大的 $a_i$ 应该和越小的 $b_i$ 配对，于是实际配对就是从分界点 $k$ 开始配对，形式化的就是将 $b_i$ 与 $a_{(i+k)\bmod m}$ 配对，也就是官方题解里提到的循环移位。

将 $b$ 完成循环移位后，此时显然应有 $\forall i, a_i+b_i\ge 0$。此外，手搓一下不难发现，分界点越靠前，$\max\set{a_i+b_i}$ 就越大，所以我们只需要二分找到最后的合法分界点并计算贡献即可。

时间复杂度 $O(n\log n)$。

代码实现将二分的 check 和贡献计算合一起了。

Link.