比赛链接

给定一个 $n+m$ 的排列，每次可以选取一个位置位于 $1\sim n$ 的元素和一个位置位于 $n+1\sim n+m$ 的元素交换位置。

问使得排列有序的最小操作次数。

将排列分解成若干置换环，则对于每个交换操作，等价于选取 $1\le i\le n,n+1\le j\le n+m$，将 $i\to p_i,j\to p_j$ 变为 $i\to p_j,j\to p_i$。

不难发现如果 $i,j$ 属于同一个置换环则环分裂，否则两个环合并。

同时将前 $n$ 个位置染黑，后 $m$ 个位置染白，于是每次操作需要选中一个黑点和一个白点进行操作。

设 $A_i$ 表示第 $i$ 次操作后大小至少为 $2$ 的纯黑色环个数， $B_i$ 表示第 $i$ 次操作后大小至少为 $2$ 的纯白色环个数，$C_i$ 表示第 $i$ 次操作后置换环个数。

定义势能函数 $f(i)=n+m-C_i+2\max(A_i,B_i)$。不难发现 $|C_{i+1}-C_i|=1,|A_{i+1}-A_i|\le 1,|B_{i+1}-B_i|\le 1$。

同时有 $(C_{i+1}-C_i)(A_{i+1}-A_i)\ge 0,(C_{i+1}-C_i)(B_{i+1}-B_i)\ge 0$。于是有 $f(i+1)\ge f(i)+1$。

终态 $A_z=B_z=0,C_z=n+m$，于是有 $f(Z)=0$，最小操作次数不小于 $f(0)-f(Z)=n+m-C_0+2\max(A_0,B_0)$。

下面证明下界可以取到：

首先如果 $A_i\gt 0,B_i\gt 0$，可以选取一个纯黑环和一个纯白环合并，这样 $A_{i+1}-A_i=B_{i+1}-B_i=C_{i+1}-C_i=-1, f(i+1)=f(i)-1$。

若 $A_i\gt 0,B_i=0$，可以选取一个纯黑环和一个含白点的环合并，这样 $\max(A_{i+1},B_{i+1})-\max(A_i,B_i)=-1,f(i+1)=f(i)-1$。

$A_i=0,B_i\gt 0$ 类似处理。最后考虑 $A_i=0,B_i=0$ 的情况，不妨任取一个大小不为 $1$ 的置换环，假设环上黑点不少于白点。

可以找到 $i,p_i$ 满足 $i$ 是白点且 $p_i$ 是黑点，交换位置 $i,p_i$ 的元素等价于从环上单独拆出 $p_i$。

这样环上黑点数减一，但显然不会形成大小超过 $1$ 的纯白环。于是 $A,B$ 不变， $C_{i+1}=C_i-1,f(i+1)=f(i)-1$。

const int MAXN=1e5+5;
int n,m,a[MAXN<<1],vis[MAXN<<1];
int cnt1,cnt2;
void dfs(int pos){
	if(vis[pos])return;
	vis[pos]=true;
	if(pos<=n)cnt1++;
	else
	cnt2++;
	dfs(a[pos]);
}
int main(){
	n=read_int(),m=read_int();
	_rep(i,1,n+m)
	a[i]=read_int();
	int ans=n+m,s1=0,s2=0;
	_rep(i,1,n+m){
		if(!vis[i]){
			ans--;
			cnt1=cnt2=0;
			dfs(i);
			if(cnt1>=2&&cnt2==0)
			s1++;
			else if(cnt2>=2&&cnt1==0)
			s2++;
		}
	}
	enter(ans+2*max(s1,s2));
	return 0;
}