【2023NOI模拟赛15】不见不散 做题记录

给定一个长度为 $n$ 的排列 $a$，同时你有一个长度为 $n$ 的排列 $b_i=i$，设 $op=\{(x,y)|1\le x<y\le n,x\neq y\}$。你需要重新排列 $b$ 的元素，满足依次交换 $b_{x_i}$ 和 $b_{y_i}$ 后有 $b=a$。
$2\le n\le 10^3$。

首先有一个结论，交换 $b_x$ 和 $b_y$（$x\neq y$）后一定会改变 $b$ 的逆序对个数的奇偶性，证明：

• $i<x$ 和 $i>y$ 的 $i$ 参与构成的逆序对显然没有影响；
• $x<i<y$ 的 $i$：
  设有 $sx$ 个 $b_i$ 满足 $x<i<y$ 且 $b_i<b_x$，有 $bx$ 个 $b_i$ 满足 $x<i<y$ 且 $b_i>b_x$；
  有 $sy$ 个 $b_i$ 满足 $x<i<y$ 且 $b_i<b_y$，有 $by$ 个 $b_i$ 满足 $x<i<y$ 且 $b_i>b_y$；
  那么交换之前 $[x,y]$ 中的逆序对个数显然是 $bx+sy+[b_x>b_y]$，交换之后是 $sx+by+[b_x<b_y]$，由于 $sx+bx=sy+by$ 所以 $bx+sy$ 和 $sx+by$ 奇偶性一样，而 $[b_x>b_y]\neq [b_x<b_y]$，所以逆序对个数的奇偶性一定会被改变。

那么 $a$ 的逆序对个数的奇偶性和 $\frac{n(n-1)}{2}$ 的奇偶性不一样则无解，接下来考虑通过构造来证明其他情况一定有解。

考虑先把所有 $b_i\neq a_i$ 的 $i$ 通过不断交换满足 $b_j\neq a_i$ 的 $b_i$ 和 $b_j$，最后再交换满足 $b_j=a_i$ 的 $b_i$ 和 $b_j$，这样就可以消掉 $i$，把问题转化为大小为 $n-1$ 的子问题。

那么现在问题就变成了要让进行完所有交换之后 $b_i=i$。

不难发现，由于逆序对个数（$0$）和 $\frac{n(n-1)}{2}$ 的奇偶性相同，那么此时的 $n$ 一定满足 $n\operatorname{mod} 4\in\{0,1\}$，所以考虑不断消掉四个位置来把问题转化为 $n-4$ 的子问题。

考虑这样的过程，其中 $st$ 是剩下的位置（不包含 $x$ 和 $y$）：

inline void slove(int x,int y)
{
	auto p=st.begin();
	while(p!=st.end()) swp(x,*p++);
	swp(x,y);
	p=st.end();
	while(p!=st.begin()) swp(y,*--p);
}

不难发现这样就可以把 $x$ 和 $y$ 消掉且交换 $b_x$ 和 $b_y$，那么考虑四个位置 $x,y,z,w$，可以这样把它们消掉：

st.erase(x);
st.erase(y);
st.erase(z);
st.erase(w);
slove(x,y);
slove(z,w);
swp(x,z),swp(y,w);
swp(x,w),swp(y,z);

那么不断执行以上操作，直到 $n\le 1$ 即可。

时间复杂度 $O(n^2)$。

代码如下：

#include <iostream>
#include <cstdio>
#include <set>

using namespace std;

const int S=1005;

struct node
{
	int x,y;
}ans[S*S];

int n,a[S],b[S];
int tr[S];
int tot;
set<int> st;

inline void add(int pos,int x)
{
	for(int i=pos;i<=n;i+=i&-i) tr[i]+=x;
}

inline int que(int pos)
{
	int res=0;
	for(int i=pos;i>=1;i-=i&-i) res+=tr[i];
	return res;
}

inline void swp(int x,int y)
{
	swap(b[x],b[y]);
	ans[++tot]=(node){min(x,y),max(x,y)};
}

inline void slove(int x,int y)
{
	auto p=st.begin();
	while(p!=st.end()) swp(x,*p++);
	swp(x,y);
	p=st.end();
	while(p!=st.begin()) swp(y,*--p);
}

int main()
{
	freopen("c.in","r",stdin);
	freopen("c.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]),b[i]=i;
	int tmp=n*(n-1)/2&1;
	for(int i=n;i>=1;i--) tmp^=que(a[i])&1,add(a[i],1);
	if(tmp!=0) return puts("NO"),0;
	else puts("YES");
	for(int i=1;i<=n;i++) st.insert(i);
	while(1)
	{
		int pos=-1;
		for(int i=1;i<=n;i++) if(b[i]!=a[i]) pos=i;
		if(pos==-1) break;
		for(int i=1;i<=n;i++) if(i!=pos&&b[i]!=a[pos]&&st.count(i)) swp(pos,i);
		for(int i=1;i<=n;i++)
		{
			if(b[i]==a[pos])
			{
				swp(pos,i);
				break;
			}
		}
		st.erase(pos);
	}
	while(st.size()>=4)
	{
		int x=*st.begin();st.erase(x);
		int y=*st.begin();st.erase(y);
		int z=*st.begin();st.erase(z);
		int w=*st.begin();st.erase(w);
		slove(x,y);
		slove(z,w);
		swp(x,z),swp(y,w);
		swp(x,w),swp(y,z);
	}
	for(int i=1;i<=tot;i++) printf("%d %d\n",ans[i].x,ans[i].y);
	return 0;
}