双调排序的正确性证明暨第八交响曲题解
推歌：Double Agent
好多题解都写的或多或少有问题（包括那篇 \(30\) 分钟速通），终于是整明白了。
首先给出双调序列的定义：满足一下条件之一的序列
- \(\exists k, \forall i<k,a_i>a_{i+1} \land \forall i>k,a_i<a_{i+1}\) 即是单谷。
- 其可以通过循环位移满足 1
注意到根据定义 \(5,6,7,6,5,1,2,3\) 是双调序列，因为其可以通过循环位移成 \(6,5,1,2,3,5,6,7\)，这里有很多题解都是错的，大多是说是单峰或单谷，GGrun 有 hack 1,2,8,7,6,5,4,3。
upd：这个 hack 是双调，或者说所有的单峰和单谷都是双调，hack 的地方是将它拆开后 1,2,4,3|6,5,8,7 中 6,5,8,7 不是单峰或单谷，但它是双调
过程不再解释，但是需要指出的是，双调序列满足从中间分成相等两段后依次经过 Batcher 比较器（即 Compare And Swap 操作）后满足左右两段都是双调序列并且左边所有值都小于右边所有值，并不需要重新构造。
如果这个结论是真的，那么整个算法的正确性是显然的，考虑证明这个结论。
首先应用高德纳的 \(0-1\) 原理，即对于任意排序算法，若其能对 \(0/1\) 序列排序，则其能对所有序列排序。
证明大致就是考虑二进制分解，其对于每一位都能排对。
考虑一个双调的 \(0/1\) 序列，容易发现其收尾相接一定最多只有连续的一段 \(1\)。
对于没有 \(1\) 或 \(0\)，算法显然正确。
然后考虑分讨 \(0/1\) 位置和划分区间，下面用 \(00011|10000\) 序列 \(0001110000\) 分成 \(00011\) 和 \(10000\) 两段。
-
形如 \(0011111000\) 的序列，即 \(1\) 是连续一段：
-
\(00001|11000\) 即划分到 \(1\) 和 \(1\) 中间：
容易发现其左边一定是前缀，右面一定是后缀，所以若两边的按位与不为 \(0\)，则经过交换后右边一定是连续的一段 \(1\)，左边经过将一定后缀变成 \(0\) 也一定最多存在一段连续的 \(1\)，满足定义。
若按位或是 \(0\)，其左边一定是 \(0\)，右边一定是一段前缀加一段后缀。
-
\(00110|00000\) 即没有划分到 \(1\) 和 \(1\) 中间：
容易发现其经过交换后右边一定是连续的一段 \(1\)，左边一定全是 \(0\)，满足定义。
-
类似分讨 \(11100011\)，即是前后缀的划分点，容易证明其算法的正确性。
Code
#include<bits/stdc++.h>
using namespace std;
using llt=long long;
using llf=long double;
using ull=unsigned long long;
#define endl '\n'
#ifdef LOCAL
FILE *InFile=freopen("in_out/in.in","r",stdin),*OutFile=freopen("in_out/out.out","w",stdout);
#else
FILE *InFile=freopen("symphony.in","r",stdin),*OutFile=freopen("symphony.out","w",stdout);
#endif
const int N=203;
int n,md;
struct V{int l,r,d; V(int a,int b,int c):l(a),r(b),d(c){}};
vector<V> aas[13];
void Srt(int l,int r,int d,vector<V> &c){
if(l==r) return ;
else{
int mid=l+r>>1;
for(int a=l,b=mid+1;a<=mid&&b<=r;++a,++b) c.emplace_back(a,b,d);
Srt(l,mid,d+1,c),Srt(mid+1,r,d+1,c);
}
}
void PSrt(int l,int r,int d,vector<V> &c){
int mid=l+r>>1;
for(int a=mid,b=mid+1;b<=r&&a>=l;--a,++b) c.emplace_back(a,b,d);
Srt(l,mid,d+1,c),Srt(mid+1,r,d+1,c);
}
void Slv(int l,int r,int d){
if(l==r) return ;
else{
int mid=l+r>>1; md=max(md,d);
Slv(l,mid,d+1),Slv(mid+1,r,d+1);
PSrt(l,r,0,aas[d]);
}
}
int main(){
ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
cin>>n; int r=1; while(r<n) r<<=1;
Slv(1,r,1);
int cnt=0;
for(int i=md;i;--i){
sort(aas[i].begin(),aas[i].end(),[](const V &a,const V &b){return a.d<b.d;});
int la=0;
for(auto k:aas[i]) if(k.r<=n) if(la!=k.d) ++cnt,la=k.d;
++cnt;
}
cout<<cnt<<endl;
for(int i=md;i;--i){
int la=0;
for(auto k:aas[i]) if(k.r<=n){
if(la!=k.d) cout<<endl,la=k.d;
cout<<"CMPSWP R"<<k.l<<" R"<<k.r<<' ';
}
cout<<endl;
}
}
P
