河外塔（构造题）
聊机
·
·
题解
在高铁上过掉了这个题，因为没看到有人写题解，所以来填补一下空白。
做法：归并排序+卡常
首先数据范围要求我们用 \log 级的算法来解决这道题目，很显然的想到归并排序，可是当我细写的时候就发现并没有“排序套皮”这么简单。
我们需要把刚才的最后一次合并剪掉，这样常数才能满足要求。
如果我们不进行最后一次合并，那就说明我们进行排序完以后的这一段不在原本的柱子上，那你一开始分开的那两段排序完以后也不会在原本的柱子上，我们需要保证它们不会重叠在一起，所以我们需要规定一下让这两段排序完以后都去到哪个柱子，我们设当前这一段所在的柱子是 $p$，要去 $to$ 柱子，我们一开始要把前半段扔到 $to$ 柱子上，然后让后半段合并到 $3-p-to$ (就是另外一根柱子上），再让扔出去的前半段合并到 $p$ 柱子上，最后我们再把这两段合并到 $to$ 柱子上。我们还要注意的是，因为我们只进行了一次合并，所以顺序会颠倒，我们需要让每相邻的两层的排序方式相反。
AC code：
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N=4e4+2;
int n,a[N];
int tot,a1[N*50],a2[N*50];
#define endl '\n'
#define move(a,b) a1[++tot]=a,a2[tot]=b
#define put(a,b) cout<<(char)('A'+a)<<' '<<(char)('A'+b)<<endl
inline bool comp(int o,int x,int y) {
if(o) return x>=y;
else return y>=x;
}
bool cmp(int x,int y) {
return x>y;
}
void divid(int p,int l,int r,int to,int o) {//参数意义同分析
if(l==r) {
move(p,to);
return ;
}
int mid=(l+r)>>1,p2=3-to-p;
for(int i=l;i<=mid;i++) move(p,to);
for(int i=l,j=mid;i<=j;i++,j--) swap(a[i],a[j]);//这个reserve千万不要忘记！
divid(p,mid+1,r,p2,o^1);
divid(to,l,mid,p,o^1);
int i=l,j=mid+1;
while(i<=mid&&j<=r) {
if(comp(o,a[i],a[j])) move(p,to),++i;
else move(p2,to),++j;
}
while(i<=mid) move(p,to),++i;
while(j<=r) move(p2,to),++j;
if(o) stable_sort(a+l,a+r+1);
else stable_sort(a+l,a+r+1,cmp);
}
int main() {
ios::sync_with_stdio(0),cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>a[i];
divid(0,1,n,2,1);
cout<<tot<<endl;
for(int i=1;i<=tot;i++) put(a1[i],a2[i]);
return 0;
}
```
说实话卡常这一部分我想了很久，就从卡常这一点来说，我认为这还是一道很不错的构造题的。
题外话：建议管理更新一下提交记录，把弱化版的记录删除掉，这样我们才能看到更多关于这题更好的做法。