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

tiger2005 · 2026-03-08 15:28:10 · 题解

需要注意到，本题的构造目标是不同于初始排列 p 的另一个排列 q，需要满足对于任意区间，初始排列和构造排列的 \operatorname{mex} 相同。这是因为在某些情况下，仅通过区间 \operatorname{mex} 是无法确定排列本身的，例如 0 3 2 1 和 0 2 3 1。

本题关键在于：对于一个排列，其某个位置序列的 \operatorname{mex} 等于位置序列补集的 \min，这是因为 \operatorname{mex} 本质上就是位置序列上缺失的数字中最小的一个，而缺失的所有数字都在位置序列的补集中给出了。对于区间 \operatorname{mex} 而言，它的补集就是一段前缀和一段后缀，因此设 A_i 表示下标在 [0, i] 范围内元素的最小值，而 B_i 表示下标在 [i, n - 1] 范围内元素的最小值，则有

因此，只要我们构造的排列对应的前缀 \min 和后缀 \min 和初始排列相同，那么构造结果就是正确的。

• 首先从长到短询问后缀 \operatorname{mex}，从而从前到后得到前缀 \min。只要在某一个时刻得到的前缀 \min 为 0，则后续的所有前缀 \min 都为 0，可以立即停止询问，另外也得到了元素 0 所在的位置；
• 考虑到元素 0 的位置已知，我们可以确定一部分的后缀 \min，而这里只需要继续从长到短询问前缀 \operatorname{mex}，从而从后往前得到后缀 \min。
• 最后，根据前后缀 \min 的分界点可以得到每个前后缀最小值所在的位置，而最后只需要从 0 开始向外填写剩余的没有出现的数字即可。需要注意的是，向外扩展的顺序和外侧已经确定的值相关，例如对于 1 ? ? ? 0 ? ? ? 5 而言就需要先扩展左边再扩展右边。

需要额外注意 0 在边界时可能出现的询问问题。剩余的细节请参考代码。

::::info[代码]

#include "perm.h"
#include <algorithm>
using namespace std;

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

vector<int> perm(int n) {
  vector<bool> used(n, false);
  vector<int> ans(n, -1);
  vector<pair<int, int>> pos;

  int last = -1, p0 = -1;
  for (int i = 0; i < n - 1; i ++) {
    int res = query(i + 1, n - 1);
    if (last != res) {
      last = res;
      ans[i] = res;
      used[res] = true;
      if (res == 0) {
        p0 = i;
        break;
      }
      pos.push_back({res, i});
    }
  }

  if (last != 0) {
    used[0] = true;
    ans[n - 1] = 0;
    p0 = n - 1;
  } else {
    last = -1;
    for (int i = n - 1; i > p0; i --) {
      int res = query(0, i - 1);
      if (last != res) {
        last = res;
        ans[i] = res;
        used[res] = true;
        pos.push_back({res, i});
      }
    }
  }

  int ptr = 0, l = p0 - 1, r = p0 + 1;

  auto gnext = [&] () {
    while (used[ptr]) ++ ptr;
    used[ptr] = true;
    return ptr;
  };

  pos.push_back({n, -1});
  pos.push_back({n + 1, n});
  sort(pos.begin(), pos.end());
  for (auto ele : pos) {
    int p = ele.second;
    if (p <= l) {
      while (l > p) ans[l --] = gnext();
      -- l;
    } else {
      while (r < p) ans[r ++] = gnext();
      ++ r;
    }
  }

  return ans;
}

::::