为了方便，以下编号和下标范围均为\([0,2^{n})\)
定义
\[\begin{cases}f_{0}(a)=a\\f_{i+1}(a)_{j}=\begin{cases}\min(f_{i}(a)_{j},f_{i}(a)_{j+2^{i}})&j二进制下第i位为0\\\max(f_{i}(a)_{j},f_{i}(a)_{j-2^{i}})&j二进制下第i位为1\end{cases}&i\in [0,n)\end{cases} \]记初始编号序列为\(a_{i}\)，则最终排名序列即\(a'_{j}=f_{n}(a)_{\overline{j}}\)（其中\(\overline{j}\)为\(j\)二进制下翻转）
不妨将\(j\rightarrow \overline{j}\)在限制中实现，即钦定了\(f_{n}(a)\)中的若干个位置
结论：\(\forall i\in [0,n),j\)二进制下第\(i\)位为\(0\)，有\(f_{n}(a)_{j}<f_{n}(a)_{j+2^{i}}\)
对\(n\)从小到大归纳，当\(n=0\)时显然成立，考虑\(n=m+1\)时：
反证法，假设存在\(i\in [0,m],j\)二进制下第\(i\)位为\(0\)满足\(f_{m+1}(a)_{j}>f_{m+1}(a)_{j+2^{i}}\)
若\(j\)二进制下第\(m\)位为\(0\)，代入后即\(\min(f_{m}(a)_{j},f_{m}(a)_{j+2^{m}})>\min(f_{m}(a)_{j+2^{i}},f_{m}(a)_{j+2^{i}+2^{m}})\)
根据归纳假设，有\(\begin{cases}f_{m}(a)_{j}<f_{m}(a)_{j+2^{i}}\\f_{m}(a)_{j+2^{m}}<f_{m}(a)_{j+2^{i}+2^{m}}\end{cases}\)，显然矛盾
类似的，\(j\)二进制下第\(m\)位\(1\)即将\(\min\)改为\(\max\)，同样矛盾
推论：存在\(f_{n}(a)=g\iff \forall i\in [0,n),j\)二进制下第\(i\)位为\(0\)，有\(g_{j}<g_{j+2^{i}}\)
（必要性根据结论显然，充分性取\(a=g\)即有\(f_{n}(a)=g\)）
换言之，问题即将未钦定的位置填满，使得其满足上述条件
仅根据钦定的位置，求出每个所有位置的上下界，并从小到大贪心填数即可
具体的，填左端点$\le $当前数、右端点最小的为中自身最小的数即可
另外，对于未钦定位置之前的限制，通过这样的贪心显然也可以满足
用set维护即可，时间复杂度为\(O(n2^{n})\)
#include<bits/stdc++.h>
using namespace std;
const int N=300000;
int n,rev[N],a[N],l[N],r[N];
vector<pair<int,int> >v[N];
set<pair<int,int> >S;
int main(){
scanf("%d",&n);
for(int i=0;i<(1<<n);i++)rev[i]=((rev[i>>1]>>1)|((i&1)<<n-1));
for(int i=0;i<(1<<n);i++)scanf("%d",&a[rev[i]]);
for(int i=0;i<(1<<n);i++){
l[i]=(a[i] ? a[i]-1 : 0);
r[i]=(a[i] ? a[i]-1 : (1<<n)-1);
}
for(int i=0;i<n;i++)
for(int j=0;j<(1<<n);j++)
if ((j>>i)&1){
l[j]=max(l[j],l[j^(1<<i)]);
r[j^(1<<i)]=min(r[j^(1<<i)],r[j]);
}
for(int i=0;i<(1<<n);i++)
v[l[i]].push_back(make_pair(r[i],i));
for(int i=0;i<(1<<n);i++){
for(pair<int,int>j:v[i])S.insert(j);
if ((S.empty())||((*S.begin()).first<i)){
puts("NO");
return 0;
}
a[(*S.begin()).second]=i+1,S.erase(S.begin());
}
puts("YES");
for(int i=0;i<(1<<n);i++)printf("%d ",a[i]);
return 0;
}