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

· · 题解

首先考虑如果单组询问可以问 2n 个问题怎么做。

显然，\text{mex} 相当于“补集的最小值”，即 [l, r] 的 \text{mex} 相当于一段前缀和一段后缀的最小值。注意到这一点后，我们可以得出以下两条结论：

  1. 任意区间 \text{mex} 相同，等价于任意前缀或后缀的 \min 相同。

  2. 前缀 \text{mex} 等于后缀 \min，反过来同理。

不妨考虑把所有前缀 \text{mex} 和后缀 \text{mex} 都问一遍，这样需要恰好 2n 次询问，可以得到所有前缀 \min与后缀 \min。

接下来考虑构造。如果 [0, l) 的 \min 与 [0, l] 的 \min 不同，相当于确定了 p_l 的值，并且给 [0, l) 的数添加了一条限制。

因此，贪心地选择符合要求的数中最小的填上即可，使用你喜欢的数据结构维护。

下面考虑 n + \log n 次怎么做。

如果把表打下来，会发现里面大量的 0 是没用的（限制每个数 \geq 0 是没意义的）。

因此，不妨先通过二分的方法找到 0 的位置，然后左右分开查询 \text{mex}。

这样可以做到 n + \log n 次查询。

最后考虑怎么把 \log n 消掉。

注意到二分其实是没意义的，因为任选一段往后扫，得到有用信息（前后缀 \min）的同时可以判断是否找到 0。

因此可以去掉二分变成 n 次询问，注意 0 在两端的细节问题。

挂一份赛后默写的代码，过 qoj 数据了：

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include "perm.h"

using namespace std;
using namespace __gnu_pbds;

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

int premin[30005], sufmin[30005];

vector<int> perm(int n){
    vector<int> res(n, -1);
    memset(premin, 0xff, sizeof(premin)), memset(sufmin, 0xff, sizeof(sufmin));
    tree<int, null_type, less<int>, rb_tree_tag> t;
    for(int i = 0; i < n; i++) t.insert(i);
    int lst = n, zero; // query(0, n - 1) == n
    for(int i = n - 2; i >= 0 && lst; i--){
        int now = query(0, i);
        if(now != lst) res[i + 1] = sufmin[i + 1] = now, t.erase(now);
        lst = now;
        if(!lst) zero = i + 1;
    }
    lst = n;
    for(int i = 1; i <= (~zero ? zero + 1 : n - 1) && lst; i++){
        int now = 0;
        if(i <= zero) now = query(i, n - 1);
        if(now != lst) res[i - 1] = premin[i - 1] = now, t.erase(now);
        lst = now;
    }
    int cur = n;
    for(int i = 0; i < n; i++){
        if(~premin[i]) cur = premin[i];
        premin[i] = cur;
    }
    cur = n;
    for(int i = n - 1; i >= 0; i--){
        if(~sufmin[i]) cur = sufmin[i];
        sufmin[i] = cur;
    }
    for(int i = 0; i < n; i++){
        if(!~res[i]){
            auto it = t.lower_bound(max(premin[i], sufmin[i]));
            res[i] = *it, t.erase(it);
        }
    }
    return res;
}