P15033 [UOI 2021 II Stage] 字典序 题解

· · 题解

题目传送门：P15033 [UOI 2021 II Stage] 字典序

题目分析

首先无解的充要条件显然是区间众数的出现次数大于 \lceil \dfrac n 2 \rceil。

考虑从前往后一个一个地放。为了让字典序最小，我们肯定想要放序列里最小的数——如果放完不会导致无解。

所以我们检查：如果放之前区间众数正好出现了 \lceil \dfrac n 2 \rceil 次，那现在只能放众数；否则放区间里最小的数。（这里的众数为最小的众数）

看起来无懈可击。（思考）

不兑，如果上一个放的也是当前最小数，现在再放不就炸了吗？这时为了最优，我们需要放当前次小数。

同理如果上一个放的也是区间最小众数，我们这回就要放最小数。

综上，我们维护当前剩下的数里区间最小众数 q_1，区间最小数 q_2 和区间次小数 q_3 即可。

单点修改、可合并，直接无脑上线段树。

代码实现

int n,vis[N],lst;
struct segment_tree{
    int u,l,r,mx,q1,q2,q3;
}s[N<<2];
void pushup(int u){
    s[u].mx=max(s[u<<1].mx,s[u<<1|1].mx);
    s[u].q1=((s[u].mx==s[u<<1].mx)?s[u<<1].q1:s[u<<1|1].q1);
    if(s[u<<1].q2==N)s[u].q2=s[u<<1|1].q2,s[u].q3=s[u<<1|1].q3;
    else s[u].q2=s[u<<1].q2,s[u].q3=min(s[u<<1].q3,s[u<<1|1].q2);
}
void build(int u,int l,int r){
    s[u].l=l,s[u].r=r;
    if(l==r){
        s[u].mx=vis[l];
        s[u].q1=l;
        s[u].q2=(vis[l]?l:N);
        s[u].q3=N;
    }
    else{
        build(u<<1,l,l+r>>1),build(u<<1|1,(l+r>>1)+1,r);
        pushup(u);
    }
}
void decrease(int u,int x){
    if(s[u].l==x&&x==s[u].r){
        if(!--s[u].mx)s[u].q2=N;
        return;
    }
    if(x<=s[u<<1].r)decrease(u<<1,x);
    else decrease(u<<1|1,x);
    pushup(u);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1,x;i<=n;i++){
        cin>>x;
        if(vis[x]++==n+1>>1){
            cout<<-1;
            return 0;
        }
    }
    build(1,1,N-1);
    for(int i=n;i;i--){
        if(s[1].mx==i+2>>1&&s[1].q1!=lst){
            cout<<s[1].q1<<' ';
            lst=s[1].q1;
            decrease(1,s[1].q1);
        }
        else if(s[1].q2!=lst){
            cout<<s[1].q2<<' ';
            lst=s[1].q2;
            decrease(1,s[1].q2);
        }
        else{
            cout<<s[1].q3<<' ';
            lst=s[1].q3;
            decrease(1,s[1].q3);
        }
    }
    return 0;
}

AC 记录。