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

_O_v_O_ · 2026-03-08 15:00:54 · 题解

注意到题目中的主角是小 H。所以让我们考虑 Ri 大手子。

本文下标 1 开头。

排列，\operatorname{mex}，考虑 冷光 的经典结论，这题有个结论，就是 \operatorname{mex}_{i=l}^r p_i=\min_{1\le i<l\lor r<i\le r} p_i。

设 pr_i 为 p 的前缀 \min，su_i 为 p 的后缀 \min，那么我们一次询问 [l,r] 实际就是告诉你 \min(pr_{l-1},su_{r+1})，pr_0=su_{n+1}=n+1。

同时有两个东西取 \min 太困难了，但事实上我们每次询问的 l=1 或 r=n，就能知道一个 pr 或者 su。而我们知道 pr 和 su 后就能进而构造出一个排列。

全部询问出来要 2n 次，但事实上假如我们知道 0 的位置为 i 那么 i 后面的 pr 和前面的 su 全部为 0，所以我们只需要询问 n 次即可。

场上代码不到 1K，非常简短。

一份能通过 qoj 的代码：

#include<bits/stdc++.h>
#include"perm.h"
using namespace std;

const int N=3e4+5;
int p[N],pre[N],suf[N];
void init(int c,int t){}
vector<int> perm(int n){
    for(int i=1;i<=n;i++) p[i]=pre[i]=suf[i]=0;
    pre[0]=suf[n+1]=n+1;
    int x=n+1;
    for(int i=1;i<n;i++){
        pre[i]=query(i,n-1);
        if(!pre[i]){
            x=i;
            break;
        }
    }
    for(int i=n;i>x;i--){
        suf[i]=query(0,i-2);
    }
    set<int> st;
    for(int i=0;i<n;i++) st.insert(i);
    for(int i=1;i<=n;i++){
        if(pre[i]!=pre[i-1]){p[i]=pre[i];st.erase(pre[i]);}
        if(suf[i]!=suf[i+1]){p[i]=suf[i];st.erase(suf[i]);}
    }
    for(int i=1;i<=n;i++){
        if(p[i]||i==x) continue;
        int mx=max(pre[i],suf[i]);
        mx=*st.lower_bound(mx);
        p[i]=mx;st.erase(mx);
    }
    vector<int> res;
    for(int i=1;i<=n;i++) res.push_back(p[i]);
    return res;
}