JZOJ 6307. 安排（归并排序+分治）

JZOJ6307. 安排

题目

Description

Input

Output

Sample Input

6
1 3 5 6 4 2
1 2 3 4 5 6

Sample Output

4
2 3
3 6
2 5
4 5

Data Constraint

Hint

题解

• 这是一道奇妙的题！！！！！
• 定义：交换两个数时，若这两个数分别是这段区间的最大值和最小值，则称此交换为合法的。
• 最暴力的做法，直接做一遍冒泡排序，每次都是相邻的两个数，所以一定是合法的。
• 虽然这样做时间是稳定且可过的，但最大交换次数达到了$\frac{n^2}{2}$，无法满足最大操作次数限制。
• 所以需要考虑更优秀的方法，目的是减少交换次数。
• 因为操作是可逆的，所以可以先使两个序列$A$和$B$经过若干操作变成$[1-n]$的升序序列，再将$A$的操作过程与$B$的操作过程的反向连接，即为最终答案。
• 这么做相当于采用若干次合法的交换使原序列排序，那考虑各种优秀的排序方法，
• 不妨考虑在归并排序的基础上进行：
• 当前有两个升序的序列$p[1-ps]$和$q[1-qs]$，需要将它们用合法的交换来合并，
• 一、若$p[ps]<q[1]$，则不需要任何交换，直接合并。它们是形如这样的：
  
• 二、否则两个序列一定是形如这样的：
  
• 接下来再运用分治（不是归并排序的分治，而是另一个），快速地进行合法交换，
• 1、找到一个最大的$t$，使$p$的后$t$个数严格大于$q$的前$t$个数（$t\le ps,qs$），
  
• 2、使这两段的$t$个数分别首尾翻转（因为有序，所以一定合法），
  
• 3、此时这两段的$t$个数连起来也是有序的了，将它们一起首尾翻转，
  
• 4、这样左右就出现了类似最早的两段有序序列，再分别递归下去。
• 这样的操作次数是$n\log n$级别的，时间复杂度是$O(n{\log }^{2}n)$的。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 5000
int a[N],b[N],sum[2]={0,0};
int u[N],v[N],i;
struct
{
	int l,r;
}s[2][172840];
void count(int p[],int q[],int ps,int qs,int l1,int r1,int l2,int r2,int o)
{
	short P[N],Q[N];
	for(i=1;i<=ps;i++) P[i]=p[i];
	for(i=1;i<=qs;i++) Q[i]=q[i];
	if(!ps||!qs||P[ps]<=Q[1]) return;
	int x=ps,y=1,t=0;
	while(x>1&&y<qs&&P[x-1]>Q[y+1]) x--,y++,t++;
	for(int i=0;2*i<t;i++)
	{
		s[o][++sum[o]].l=r1-t+i,s[o][sum[o]].r=r1-i,swap(P[ps-t+i],P[ps-i]);
		s[o][++sum[o]].l=l2+i,s[o][sum[o]].r=l2+t-i,swap(Q[1+i],Q[1+t-i]);
	}
	for(i=0;i<=t;i++) 
	{
		s[o][++sum[o]].l=r1-i,s[o][sum[o]].r=l2+i;
		swap(P[ps-i],Q[1+i]);
	}
	x=y=0;
	for(i=1;i<ps-t;i++) u[++x]=P[i];
	for(i=ps-t;i<=ps;i++) v[++y]=P[i];
	count(u,v,ps-t-1,t+1,l1,r1-t-1,r1-t,r1,o);
	x=y=0;
	for(i=1;i<=t+1;i++) u[++x]=Q[i];
	for(i=t+2;i<=qs;i++) v[++y]=Q[i];
	count(u,v,t+1,qs-t-1,l2,l2+t,l2+t+1,r2,o);
}
void solve(int l,int r,int o)
{
	if(l==r) return;
	int mid=(l+r)/2;
	solve(l,mid,o),solve(mid+1,r,o);
	int ps=0,qs=0;
	for(i=l;i<=mid;i++) u[++ps]=a[i];
	for(i=mid+1;i<=r;i++) v[++qs]=a[i];
	count(u,v,ps,qs,l,mid,mid+1,r,o);
	ps=qs=0;
	for(i=l;i<=mid;i++) u[++ps]=a[i];
	for(i=mid+1;i<=r;i++) v[++qs]=a[i];
	int x=1,y=1;
	for(i=l;i<=r;i++) if(y>qs||(x<=ps&&u[x]<v[y])) a[i]=u[x++]; else a[i]=v[y++];
}
int main()
{
	int n,i;
	scanf("%d",&n);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	solve(1,n,0);
	for(i=1;i<=n;i++) scanf("%d",&a[i]);
	solve(1,n,1);
	printf("%d
",sum[0]+sum[1]);
	for(i=1;i<=sum[0];i++) printf("%d %d
",s[0][i].l,s[0][i].r);
	for(i=sum[1];i;i--) printf("%d %d
",s[1][i].l,s[1][i].r);
	return 0;
}