题目大意

给定一个长度为 $n$ 的数组 $a$，元素值在 $[1,n]$ 范围内。你可以在一个 $n \times n$ 的网格上从 $(1,1)$ 走到 $(n,n)$，每次只能向右或向下走一步。当你踏入格子 $(i,j)$ 时，若 $i \neq j$，则交换 $a_i$ 和 $a_j$。你需要用不超过 $n+4$ 次这样的行走将数组排成非降序。

---

核心思想

$1$. 奇偶排序与行走的对应关系

首先，我们需要理解一条路径对应的交换操作。考虑一条路径经过的格子序列：

$$(1,1) \to (1,2) \to (2,2) \to (2,3) \to (3,3) \to \dots $$

当路径经过 $(i,i)$ 和 $(i,i+1)$ 时，会依次交换 $(a_i, a_{i+1})$。这样的路径实际上对应了一次冒泡排序的奇偶阶段。

更一般地，考虑路径：

$$(1,1) \to (1,p_1) \to (2,p_1) \to (2,p_2) \to (3,p_2) \to \dots \to (k,p_k) \to \dots \to (n,n) $$

忽略其他格子，这条路径执行了：

$$swap(a_1, a_{p_1}),\ swap(a_2, a_{p_2}),\ \dots,\ swap(a_k, a_{p_k}) $$

我们可以利用这个结构，在单次行走中执行多个指定位置的交换。

---

$2$. 困难版本与简单版本的区别

在简单版本中，每次奇偶排序后需要额外操作将最小值移到位置 $1$，导致总操作数为 $\Theta(n)$。困难版本要求将操作数优化到 $n+4$，因此需要打破这个瓶颈。

---

$3$. 分治思想：划分大小两类数

设 $S$ 表示值 $\le \lfloor n/2 \rfloor$ 的数，$B$ 表示值 $> \lfloor n/2 \rfloor$ 的数。
目标：将数组排成 $[S,\dots,S,B,\dots,B]$ 的形式。

$3.1$ 如何得到 $[S,\dots,S,B,\dots,B]$

首先，执行一次操作将 $a_1$ 变为 $n$（最大值）。
然后选择 $n/2$ 个位置 $p_1, p_2, \dots, p_{n/2}$（$1 < p_1 < p_2 < \dots < p_k \le n$），通过一条路径执行：

$$swap(a_1, a_{p_1}), swap(a_2, a_{p_2}), \dots$$

通过精心选择 $p_i$，可以使得最终数组形如 $[S,\dots,S,B,\dots,B]$。

---

$4$. 核心过程：交替排序

假设当前数组为 $[S,\dots,S,B,\dots,B]$。

$4.1$ 第一轮变换

$[S,\dots,S,B,\dots,B] \to [S,\dots,S,B,\dots,B,S] \to [S,\dots,S,B,\dots,B,S,S] \to \dots \to [B,\dots,B,S,\dots,S]$

在这个过程中，我们只对 $B$ 部分进行奇偶排序（每次将末尾的 $S$ 逐步移到前面）。

$4.2$ 第二轮变换

$[B,\dots,B,S,\dots,S] \to [B,\dots,B,S,\dots,S,B] \to \dots \to [S,\dots,S,B,\dots,B]$

这次只对 $S$ 部分进行奇偶排序。

经过若干轮后，数组完全有序。关键在于，每次奇偶排序只需 $O(n)$ 步，但这里我们通过巧妙构造，使得每轮变换中不需要额外操作将最小值移到开头，从而将总操作数控制在 $n+4$ 内。

---

$5$. 奇数的处理

当 $n$ 为奇数时，需要额外两次操作来处理中间元素，因此总操作数不超过 $n+4$。

---

$6$. 路径构造

代码中实现了几个关键函数：

• $path1(num)$：走对角线路径，执行相邻交换。
• $path2(num)$：走 $(1,1)\to(1,n)\to(n,n)$ 路径。
• $path3(num, p)$：执行 $swap(a_1,a_{p_0}), swap(a_2,a_{p_1}), \dots$。
• $walk1(j)$：执行 $swap(a_{j-1}, a_{j+1})$。
• $walk2(j)$：执行 $swap(a_{j-1}, a_j)$ 和 $swap(a_j, a_{j+1})$。
• $walk3(j)$：执行 $swap(a_{j-1}, a_j)$。

这些基本操作组合起来，可以实现任意需要的交换模式。

---

完整代码

#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
#include <bitset>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=2010;
int T,n,tot;
int a[N];
vector<int> X[N],Y[N];

void path1(int num)  //(1,1)->(1,2)->(2,2)->(2,3)->(3,3)->...
{
	for(int i=1;i<=n;i++)
	{
		X[num].push_back(i),Y[num].push_back(i);
		if(i!=n)
		{
			X[num].push_back(i),Y[num].push_back(i+1);
			swap(a[i],a[i+1]);
		}
	}
}

void path2(int num) //(1,1)->(1,n)->(n,n)
{
	for(int i=1;i<=n;i++)
	{
		X[num].push_back(1),Y[num].push_back(i);
		swap(a[1],a[i]);
	}
	for(int i=2;i<=n;i++)
	{
		X[num].push_back(i),Y[num].push_back(n);
		swap(a[i],a[n]);
	}
}

