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

· · 题解

省选最简单的一题，经常打 CF 的这题应该可以一眼秒。

考虑一个很经典的性质，一个排列的区间 mex 等于它的补集的 min，这是因为数字 0 \sim n-1 在排列中正好出现了一次，所以未出现过的最小非负整数在区间外一定出现一次。

所以本题可以利用这个性质，考虑从前往后枚举左端点，固定右端点为 n，每次如果返回值变小，那么上一个数字必然是这个返回值，如果没有变小，则这个数字就大于这个返回值，可以贪心的取没有取过的数字中较小的，遇到 0 就从右到左按照类似的流程走。

本题有一个比较宽松的答案要求，仅需对于每一个 0 \le l \le r \le n-1，答案的 mex 和程序输出的 mex 相同即可，根据上面说的性质，这只和数组的前缀 min 和后缀 min 有关，所以这样做是正确的，询问次数刚好 n 次，可以通过。

:::success[参考代码]

#include "perm.h"
#include<set> 

using namespace std;

void init(int c, int t){
    return;
}

vector<int> perm(int n){
    vector<int> ans, r;
    vector<bool> vis;
    set<int> st;
    for(int i = 1; i <= n; i++) vis.push_back(0);
    int lst = 1e9, res, zero_pos = -1;
    for(int i = 1; i < n; i++){
        res = query(i, n-1);
        if(res < lst){
            ans.push_back(res);
            vis[res] = 1;
            lst = res;
        }
        else ans.push_back(-res);
        if(res == 0){
            zero_pos = i-1;
            break;
        }
    }
    if(zero_pos != -1){
        lst = 1e9;
        for(int i = n-2; i >= zero_pos; i--){
            res = query(0, i);
            if(res < lst){
                r.push_back(res);
                vis[res] = 1;
                lst = res;
            }
            else r.push_back(-res);
        }
        for(int i = (int)r.size()-1; i >= 0; i--) ans.push_back(r[i]);
    }
    else ans.push_back(0);
    for(int i = 0; i < n; i++){
        if(!vis[i]) st.insert(i);
    }
    for(int i = 0; i < n; i++){
        if(ans[i] < 0){
            auto it = st.upper_bound(-ans[i]);
            ans[i] = *it;
            st.erase(it);
        }
    }
    return ans;
}

:::