思路

题意简述：给定长度为 $2^N$ 的排列，每次操作可以翻转任意一个起点为 $2^b$ 的倍数、长度为 $2^b$ 的区间（即翻转一个与二进制分治结构对齐的 $2^b$ 长度块）。可以进行任意多次操作，求能达到的字典序最小的排列。

把数组看成一棵完全二叉树（线段树结构）：根是整段，每个结点对应一个长度为 $2^k$ 且对齐的区间，其左右孩子是长 $2^{k-1}$ 的两个半区。

关键性质：

• 翻转一个长为 $2^{k-1}$ 的块是允许的操作，所以任意一个半区都可以单独翻转；
• 翻转一个长为 $2^k$ 的块，等价于“交换左右两个半区，并把两个半区各自反转”。由于两个半区各自的反转也都能单独完成，把这三个操作复合起来，就能实现“只交换左右半区、不改变半区内部顺序”；
• 因此在一个块内，我们能做的是：先分别把左右半区变成各自可达的最优排列，再决定两个半区谁在前谁在后（不能把元素任意穿插）。

于是得到分治算法 merge(l,r)：

1. 区间长度为 1 时直接返回。
2. 递归处理左右两半，使它们各自达到字典序最小的可达状态。
3. 取出此时的两半，用 vector 的字典序比较（min/max）决定顺序：字典序较小的一半放在前面，较大的一半放在后面。
4. 把选定的顺序写回原数组。

正确性：归纳证明。长度为 1 的块显然最优。设左右半区已经各自取得最优排列 $A$、$B$。块内可达的排列只可能是 $(A',B')$ 或 $(B',A')$，其中 $A'$、$B'$ 分别是两半可达的排列；而字典序最小的 $A'=A$、$B'=B$。两种放置中，首元素较小者更优，即把 $\min(A,B)$ 放前面，故 min(A,B) + max(A,B) 就是本块的最优解。自底向上递归，最终根结点就是全局最小可达排列。

复杂度：递归深度 $O(\log n)$；每一层对所有元素各复制、比较一次，总计 $O(n\log n)$ 时间（$n=2^N$）。空间上递归栈 $O(\log n)$，合并用的临时向量峰值为 $O(n)$。

代码

#include<bits/stdc++.h>
#define int long long
#define dd double
#define str string
#define el cout << endl
#define re return
#define ff first
#define ss second
#define pll pair<int,int>
#define pdd pair<dd,dd>
#define all(x) x.begin(),x.end()
#define pb push_back
#define sz(x) (int) x.size()
using namespace std;

int n;
vector<int>v;

// 分治：把区间 [l,r] 调整为该块可达的字典序最小排列
void merge(int l,int r){
    if(l==r){
        return;
    }

    // 先递归处理左右两个半区
    int m = (l+r)/2;
    merge(l,m);
    merge(m+1,r);

    // 取出左右半区当前（已是最优）的排列
    vector<int>a,b;
    for(int i=l;i<=m;i++){
        a.pb(v[i]);
    }
    for(int i = m+1;i<=r;i++){
        b.pb(v[i]);
    }

    // 按 vector 的字典序比较，较小的一半放前面
    vector<int>mi,ma;
    mi = min(a,b);
    ma = max(a,b);

    for(int i=l,j=0 ; i<=m ; i++,j++){
        v[i] = mi[j];
    }

    for(int i=m+1,j=0 ; i<=r ; i++,j++){
        v[i] =ma[j];
    }
}

void go(){
    cin>>n;
    // 输入的是指数 N，实际长度为 2^N
    n = 1<<n;
    v.assign(n,0);
    for(int i=0;i<n;i++){
        cin>>v[i];
    }
    merge(0,n-1);

    // 输出字典序最小的可达排列
    for(int i=0;i<n;i++){
        cout<<v[i]<<' ';
    }
    el;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);cout.tie(nullptr);
    int t=1;
    cin >>t;
    // 多组测试数据
    while(t--){
        go();
    }
    return 0;
}