P15652 [省选联考 2026] 排列游戏 / perm

zhlzt · 2026-03-08 14:56:58 · 题解

纯靠对 \text{mex} 的理解啊。我怎么做了 2.5h。

以下 \text{mex}(l,r) 等于 \text{query}(l,r) 的答案。

有一个大概的思路就是，先找到数 0 的位置，然后依次扩展区间覆盖数 1\sim n-1 的位置，最终即可覆盖排列 p。

假设当前区间覆盖了 0\sim i，区间为 [l,r]，则可以将 (i+1)\sim (\text{mex}(l,r)-1) 以任意顺序填入 [l,r] 中未被占用的位置，并令 i\gets \text{mex}(l,r)-1。此时 i+1 一定在当前区间外，确定其在区间的左侧还是右侧后线性扩展即可。但是做不到 n 次查询以内。

判断 i+1 是否在区间的左侧即判断 \text{mex}(0,r)>i+1（\text{mex}(l,n-1)\le i+1）是否成立。这启发我们把求区间 [l,r] 的 \text{mex} 转为求前后缀的 \text{mex}。由于是排列，所以 \text{mex}(l,r) 只在 [0,l-1] 和 [r+1,n-1] 中的一个内出现，进而 \text{mex}(l,r)=\min(\text{mex}(0,r),\text{mex}(l,n-1))。

出于需求，只要求出所有包含数 0 的形如 [0,r] 或 [l,n-1] 的区间的 \text{mex}。

从 1 开始枚举 l 直至 \text{mex}(l,n-1)=0，则 0 的位置即为此时的 l-1。之后从 l-1 开始枚举 r 直到 n-2，结合 \text{mex}(0,n-1)=n 即可在 n 次查询内完成。

代码中部分细节进行了简化。

:::success[排列游戏 - perm.cpp]

#include"perm.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=30005;
int dpl[maxn],dpr[maxn],pos[maxn],sta[maxn];
int c,t;
void init(int C,int T){
    c=C,t=T;
}
vector<int> perm(int n){
    int top=0;
    pos[0]=0;
    dpr[n-1]=n;
    for(int i=n-2;i>=0;i--){
        dpr[i]=query(0,i);
        if(dpr[i]==0){pos[0]=i+1;break;}
    }
    dpl[0]=n;
    for(int i=1;i<=pos[0];i++){
        dpl[i]=query(i,n-1);
    }
    int pl=pos[0],pr=pos[0],now=0;
    while(pl>0 or pr<n-1){
        ++now;
        if(dpr[pr]>now){
            pos[now]=pl;
            while(dpl[pos[now]]<=now) pos[now]--;
            for(int i=pos[now]+1;i<pl;i++) sta[++top]=i;
            pl=pos[now];
        }
        else{ // dpl[pl]>now
            pos[now]=pr;
            while(dpr[pos[now]]<=now) pos[now]++;
            for(int i=pos[now]-1;i>pr;i--) sta[++top]=i;
            pr=pos[now];
        }
        int val=min(dpr[pr],dpl[pl])-1;
        while(now<val) pos[++now]=sta[top--];
    }
    vector<int>res;
    for(int i=0;i<n;i++) res.push_back(0);
    for(int i=0;i<n;i++) res[pos[i]]=i;
    return res;
}

:::