ARC167D Good Permutation 题解

题意

给定一个长度为 \(N\) 的排列 \((P_1,P_2,\cdots,P_N)\)。称一个排列 \(P\) 为“好排列”当且仅当对于所有 \(1\leq x\leq N\)，都能通过不停地使 \(x\leftarrow P_x\) 将 \(x\) 变成 \(1\)。

通过最小次数操作将 \(P\) 变成“好排列”，每次操作为交换 \(P\) 中的两个数 \(P_i\) 和 \(P_j\)。并且在保证操作次数最小的情况下使最后的 \(P\) 字典序最小，求最后的 \(P\)。

题解

这种不停地跳的问题显然想到 \(i\rightarrow P_i\) 连边，则原序列的图为一个个环。显然，最小操作次数为 环的数量 - 1，因为每次操作只要选不同环上的两个点，交换它们连向的点就可以把两个环合并为一个环。

考虑如何操作使字典序最小，我们从小到大依次考虑每个位置能放的最小的数。显然，一个位置上的数除了自己环上的其他都可以放。

则可以用一个 set 维护所有环上的最小值，每次寻找不是自己环上的最小值（只可能是 begin 或这 begin 的下一个），如果比当前值小，直接交换即可，这个最小值可以用并查集维护。

考虑到一个问题，就比如 2 1 4 3 这个样例，在第一个环 2 1 上显然不会交换，但在第二个环 4 3 上就会和 1 交换，这样显然是不优的。解决的方法就是我们强制钦定每个环在最后一个必须交换，这样在 1 的时候就会和 3 交换，把两个环合并为一个，避免了不优的问题。

时间复杂度 \(\mathcal{O}(n\log n)\)。

代码

#include <bits/stdc++.h>
#define rep(i, j, k) for(int i = (j); i <= (k); i++)
#define per(i, j, k) for(int i = (j); i >= (k); i--)
#define ll long long
#define vi vector<int>
#define sz(a) ((int)(a.size()))
#define mset(f, x) memset(f, x, sizeof(f))
#define ALL(x) (x).begin(), (x).end()
#define rALL(x) (x).rbegin(), (x).rend()
#define uni(x) x.resize(unique(ALL(x)) - x.begin())
#define ull unsigned long long
using namespace std;
const int maxN = 2e5 + 10;
int n, p[maxN], pre[maxN];
int fa[maxN], mx[maxN], mn[maxN];
set<int> S;
int getfa(int x) {if(fa[x] == x) return x; return fa[x] = getfa(fa[x]);}
void merge(int x, int y) {
    x = getfa(x), y = getfa(y);
    if(x == y) return;
    fa[x] = y;
    mx[y] = max(mx[y], mx[x]);
    mn[y] = min(mn[y], mn[x]);
}
void Main() {
    cin >> n;
    rep(i, 1, n) {
        cin >> p[i];
        fa[i] = i;
        mx[i] = mn[i] = i;
    }
    rep(i, 1, n) {
        pre[p[i]] = i;
        merge(i, p[i]);
    }
    rep(i, 1, n) if(getfa(i) == i) S.insert(mn[i]);
    rep(i, 1, n - 1) {
        if((int)S.size() == 1) break;
        auto it = S.begin();
        if((*it) == mn[getfa(i)]) it++;
        int val = (*it);
        if(val < p[i] || i == mx[getfa(i)]) {
            S.erase(mn[getfa(i)]);
            S.erase(mn[getfa(val)]);
            merge(i, val);
            S.insert(mn[getfa(i)]);
            int tmp = pre[val];
            swap(pre[p[i]], pre[val]);
            swap(p[i], p[tmp]);
        }
    }
    rep(i, 1, n) cout << p[i] << " "; cout << "\n";
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int t; cin >> t; while(t--) Main();
	return 0;
}