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

Wyh_dailyAC · 2026-03-08 16:24:48 · 题解

题意

略。

Sol

排列的区间 \operatorname{mex} 即其补集的 \min，于是这题就可以去求前缀 \min 了。

求前缀 \min 时如果发生了跳变则该位数值可以确定，否则先空着；我们正向去扫前缀 \min 应该扫到前缀 \min 为 0 就停止（因为再扫没有任何意义），然后去扫后缀也是碰到 0 就停止，这样询问次数就是 \le n 次的。

没有记载到跳变的位置就在维持前缀 / 后缀 \min 不变的前提下去按值划定可填空位范围，然后从小到大遍历数值，动态更新范围，之后 \log{n} 正常填即可。

总时间复杂度 O(n\log{n})。

注：求前 / 后缀 \operatorname{mex} 其实是求后 / 前缀 \min。

Code

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

int C, T;

void init(int c, int t) { C = c, T = t; }

vector<int> perm(int n) {
    vector<int> ans(n, -1);
    if (n == 1) { ans[0] = 0; return ans; }
    int pP = n, pos0 = -1;
    for (int i = 1; i < n; i++) {
        int pm = query(i, n - 1);
        if (pm < pP) {
            ans[i - 1] = pm;
            if (pm == 0) { pos0 = i - 1; break; }
        }
        pP = pm;
    }
    if (pos0 == -1) { ans[n - 1] = 0; pos0 = n - 1; }
    int sP = n;
    for (int j = n - 1; j > pos0; j--) {
        int sm = query(0, j - 1);
        if (sm < sP) {
            if (ans[j] == -1) ans[j] = sm;
        }
        sP = sm;
    }
    vector<int> vpos(n, -1);
    for (int i = 0; i < n; i++) if (ans[i] != -1) vpos[ans[i]] = i;
    set<int> emp;
    for (int i = 0; i < n; i++) if (ans[i] == -1) emp.insert(i);
    int L = vpos[0], R = vpos[0];
    for (int v = 0; v < n; v++) {
        if (vpos[v] != -1) {
            L = min(L, vpos[v]);
            R = max(R, vpos[v]);
        } else {
            auto it = emp.lower_bound(L);
            int pos = *it;
            ans[pos] = v;
            vpos[v] = pos;
            emp.erase(it);
        }
    }
    return ans;
}