题解：CF1768D Lucky Permutation

Hsl_Beat · 2025-12-13 22:21:45 · 题解

首先对于排列 p ，有一个逆序对的条件就是存在一个位置 i 满足 p_i > p_{i + 1} ，其他相邻元素都是递增的。

我们可以对于每个 i 把 i 与 p_i 连一条无向边，最终会形成一个个环。我们只需要把这些环内部归位再进行一次操作就可以让 p 满足条件。对于一个环，它对答案的贡献就是它内部的点数 -1 。

对于环我们可以用并查集维护，算答案的时候可以让答案初始化为 n ，然后每次遇到一个环就把答案减一。

注意我们要是发现相邻两个元素在同一个环里，那么我们可以在复原环的时就省一步让 p 满足条件，要特判。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int fa[222222];
int n;
void init()
{
    for (int i = 1; i <= n; i++) {
        fa[i] = i;
    }
}
int find(int x)
{
    if (fa[x] == x) {
        return x;
    }
    return fa[x] = find(fa[x]);
}
void merge(int x, int y)
{
    fa[find(x)] = find(y);
}
bool same(int x, int y)
{
    return find(x) == find(y);
}
void solve()
{
    cin >> n;
    init();
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        merge(i + 1, a[i]);
    }
    int ans = n;
    for (int i = 1; i <= n; i++) {
        if (find(i) == i) {
            ans--;
        }
    }
    for (int i = 1; i < n; i++)  {
        if (same(i, i + 1)) {
            cout << ans - 1 << '\n'; // 省一步操作
            return;
        }
    }
    cout << ans + 1 << '\n'; // 复原后还要操作一次满足条件
} 
signed main()
{
    ios::sync_with_stdio(0) ;
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}