置换环是用来求解数组排序元素间所需最小交换次数这类问题。

置换环思想：置换环将每个元素指向其排序后应在的位置，最终首位相连形成一个环（若数字在最终位置，则其自身成环），可知元素之间的交换只会在同一个环内进行，而每个环内的最小交换次数为 环上元素-1
最后化简公式得，排序所需最小交换次数为数组长度-环的个数

https://www.acwing.com/problem/content/1226/
根据置换环定理，我们只需要找到每一个环交换顺序即可

#include <bits/stdc++.h>
#include <algorithm>
using namespace std;
const int N = 2e5 + 5;
int a[N],n,res=0;
bool b[N];
int main()
{
        cin>>n;
        for(int i=1;i<=n;i++)
        {
        cin>>a[i];
        }
        for(int i=1;i<=n;i++)
        {
        if(a[i]==i||b[i])
        continue;
        int j=i,cnt=0;
        while(!b[j])
        {
        b[j]=1;
        j=a[j];
        cnt++;
        }
        res+=cnt-1;
        }
        cout<<res;
}

https://www.luogu.com.cn/problem/CF2033E
第一个条件为自环，第二个条件p[p[i]]=i 则就是两个元素组成的环。我们重新考虑，发现每个环的交换次数为(环上元素-1）/2，依次累加每个环即可。

#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=1000005;
int a[N];
bool vis[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
            vis[i]=0;
        }
        int ans=0;
        for(int i=1;i<=n;i++)
        {
            if(vis[i])continue;
            int now=i,cnt=0;
            while(!vis[now])
            {
                vis[now]=1;
                now=a[now];
                cnt++;
            }
            ans+=cnt-1>>1;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

https://codeforces.com/contest/1768/problem/D

思路：我们不难知道每次交换两个相邻的数就会形成一个逆序对。

我们考虑置换环，置换环是啥（置换环就是我们对于每一个结点，将其指向排序之后它应该在的地方，直至形成一个环）。

明白置换环什么意思之后，不明白也没关系，我们来举个具体的例子，首先我们给出一个排列[1,3,4,5,2,6]，那么现在假设我们想让它变成一个单调递增的序列及[1,2,3,4,5,6]，那对于1和6来说就是一个自环，因为1和6最后指向的位置都是自己。那么3,4,5,2就会形成一个环，及2 − > 3 − > 4 − > 5 − > 2 ，环内有四个点，我们只需要用3步就可以变成单增的序列。也就是说每一个环内相当于只有一个点是不会改变的。那我们的操作次数就是n-环的个数。因为要保证有且仅有一个逆序对我们还得进行一次操作就是任意交换两个相邻的数得到一个逆序对多以操作次数再加1.

我们再考虑一种情况，那就是任意一个置换环内如果有两个数是相邻的，我们能不能省去一步操作呢。答案是可以的，还是上面那个例子，我们现在有一个环是[3,4,5,2]我们可以进行一步操作得到[3,,4,2,5]，然后我们再进行一步操作可以得到[3,2,4,5]那么现在我们观察一下这个序列是不是已经存在了一个[3,2]的逆序对了，那我们就不需要再还原然后交换相邻的位置了。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int p[N], vis[N];
map<int, int> ring;
int flag;

void dfs(int u)
{
    if (vis[u])
        return;
    vis[u] = 1;
    ring[u] = 1;
    int v = p[u];
    if (ring[u - 1] || ring[u + 1])
        flag = 1;
    dfs(v);
}

void solve()
{
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        vis[i] = 0;
    for (int i = 1; i <= n; i++)
        cin >> p[i];
    int cur = 0;
    flag = 0;
    for (int i = 1; i <= n; i++)
        if (!vis[i])
        {
            cur++;
            ring.clear();
            dfs(i);
        }

    if (flag)
        cout << n - cur - 1 << endl;
    else
        cout << n - cur + 1 << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
    return 0;
}