传送门

他既然要求字典序最小,那我们就一个个大力贪心模拟选哪个就好了。对于每个点,它跟儿子的交换可能是确定的,可能是不确定的(当右儿子小于左儿子的时候就不确定,因为不知道交换完之后左右儿子分别对应哪个值会比较优,需要留到后面处理)。从小到大考虑每个点,我们沿着不确定的点一直向上走,就能得到这个点可能取到的值。因为字典序要最小,所以我们选其中最小的一个值。这时候有三种情况,一个是这个最小值比左儿子大,且左儿子小于右儿子,这时最优的方案显然是把这个点跟左儿子交换;第二种情况是最小值大于右儿子,且右儿子小于左儿子,这时的情况就不确定了,但这个点取到的值一定就是右儿子的值,剩下两个值怎么分配留到后面去处理;最后一种情况就是不跟儿子交换,直接取上面换下来的值,这样我们就可以一路往上,把所有不确定方向的点都改为确定方向,直到碰到那个最小值的点为止。这样就在$O(n\log n)$的时间内做完了。

感觉这题可以出到一般的二叉树上?把暴力跳换成数据结构是不是就行了呢?

#include <cstdio>
#include <cstring>
#define MAXN 200010

int n;
int v[MAXN],v2[MAXN],d[MAXN];

int gao(int x){
    int minv=n+1;
    for(int i=x>>1,j=x;;i>>=1,j>>=1){
        if(d[i]==-1){
            if(v2[i]<minv) minv=v2[i];
        }else if(i*2+d[i]!=j){
            if(v[j]<minv) minv=v[j];
            break;
        }
    }
    int c1=x<<1,c2=x<<1|1;
    if(c1>n) c1=0;
    if(c2>n) c2=0;
    if(minv<v[c1] && minv<v[c2]){
        d[x]=2;
        v2[x]=n+1;
        for(int i=x>>1,j=x;;i>>=1,j>>=1){
            if(d[i]==-1){
                if(v2[i]!=minv){
                    d[i]=j-i*2;
                    v[j^1]=v2[i];
                }else{
                    d[i]=(j-i*2)^1;
                    v[j]=v2[i];
                    break;
                }
            }else if(i*2+d[i]!=j){
                d[j]=2;
                break;
            }
        }
        return minv;
    }else if(v[c1]<v[c2]){
        d[x]=0;
        v2[x]=v[c2];
        return v[c1];
    }else{
        v2[x]=v[c1];
        return v[c2];
    }
}

int main(){
#ifdef DEBUG
    freopen("140.in","r",stdin);
#endif
    scanf("%d",&n);
    v[0]=n+1;
    memset(d,-1,sizeof d);
    d[0]=2;
    for(int i=1;i<=n;i++) scanf("%d",v+i);
    for(int i=1;i<=n;i++) printf("%d ",gao(i));
    return 0;
}