[ARC147C] Min Diff Sum 题解

本文提供一种另类做法。虽然我的代码从实现以及常数上都更劣一些。

考虑原式的几何意义，即在数轴上的 个区间内各选一个点使得这 个点两两距离之和最小。

考虑什么时候距离之和最小，显然是所有点都尽量向某一个位置靠拢时。所以钦定中心点，让其它所有点都尽量向这个点靠拢，再暴力计算贡献。时间复杂度 。

注意到，中心点取在非端点显然时不会更优，所以可以离散化。时间复杂度 。

现在考虑优化计算原式的过程。考虑拆贡献。 个点把数轴分成 条线段（以及两条射线）,那么第 条线段就会被计算 次。这是显然的。那么我们可以现将这 个点排序，再按上述过程计算。时间复杂度 。

容易发现，在中心点移动的过程中，有许多点的位置并不会随着中心点位置的改变而改变，所以考虑动态维护每个点的位置以及贡献。设当前中心点位置为 ，可以把 个点分成 段：

• ，这些点的位置固定在了 ，不会再改变。

• ，这些点的位置会随着中心点位置的改变而改变，且它们的位置都是 。

• ，这些点的位置暂时固定在了 。

那么我们可以动态维护这三段的端点。当 遇到了一个左端点时，相当于将一个点从第三段移到第二段；当 遇到了一个右端点时，相当于把一个点从第二段移到了第一段。

在此同时，动态维护每段内部的贡献。第一三段的贡献只需要在遇到端点时更新，第二段内部显然没有贡献。。

于是这道题就做完了。

提交记录。