题目链接 (opens new window)

题目大意：给 $n$ 个数的排列（互不相同），一次操作可以选择一个子序列，将子序列按照原来顺序移动至最前，其余元素按照原来顺序放在最后。问最小操作次数和一种可行的操作方案。

input:
6
6 5 2 4 1 3

output:
3
6 5 2 4 1 3
6 4 1 5 2 3
6 1 2 3 4 5
1 2 3 4 5 6

一开始看的是 CTSC 2008 曹钦翔《数据结构的提炼与压缩》这篇论文。结果按照他的算法写，一直 wa，花了不少时间，太气人了（也可能是我的问题因为我没看论文里的证明）。最后在 discuss 里才看到正解。

网上似乎没什么题解，那就我来写一个吧。

算法如下：

1. 若序列已经递增，停止算法。
2. 把序列分割成尽可能少的递增子序列，满足子序列内相邻两个数都相差 1。比如 $[6,5,2,4,1,3]$ 的分割为 $[6][5][2,3][4][1]$。
3. 将子序列排序（以第一个元素为关键字）。我们把它称为原序列的有序分割。比如 $[6][5][2,3][4][1]$ 排序后为 $[1][2,3][4][5][6]$。
4. 将位置在奇数的子序列合并在一起，记为集合 $A$，位置在偶数的子序列合并在一起，记为集合 $B$。比如 $[1][2,3][4][5][6]$ 中奇数位的 $[1][4][6]$ 合并为 $A=\{1,4,6\}$，偶数位是 $[2,3][5]$ 合并为 $B=\{2,3,5\}$。
5. 回到原序列，把在集合 $A$ 中的元素看作操作里的子序列，进行一次操作，回到第 1 步。比如 $[6,5,2,4,1,3]$ 中操作子序列 $[6,4,1]$ 变为 $[6,4,1,5,2,3]$，接下来操作 $[6,1,2,3]$ 变为 $[6,1,2,3,4,5]$，接下来操作 $[1,2,3,4,5]$ 变为 $[1,2,3,4,5,6]$，停止算法。

上述算法每一步操作是 $O(n\log n)$ 的，足以过这题。当然事实上，先记录一下 pos[a[i]]=i，即 $i$ 在 a[1..n] 中的位置。如果 pos[i]>pos[i+1] 表示数字 $i$ 在数字 $i+1$ 的后面，我们就在 $i$ 和 $i+1$ 中间断开。这样就直接得到第 3 步得到的有序分割，可以 $O(n)$ 处理每一步操作。

又由于操作数为 $O(\log n)$，总复杂度 $O(n\log n)$。

那么为什么这么做是正确的呢？或者说怎么证明操作数 $O(\log n)$？感性地来说，就是第 3 步得到的有序分割（比如 $[1][2,3][4][5][6]$），因为所有奇数位将会排到偶数位之前，所以可以看作奇数位和它后面相邻的子序列进行了合并。比如 $[1]$ 一定排到 $[2,3]$ 之前，那么在下次操作后 $[1,2,3]$ 一定是作为一个子序列出现的，$[4]$ 和 $[5]$ 同理。这样，有序分割的大小就会小一半。这个操作看似是归并排序反过来的操作，但是本质和归并排序是一样的思想，真是神奇。

#include <bits/stdc++.h>
using namespace std;
#define repeat(i,a,b) for(int i=(a),_=(b);i<_;i++)
#define repeat_back(i,a,b) for(int i=(b)-1,_=(a);i>=_;i--)
const int N=200010; typedef long long ll; ll read(){ll x; if(scanf("%lld",&x)!=1)exit(0); return x;}
int n,a[N],b[N],f[N],A[N],pos[N];
// f[i]标记了a[i]是有序分割中第几个子序列的元素，pos含义见题解
void print(){
    repeat(i,1,n+1)
        printf("%d%c",a[i]," \n"[i==n]);
}
int getcnt(){ // 得到有序分割的大小
    repeat(i,1,n+1)pos[a[i]]=i;
    int cnt=1;
    repeat(i,1,n+1){
        if(i>1 && pos[i-1]>pos[i])cnt++;
        f[pos[i]]=cnt;
    }
    return cnt;
}
void work(){ // 进行一次操作
    getcnt();
    int t=0;
    repeat(i,1,n+1)if(f[i]%2==1)b[++t]=a[i];
    repeat(i,1,n+1)if(f[i]%2==0)b[++t]=a[i];
    copy(b+1,b+n+1,a+1);
}
void Solve(){
    n=read();
    repeat(i,1,n+1){
        A[i]=a[i]=read();
    }
    int ans=0;
    while(getcnt()!=1){
        work();
        ans++;
    }
    copy(A+1,A+n+1,a+1);
    printf("%d\n",ans);
    print();
    repeat(i,0,ans){
        work();
        print();
    }
}
signed main(){
    //freopen("data.txt","r",stdin);
    int T=1; //T=read();
    repeat(ca,1,T+1){
        Solve();
    }
    return 0;
}