LOJ2818 「eJOI2018」循环排序
本题题解
约定：以下我们定义无向图的“连通块”，是指它的极大基图连通子图。其中基图是指把有向边边视作无向边，得到的无向图。
首先要搞清楚，对于一种排序方案，有两个参数来衡量它：操作次数，和操作到的位置数。本题里，我们要在满足【操作到的位置数】(leq s) 的前提下，最小化【操作次数】。思考时，千万不要将这两个量搞混了。
先将 (a) 序列离散化。设最大值为 (m)。然后求出排好序的序列长什么样子，设为 (b)。
建一张 (m) 个点的图。对每个 (i) ((1leq ileq n))，若 (a_i eq b_i)，我们连一条有向边 ((b_i,a_i))，原因稍后解释。记这条边的“编号”为 (i)。
容易发现，每个 (a_i eq b_i) 的 (i) 至少要作为【操作到的位置】出现一次。设这样的 (i) 有 (k) 个，则【操作到的位置数】至少为 (k)。所以如果 (k > s)，则可以直接判为无解。否则，发现【操作到的位置数】是可以等于 (k) 的。考虑我们刚刚建出来的有向图，这张图里每个点入度一定等于出度。因此这张图里的每个连通块，都存在欧拉回路。可以构造出一种操作方案是：对每个连通块，求出它的欧拉回路，按顺序输出所有边。此时读者不难发现，根据我们的建图方式，把一个连通块的欧拉回路上每条边的编号按顺序操作一遍后，就能使连通块里所有数值走到它最终应该走到的位置。
特别地，如果 (a) 是一个排列，则我们建出的有向图实际就是若干个环。每个点入度、出度都为 (1)。这是入度等于出度的一种特殊情况。应该可以帮助读者更好地理解上述操作策略。
设有 (c) 个连通块。那么在上述的操作策略中，我们所用的【操作次数】为 (c)，【操作到的位置数】为 (k)。前面已经说明过，这是能将【操作到的位置数】最小化的方案。但如果在允许的范围内（(leq s)），把【操作到的位置数】扩大一些，可能能进一步减小【操作次数】。
具体来说，我们可以用 (1) 次操作，将若干个连通块合并为一个连通块，使新连通块仍然存在欧拉回路。具体的方法是在每个连通块里任选一条边，设选出的边编号分别为 (i_1,i_2,dots,i_t)，那么对 (i_1,i_2,dots ,i_t) 做一次操作，就能使这些连通块以一个环的形式串起来。然后我们只需要再对新连通块做 (1) 次操作，就能使里面的数全部走到最终位置！
换句话说，无论多少个连通块，我们只需要 (2) 次操作，就能将它们全部排好序。但同时，这会使得【操作到的位置数】增大相应的连通块数量。所以有可能我们不能对所有连通块进行操作。具体来说，我们只会任选 (x = min(c, s - k)) 个连通块，将它们合并。最终，若 (x < 2)，则【操作次数】就是 (c)（不搞合并了），否则是：(2 + (c - x))。
还有一个小问题，就是求有向图的欧拉回路。我用 ( ext{dfs}) 来实现。那么对于有向边 ((u,v))，只能在从 (v) 回溯时输出（或记录）这条边，而不能在进入 (v) 之前输出，否则输出的可能就不是一条连续、完整的路径了。但是这样记录下的路径，与我们实际走的顺序其实是反的。所以你可以把路径 ( ext{reverse}) 一下，或者在建边的时候就干脆建反向边。
时间复杂度 (O(nlog n))。因为要排序。
参考代码
// problem: LOJ2818
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mk make_pair
#define lob lower_bound
#define upb upper_bound
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
template<typename T> inline void ckmax(T& x, T y) { x = (y > x ? y : x); }
template<typename T> inline void ckmin(T& x, T y) { x = (y < x ? y : x); }
const int MAXN = 2e5;
int n, lim, a[MAXN + 5], goal[MAXN + 5];
int vals[MAXN + 5], cnt_val;
int need_oper_pos;
vector<vector<int> > ans;
int fa[MAXN + 5], sz[MAXN + 5];
int last_edge[MAXN + 5];
int get_fa(int u) { return (u == fa[u]) ? u : (fa[u] = get_fa(fa[u])); }
void unite(int u, int v, int e) {
int fu = get_fa(u);
int fv = get_fa(v);
if (fu != fv) {
if (sz[fu] > sz[fv])
swap(fu, fv);
fa[fu] = fv;
sz[fv] += sz[fu];
}
last_edge[fu] = e;
}
struct EDGE { int nxt, to, eid; } edge[MAXN + 5];
int head[MAXN + 5], tot;
inline void add_edge(int u, int v, int eid) {
edge[++tot].nxt = head[u];
edge[tot].to = v;
edge[tot].eid = eid;
head[u] = tot;
}
vector<int> pos;
void dfs(int u) {
for (int& i = head[u]; i; ) {
int v = edge[i].to;
int eid = edge[i].eid;
i = edge[i].nxt;
dfs(v);
pos.pb(eid);
}
}
int main() {
cin >> n >> lim;
for (int i = 1; i <= n; ++i) {
cin >> a[i];
vals[++cnt_val] = a[i];
}
sort(vals + 1, vals + cnt_val + 1);
for (int i = 1; i <= n; ++i) goal[i] = vals[i]; // 目标序列
cnt_val = unique(vals + 1, vals + cnt_val + 1) - (vals + 1);
for (int i = 1; i <= cnt_val; ++i) {
fa[i] = i;
sz[i] = 1;
}
for (int i = 1; i <= n; ++i) {
a[i] = lob(vals + 1, vals + cnt_val + 1, a[i]) - vals;
goal[i] = lob(vals + 1, vals + cnt_val + 1, goal[i]) - vals;
// cerr << a[i] << "
"[i == n];
if (a[i] != goal[i]) {
unite(a[i], goal[i], i);
need_oper_pos++;
}
}
if (need_oper_pos > lim) {
cout << -1 << endl;
return 0;
}
int rest = lim - need_oper_pos;
// cerr << rest << endl;
if (rest >= 2) {
for (int i = 1; i <= cnt_val; ++i) {
if (get_fa(i) == i && last_edge[i] != 0) {
pos.pb(last_edge[i]);
if (SZ(pos) == rest)
break;
}
}
if (SZ(pos) >= 2) {
ans.pb(pos);
int last_val = a[pos.back()];
for (int i = SZ(pos) - 1; i >= 1; --i) {
a[pos[i]] = a[pos[i - 1]];
}
a[pos[0]] = last_val;
}
}
for (int i = 1; i <= n; ++i) {
if (a[i] != goal[i]) {
// cerr << i << " " << a[i] << " " << goal[i] << endl;
add_edge(a[i], goal[i], i);
}
}
for (int i = 1; i <= n; ++i) {
if (head[i]) {
vector<int>().swap(pos);
dfs(i);
ans.pb(pos);
}
}
cout << SZ(ans) << endl;
for (int i = 0; i < SZ(ans); ++i) {
cout << SZ(ans[i]) << endl;
for (int j = 0; j < SZ(ans[i]); ++j) {
cout << ans[i][j] << "
"[j == SZ(ans[i]) - 1];
}
}
return 0;
}