The 2021 ICPC Asia Macau Regional Contest-526互联

随便选一条路径，若不合法则 reverse 即可。

大小相等的置换环显然可以合并，大小不同的环只有 \(O(\sqrt n)\) 种，预处理每个环的 \(size\) 个不同答案即可单组询问 \(O(\sqrt n)\) 。

对于一个环 \(a_0,...,a_{n-1}\)，需要对 \(0\le i<n\) 求出 \(f_i=\sum_{j=0}^{n-1} a_ja_{(j+i+1)\bmod n}\)，显然是个差卷积的形式，FFT 即可 \(O(n\log n)\) 求出。

直接模拟前 \(n\) 轮，用堆维护。

复杂度 \(O(n\log n)\)。

若当前 \(i\) 没法读取，那么就是要把 \(i\) 挪到 \(1\) 或 \(k\) 的位置。设 \(dp(i,0/1)\) 处理完了前 \(i\) 个数，\(i\) 在 \(1/k\) 的最小操作次数，转移到下一个没法读取的数，可以利用树状数组二分求出。

复杂度 \(O(n\log^2n)\)。

考虑 Borvuka，每次需要对每个点找到一个异色最小边。

在所有串中间加唯一字符拼起来，然后后缀排序。要对每个点求出前面与后面第一个异色点，可以直接递推。

复杂度 \(O(n\log n+n\alpha(n))\)。

按边权从小到大加边，出现环时该环即为答案，用并查集简单维护即可。

复杂度 \(O(n\alpha(n))\)。