void path3(int num,vector<int> p) //swap(1,p[0]),(2,p[1]),... note p[0]!=1
{
	for(int i=1;i<=p[0];i++)
	{
		X[num].push_back(1),Y[num].push_back(i);
		swap(a[1],a[i]);
	}
	for(int i=1;i<p.size();i++)
	{
		for(int j=p[i-1];j<=p[i];j++)
		{
			X[num].push_back(i+1),Y[num].push_back(j);
		    swap(a[i+1],a[j]);
		}
	}
	int x=p.size(),y=p.back();
	while(x!=n)
	{
	    x++;
	    X[num].push_back(x),Y[num].push_back(y);
		swap(a[x],a[y]);
	}
	while(y!=n)
	{
	    y++;
	    X[num].push_back(x),Y[num].push_back(y);
		swap(a[x],a[y]);
	}
}

void walk1(int j)
{
	X[tot].push_back(j-1),Y[tot].push_back(j);
	X[tot].push_back(j-1),Y[tot].push_back(j+1);
    X[tot].push_back(j),Y[tot].push_back(j+1);
	X[tot].push_back(j+1),Y[tot].push_back(j+1);
    swap(a[j-1],a[j+1]);
}

void walk2(int j)
{
	X[tot].push_back(j-1),Y[tot].push_back(j);
	X[tot].push_back(j),Y[tot].push_back(j);
	X[tot].push_back(j),Y[tot].push_back(j+1);
	X[tot].push_back(j+1),Y[tot].push_back(j+1);
	swap(a[j-1],a[j]);
	swap(a[j],a[j+1]);
}

void walk3(int j)
{
	X[tot].push_back(j-1),Y[tot].push_back(j);
	X[tot].push_back(j),Y[tot].push_back(j);
	swap(a[j-1],a[j]);
}

void init()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	tot=0;
	for(int i=1;i<=3*n;i++) X[i].clear(),Y[i].clear();
	vector<pair<int,int> > pr;
	for(int i=1;i<=n;i++) pr.push_back(make_pair(a[i],i));
	sort(pr.begin(),pr.end());
	for(int i=1;i<=n;i++) a[pr[i-1].second]=i;
}

void step1()
{
	int p1,pn;
	vector<int> p;
	for(int i=1;i<=n;i++) if(a[i]==1) p1=i;
	if(p1!=1)
	{
        p.push_back(p1);
        path3(++tot,p);
	}
	if(n==2) return ;
	tot++;
	X[tot].push_back(1),Y[tot].push_back(1);
	for(int j=2;j<=n;j+=2)
	{
	    if(j+1>n) walk3(j);
	    else if(a[j]==n) walk1(j);
		else walk2(j);
	}
	p1=n;
	for(int i=1;i<=n;i++) if(a[i]==n) pn=i;
    p.clear();
    p.push_back(pn);p.push_back(p1);
    path3(++tot,p);
    p.clear();
    for(int i=1;i<=n;i++) if(a[i]<=(n+1)/2) p.push_back(i);
    path3(++tot,p);
}

void step2()
{
	int head;
	if(n&1)
	{
	    for(int t=1;t<=2;t++)
		{
            head=n/2+2;
            for(int i=1;i<=n/2+(t==1);i++)
            {
                tot++;
                X[tot].push_back(1),Y[tot].push_back(1);
                for(int j=2;j<=n;j++)
                {
                    if(!(head<=j&&j<=head+n/2-1)) walk3(j);
                    else if(j==head&&(head&1)) walk3(j);
                    else
                    {
                        if(!(head<=j+1&&j+1<=head+n/2-1)) walk3(j);
                        else if(a[j]>a[j+1]) walk1(j),j++;
                        else walk2(j),j++;
                    }
                }
                head--;
            }
		}
	}
	else
	{
		for(int t=1;t<=2;t++)
		{
            head=n/2+1;
            for(int i=1;i<=n/2;i++)
            {
                tot++;
                X[tot].push_back(1),Y[tot].push_back(1);
                for(int j=2;j<=n;j++)
                {
                    if(!(head<=j&&j<=head+n/2-1)) walk3(j);
                    else if(j==head&&(head&1)) walk3(j);
                    else
                    {
                        if(!(head<=j+1&&j+1<=head+n/2-1)) walk3(j);
                        else if(a[j]>a[j+1]) walk1(j),j++;
                        else walk2(j),j++;
                    }
                }
                head--;
            }
		}
	}
}

void output()
{
	printf("%d\n",tot);
	for(int i=1;i<=tot;i++)
	{
		for(int j=1;j<2*n-1;j++)
		{
		    if(X[i][j]==X[i][j-1]) printf("R");
		    else printf("D");
		}
		printf("\n");
	}
}

int main()
{
	scanf("%d",&T);
	while(T--)
	{
		init();
		step1();
		step2();
		output();
	}
	return 0;
}

---

时间复杂度分析

• 每次行走的路径长度为 $2n-2$，输出总长度 $O(kn)$。
• 由于 $k \le n+4$，且 $\sum n^2 \le 2.5\times 10^5$，总复杂度为 $O(\sum n^2)$，足以通过。

---

总结

本题的关键在于： $1$. 将行走路径映射到一系列交换操作。 $2$. 利用 $S$/$B$ 划分和交替排序，避免每次排序后单独移动最小值。 $3$. 精心构造基本路径（$walk1$、$walk2$、$walk3$、$path3$）来组合实现复杂交换。 $4$. 最终用不超过 $n+4$ 次行走完成排序。