排序方案与 \(a_i\) 的具体数值无关，只与 \(a_i\) 的相对大小有关，所以离散化是显然的。
以下默认 \(a\) 已经离散化。
\(a\) 是排列
令 \(b\) 为 \(a\) 排序后序列，我们发现从 \(a\) 到 \(b\) 的方案是不好找的，但是 \(b\) 到 \(a\) 的方案挺好找，即连边 \((a_i, b_i, i)\) 构成若干个无交的置换环，然后在每个置换环上做一次轮换即可，方案即按顺序输出边权，那对 \(a\) 逆着做 \(b\) 到 \(a\) 的变换不就好了。
容易发现这也是选定下标总数最小的方案。
置换环是可以合并的，具体地，我们可以通过在每个要合并起来的置换环内各选一个点做一次轮换，假设选了 \(k\) 个点，就有 \(k\) 个置换环并成了一个，再轮换一次就可以消去这个大置换环。
消去 \(k\) 个置换环原来的操作次数是 \(k\)，现在是 \(2\)；原来的选定下标总数是 \(k\) 个环的大小之和，现在是 \(k\) 个环的大小之和 \(+ k\)。
同时我们也证明了选定下标总数的变化只与消去几个置换环有关，而与消去的置换环是哪些无关。
然后在 \(s\) 允许的情况下减小 \(q\) 就好了。
一般情况
此时 \(a_i\) 可能相同，考虑把所有相同的 \(a_i\) 缩成一个点。
然后我们会发现整张图形成了若干个连通块，每个连通块里是一条欧拉回路，也就是说原来我们要走的是置换环，现在要走的是欧拉回路。
剩下的和 \(a\) 是排列的情况就大同小异了。
连通块用并查集维护一下就好，找欧拉回路我用的是 dfs，时间复杂度是离散化的 \(\mathcal O(n \log n)\)。
然后是我最不会的代码实现……
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 2e5 + 10;
int n, s, a[N], b[N], tmp[N], to[N];
int head[N];
struct Edge {
int to, nxt, id;
} e[N];
vector<int> p;
inline void add(int x, int y, int id) {e[id] = Edge{y, head[x], id}, head[x] = id;}
namespace DSU {
int fa[N], sz[N], e[N];
void init(int n) {for (int i = 1; i <= n; i++) fa[i] = i;}
int find(int x) {
if (x == fa[x]) return x;
return fa[x] = find(fa[x]);
}
inline void merge(int x, int y, int id) {
int fx = find(x), fy = find(y);
if (fx != fy) {
if (sz[fx] < sz[fy]) swap(fx, fy);
fa[fy] = fx, sz[fx] += fy;
}
e[fx] = id;
}
}
void dfs(int u) {
while (head[u]) {
int v = e[head[u]].to, id = e[head[u]].id; head[u] = e[head[u]].nxt;
dfs(v); p.emplace_back(id);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
cin >> n >> s;
for (int i = 1; i <= n; i++) cin >> a[i], tmp[i] = a[i];
sort(tmp + 1, tmp + n + 1); int m = unique(tmp + 1, tmp + n + 1) - tmp - 1;
if (m == 1) {cout << 0; return 0;}
for (int i = 1; i <= n; i++) b[i] = a[i] = lower_bound(tmp + 1, tmp + m + 1, a[i]) - tmp;
sort(b + 1, b + n + 1); int mink = 0; DSU::init(m);
for (int i = 1; i <= n; i++) if (a[i] != b[i]) DSU::merge(a[i], b[i], i), mink++;
if (!mink) {cout << 0; return 0;}
if (s < mink) {cout << -1; return 0;};
for (int i = 1; i <= m; i++) if (DSU::fa[i] == i && DSU::e[i]) p.emplace_back(DSU::e[i]);
if (p.size() == 1) {
for (int i = 1; i <= n; i++) if (a[i] != b[i]) add(a[i], b[i], i);
p.clear();
for (int i = 1; i <= m; i++) if (head[i]) {dfs(i); break;}
cout << "1\n" << p.size() << '\n';
for (int i : p) cout << i << ' ';
return 0;
}
if (s > mink + 2) {
int merge = min((int)p.size(), s - mink);
cout << p.size() - merge + 2 << '\n' << merge << '\n';
p.erase(p.begin() + merge, p.end());
for (int i : p) cout << i << ' '; cout << '\n';
int ap0 = a[p[merge - 1]];
for (int i = merge - 1; i; i--) a[p[i]] = a[p[i - 1]];
a[p[0]] = ap0;
} else cout << p.size() << '\n';
for (int i = 1; i <= n; i++) if (a[i] != b[i]) add(a[i], b[i], i);
for (int i = 1; i <= m; i++) {
if (head[i]) {
p.clear(), dfs(i);
cout << p.size() << '\n';
for (int i : p) cout << i << ' '; cout << '\n';
}
}
return 0;
}