【玫瑰】

WeWantToRun · 2024-08-23 21:44:39 · 题解

设前 n 个点为红色，后 m 个点为蓝色。

观察样例一可以发现，一个大小为 t 的非同色环一定只需要 t-1 次操作即可复原，因为显然可以构造操作序列使得每次交换两个异色点。

然后考虑同色环。一个简单的大小为 t 的同色环显然交换一次之后会变成一个大小为 t+1 的非同色环，因此操作次数是 t+1 次。但是我们可以将两个大小分别为 x 和 y 的异色同色环配对，就只需要进行一次第一个操作，然后形成一个大小为 x+y 的同色环，因此操作次数总计是 x+y 次。

所以总的考虑，非同色环和孤立点操作次数比点数少一次，配对环操作次数等于点数，未配对同色环操作次数比点数多一次，并查集维护环的颜色即可。时间复杂度 O(n\alpha(n))。