Description：

$2n$ 个数站成两排（每个数在 $2n$ 个数中最多出现两遍），一次操作可以交换任意一列中两个数，求使每行数不重复的最少操作数。

$1\leqslant n \leqslant 50000$

Solution：

带权并查集，把位置看作点（总共 $n$ 个点，不是把人看作点），那么如果两个位置要么同时交换，要么同时不交换，就连权值为 $0$ 的边，否则连权值为一的边，最后枚举联通块内的所有点，分别统计必须在两边的每边的点的数量，两者取 $\min$ 累加到答案里即可。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int n;

#define MAXN 50010

int a[MAXN],b[MAXN];

#define MAX 100000

int pos[MAX];

int f[MAXN << 1],g[MAXN << 1],s[MAXN << 1],w[MAXN << 1];

int find(int x)

{

	if(f[x] == -1)return x;

	int fa = find(f[x]);

	g[x] ^= g[f[x]];

	f[x] = fa;

	return f[x];

}

int merge(int a,int b,int c)

{

	int p = find(a),q = find(b);

	if(p == q)

	{

		int val = g[a] ^ g[b];

		return (val ^ c);

	}

	else

	{

		int val = c ^ g[a] ^ g[b];

		f[p] = q;g[p] = val;s[q] += s[p];

		return 0;

	}

}

bool v[MAXN];

int main()

{

	scanf("%d",&n);

	int maxv = 0;

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

	for(int i = 1;i <= n;++i)maxv = max(maxv,b[i] = read());

	memset(f,-1,sizeof(f));

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

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

	{

		if(pos[a[i]] == 0)pos[a[i]] = i;

		else merge(pos[a[i]],i,1);

	}

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

	{

		if(pos[b[i]] == 0)pos[b[i]] = i + MAXN;

		else

		{

			if(pos[b[i]] <= MAXN)merge(pos[b[i]],i,0);

			else merge(pos[b[i]] - MAXN,i,1);

		}

	}

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

	{

		find(i);

		if(g[i] == 1)++w[find(i)];

	}

	memset(v,false,sizeof(v));

	int ans = 0;

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

	{

		if(!v[find(i)])

		{

			ans += min(w[find(i)],s[find(i)] - w[find(i)]);

			v[find(i)] = true;

		}

	}

	cout << ans << endl;

	return 0;

}