Description：

一个序列 $a$ ，要把它排序，每次可以交换两个位置上的数，但是要求交换之后归位的数字的个数必须比之前多，问最多能交换几次。

$1\leqslant n\leqslant 10^6$

Solution：

发现如果只考虑两个位置的话，匹配数的变化一定是 $0\to 1$ 或者 $0\to 2$ ，不可能是 $1\to 2$ ，那么设 $b[]$ 为排好序的序列，如果 $a[i]\ne b[i]$ 就在一个无向图中连边 $a[i]\longleftrightarrow b[i]$ ，如果是 $0\to 1$ ，那么就是 $a\longleftrightarrow b\longleftrightarrow c$ 变成 $a\longleftrightarrow c$ ， $0\to 2$ 就是 $a\Longleftrightarrow b$ 这条边消失，那么我们把这个图建出来，如果大小为 $1$ ，对答案没有贡献，如果大小为 $2$ ，那么只能不停用 $0\to 2$ ，对答案的贡献为 $siz/2$ ，否则不考虑重边的话这个联通块一定是一个环，那么我们就可以用第一种方法把这个环上的边传来传去，也就是说最后一定会被削成只有两个点，之间有两条边的情况，因此贡献为 $siz-1$ 。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n;

#define MAXN 1000010

int a[MAXN],b[MAXN],c[MAXN];

int f[MAXN],pn[MAXN],en[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

bool vis[MAXN];

int main()

{

	freopen("banzhuan.in","r",stdin);

	freopen("banzhuan.out","w",stdout);

	scanf("%d",&n);

	for(int i = 1;i <= n;++i)scanf("%d",&a[i]);

	for(int i = 1;i <= n;++i)c[i] = b[i] = a[i];

	sort(c + 1,c + 1 + n);

	c[0] = unique(c + 1,c + 1 + n) - c - 1;

	for(int i = 1;i <= n;++i)a[i] = lower_bound(c + 1,c + 1 + c[0],a[i]) - c;

	for(int i = 1;i <= n;++i)b[i] = a[i];

	sort(b + 1,b + 1 + n);

	int mx = 0;

	for(int i = 1;i <= n;++i)mx = max(mx,a[i]);

	for(int i = 1;i <= mx;++i)f[i] = i;

	for(int i = 1;i <= mx;++i)pn[i] = 1;

	for(int i = 1;i <= n;++i)

	{

		if(a[i] != b[i])

		{

			int p = find(a[i]),q = find(b[i]);

			if(p != q)

			{

				f[p] = q;

				pn[q] += pn[p];

				en[q] += en[p] + 1;

			}

			else en[p]++;

		}

	}

	int ans = 0;

	for(int i = 1;i <= mx;++i)

	{

		int k = find(i);

		if(!vis[k])

		{

			vis[k] = true;

			if(pn[k] == 1)continue;

			if(pn[k] == 2)ans += en[k] / 2;

			if(pn[k] > 2)ans += en[k] - 1;

		}

	}

	cout << ans << endl;

	fclose(stdin);

	fclose(stdout);

	return 0;

}