题意

给定长度为 的序列 ，给定操作 为 ，构造不超过 步的操作序列排序 。

思路

我有 4 种单 log 做法，每一种都跑满了。

我们发现如果按照题目给的方法来做，很难有操作空间，因为操作一次某个我们想要的数最多往前挪距离的一半。

这个时候我们按照构造题的常见套路选择反过来做，把有序数组变为 ，操作变为区间拆成两块后再重排。你发现这样如果某个数想要往右移，我们可以将区间往左拓展来控制它往右移多少。

具体的，如果我们操作 ，那么就可以将 上的数移到 ，我们发现位移大小就可以随便定了。

但是这样并不是所有数都是一步完成的，一些在左边的数会需要先倍增个几次，然后才能跳出去。

算算期望复杂度，你发现，对不起我不会发现，柿子是抄的： 这样一上来随意扰动一下即可。

CODE

#include<cstdio>
#include<vector>
#include<random>
#include<chrono>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=3010,FSIZE=1<<26;
int n,a[N],b[N];
mt19937 rnd(chrono::steady_clock().now().time_since_epoch().count());
vector<pair<int,int>> ans;
char BuF[FSIZE],*InF=BuF;
template<typename T>void read(T &x){
    for(;*InF<33;++InF);
    for(x=0;*InF>32;x=x*10+(*InF++^48));
}
void change(int l,int r){
    ans.emplace_back(l,r);
    for(int i=l,mid=(l+r+1)>>1,cnt=0;i<=mid;++i){
        b[cnt++]=a[mid+i-l];
        b[cnt++]=a[i];
    }
    memcpy(a+l,b,(r-l+1)<<2);
}
int main(){
    fread(BuF,1,FSIZE,stdin);
    read(n);
    for(int i=1,x;i<=n;++i){read(x);a[x]=i;}
    for(int i=1;i<=100;++i){
        int l=rnd()%n+1,r=rnd()%n+1;
        if(l>r) swap(l,r);
        if(l<r) change(l,r);
    }
    for(int i=n;i;--i){
        int p=find(a+1,a+i+1,i)-a;
        for(;p+p<=i;change(1,p<<=1));
        if(p!=i) change(p+p-i+1,i);
    }
    reverse(ans.begin(),ans.end());
    printf("%lld\n",ans.size());
    for(auto [i,j]:ans) printf("%d %d\n",i,j);
    return(0);
}