Problem - D - Codeforces 

 D. Lucky Permutation（置换环）-CSDN博客

如果环中，有相邻的两个点，那么可以通过减少一次交换，使得其贡献出一个逆序对。 

感觉这个博客对于最后逆序说的还是不太好理解，这个结论如何证明呢？

枚举情况理解：

2 1 3 4

连续的数如果“被动归位”（置换环的数都是主动回到自己位置），说明环内没有别的数了，只有环内其余数都归位，这个没动过数才会归位。（所以n-1次）

就对1 2 来说吧，1,2在环中时

如果不动 1 2，他们永不归位，最后会到对方的位置，正好符合一个连续逆序对。

（自己想想，）

——————

环是越来越小的，每次交换两个数是为了让一个数回自己的位置，如果另一个数也回去了，说明只剩两个数了。

1,2可能不在环内连着，但是慢慢的会靠近。

map<int, bool>ring;void solve()
{int n;cin >> n;vector<int>arr(n + 1);vector<int>vis(n + 1);int flag = 0;for (int i = 1; i <= n; i++){cin >> arr[i];}int ans = 0;for (int i = 1; i <= n; i++){if (vis[i] || arr[i] == i)continue;int cur = i;int tmp = 0;ring.clear();while (vis[cur] == 0){vis[cur] = 1;ring[cur] = 1;if (ring[cur + 1] || ring[cur - 1]){flag = 1;}cur = arr[cur];tmp++;}ans += tmp - 1;}if (flag)cout << ans - 1 << endl;elsecout << ans + 1 << endl;
}
signed main()
{ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);int t = 1;cin >> t;while (t--){solve();}return 0;
}