看到 \(i\) 和 \(\lfloor \frac{i}{2} \rfloor\)，考虑一颗二叉树。题目的操作相当于按顺序交换当前节点和左右儿子的权值。
假设当前考虑的节点为 \(id\)，左儿子为 \(ls\)，右儿子为 \(rs\)，当前这些点的值分别为 \(A,B,C\)。
因为 \(id\) 的位置最靠前，最终又要字典序最小，所以要尽可能让 \(a_{id}\) 最小。
分三种情况讨论：
- \(\min(A,B,C)=A\)
肯定都不交换，因为要贪心地使 \(a_{id}\) 最小，如果交换了任意一个的话 \(a_{id}\) 就肯定大于 \(A\) 了。
- \(\min(A,B,C)=B\)
因为要让 \(a_{id}\) 最小，所以肯定会交换 \((id,ls)\)，并且不会交换 \((id,rs)\)。
- \(\min(A,B,C)=C\)
会发现肯定要交换 \((id,rs)\)，但是不确定要不要交换 \((id,ls)\)，也就是不确定 \(A\) 放左边还是 \(B\) 放左边。直接贪心肯定不行，我们假设 \(mn = \min(A,B)\)。定义函数 \(f(id,val)\) 表示将当前节点为 \(id\)，值为 \(val\)，最终 \(val\) 的位置在哪。看 \(mn\) 放哪边的最终位置（即 \(f(ls,mn)\) 和 \(f(rs,mn)\)）更小即可。为啥？因为若 \(mn\) 不放最终位置更小的那边，那么这个位置的值肯定会更大，而放这个位置的话影响的位置更靠后，所以放小的这边更优。
那如何求 \(f(id,val)\) 呢，会发现对于同一个 \(id\)，可能的 \(val\) 只有 \(\log\) 个（\(id\) 的祖先以及祖先的兄弟节点），那直接暴力转移再记忆化一下即可。
时间复杂度的瓶颈在求 \(f\)，复杂度 \(O(n \log^2 n)\)。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 4e5 + 10;
int n,a[MAXN],ans[MAXN];
#define ls id << 1
#define rs id << 1 | 1
map <int,int> mp[MAXN];
inline int dfs(int id,int val) {
if(mp[id].count(val)) return mp[id][val];
int res = id,A = val,B = a[ls],C = a[rs];
if(B == 0 && C == 0) res = id;
else if(C == 0) {
if(B < A) res = ls;
else res = id;
} else {
if(A < B && A < C) res = id;
else if(B < A && B < C) res = dfs(ls,val);
else {
int mx = max(A,B),mn = min(A,B);
int LS = dfs(ls,mn),RS = dfs(rs,mn);
if(A < B) res = min(LS,RS);
else {
if(LS < RS) res = dfs(rs,val);
else res = dfs(ls,val);
}
}
} return mp[id][val] = res;
}
inline void solve(int id) {
int A = a[id],B = a[ls],C = a[rs];
if(B == 0 && C == 0) return;
else if(C == 0) {
if(B < A) swap(a[id],a[ls]);
return;
} else {
if(A < B && A < C) solve(ls),solve(rs);
else if(B < A && B < C) {
swap(a[id],a[ls]);
solve(ls),solve(rs);
} else {
a[id] = C;
int mx = max(A,B),mn = min(A,B);
int LS = dfs(ls,mn),RS = dfs(rs,mn);
if(LS < RS) a[ls] = mn,a[rs] = mx;
else a[rs] = mn,a[ls] = mx;
solve(ls),solve(rs);
}
} return;
}
signed main() {
cin >> n;
for(int i = 1;i <= n;i++) cin >> a[i];
solve(1);
for(int i = 1;i <= n;i++) cout << a[i] << " ";
return 0;
}