首先考虑排列怎么做，排序时显然是可以将1移到下标为1的位置，然后把下标为1的位置移到它所应到的位置……直到点应到的位置为1原来的位置，就可以操作一次，使得这些点都归位。
于是建图 \(G = \langle V, E \rangle, V = \{i\ |\ 1 \le i \le n \}, E = \{(i, a_i)\ |\ 1 \le i \le n\}\)。由于 \(a\) 是一个排列，那么 \(G\) 就构成若干环。设 \(G\) 中有 \(k\) 个环，第 \(i\) 个环有 \(l_i\) 的点，分别为 \(p_{i, 1}, p_{i, 2}, \cdots, p_{i, l_i}\)。如果对一个环的所有点按顺序操作一次，每个点就都能在应在的位置。如果对某些环中任意一点进行轮换，可以合并这些环。
发现下标数量和操作次数就只与提前合并的环数有关。设其为 \(m\)，则操作次数为 \(cnt_2 - m + 2\)，下标数量为 \(cnt_1 + m\)。其中 \(cnt_1, cnt_2\) 分别为点数与环数。特别的，当 \(m = 1\) 时需要特判，此时不需要提前合并了，次数和下标都减1。这里都是很简单的。
好，考虑扩展到可重序列。观察上面排列能做的原因——每个点都有唯一对应位置，而可重序列就是在一段区间内的。那么可以对每个权值建一个虚点，让所有不在区间内的点连向虚点，虚点连向区间内未匹配的点。那么如果要使序列有序，即每条边都需要遍历，即欧拉回路。
那么处理出来这些欧拉回路后，把欧拉回路当作环即可。正确性显然。
标签：cnt,le,下标,LOJ2818,位置,循环,虚点,排序,欧拉 From： https://www.cnblogs.com/shengxuanyi/p/18561508