因为某 hhz 曾经往 XJOI 模拟赛搬了这题，然后现在我要给模拟赛讲题，所以滚回来补题了。
观察 \(1\)：对于一个形如 WWBB 的子图，如果当前匹配是 \((1,4)(2,3)\)，我们换成 \((1,3)(2,4)\) 总更优。
观察 \(2\)：满足观察 \(1\) 的情况，可以被描述为，假设某个 B 和 W 相连，那么当前 B 的后一个 B 一定连着当前 W 的下一个 W。
观察 \(3\)：在观察 \(2\) 的基础上，假设一条线段的两个点在环上的距离为 \(d\)，那么该线段一定和 \(d-1\) 条线段相交。
观察 \(4\)：在观察 \(3\) 的基础上，考虑把白点全部对称到环上对称的位置，然后再计算距离 \(d\)，那么即为 \(n-d-1\) 的贡献。
因此我们的目标转为最小化 \(\sum d\)。
容易发现，我们假设每个黑点权值是 \(+1\)，每个白点权值是 \(-1\)，那么当前问题就转化为了经典的糖果传递，直接套结论即可。
总复杂度可以做到 \(O(n)\)。
标签：环上,线段,当前,权值,观察,loj3362 From： https://www.cnblogs.com/myee/p/loj3362.html