D. Lucky Permutation 置换环，仅有一个连续的逆序的理解

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;
	else
		cout << 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;
}