P15652 [省选联考 2026] 排列游戏 - 洛谷 (luogu.com.cn)0.分析交互题特有的谜语人。玩海龟汤评测会给定一个序列作为汤底不告诉你。其中你可以每次询问一组评测会告诉你汤底序列区间的 mex 值。mex 即为一个序列中未出现的最小值。求满足在所有询问区间下 mex 意义和汤底序列等价的序列。1.初步在测试点计分规则表中我们发现题目强制要求询问次数。考虑线性求解这个问题假设我们已经知道汤底序列如何线性求出询问的答案设即序列区间的 mex。设即序列区间的 mex。那么答案很明显就是。也就是我们只要知道汤底序列的数组就能够造出满足题目要求的序列因为这个序列的数组和汤底序列的数组等价那么两者就在所有询问区间下 mex 意义等价。2.细节构造数组很简单正常询问评测就 ok。但要从优化到可以特判 0 的位置即发现 0 接下来的就都是 0直接 break。在有了数组后我们该如何构造合法序列以下情况可以唯一确定一个位置上的值1当代表着使得的 mex 变大了。说明当前的也就是取到了的 mex。2当代表着使得的 mex 变大了。说明当前的也就是取到了的 mex。把这些确定的位置先填好并从可用数集合中删掉。这里的空值定为 n避免紊乱。而对于没有唯一确定的值我们有两个约束。1的 mex 是最小可以取到的数。2的 mex 是最小可以取到的数。我们取两者中较大的那个毕竟较小的那个代表着在另一边取过。所以答案满足在之前未选到的集合里面选。3.实现请注意细节。洛谷提交还要改一下头文件。#includebits/stdc.h #includeperm.h using namespace std; void init(int c, int t) {} int query(int l, int r); std::vectorint perm(int n) { vectorint A(n 1, 0), B(n 1, 0); B[0] n; // 后缀 [0, n - 1] 最小的没出现过的值为 n - 1 A[n - 1] n; // 前缀 [0, n - 1] 最小的没出现过的值为 n - 1 int pzero n - 1; for (int l 1; l n - 1; l ) { // 从小到大处理后缀 int v query(l, n - 1); if (v 0) { // 一旦出现 0后面的后缀都是 0 pzero l - 1; // 第一次出现 0代表着第一次将 0 排在外面 // 所以上一个位置就是 0 break; } B[l] v; } for (int r n - 2; r pzero; r --) { A[r] query(0, r); // 前缀从大到小到 0 后的前缀 mex 都是 0 } vectorint p(n, -1); // 这里要是打成 n 1 绝对判你错 setint unused; unused.clear(); for (int i 0; i n; i ) { unused.insert(i); } for (int i 0; i n; i ) { int x -1; if (i 0 A[i - 1] A[i]) { x A[i - 1]; } if (i n - 1 B[i] B[i 1]) { x B[i 1]; } if (x ! -1) { unused.erase(x); p[i] x; } } for (int i 0; i n; i ) if (p[i] -1) { int lef 0, rig 0; if (i ! 0) lef A[i - 1]; if (i ! n - 1) rig B[i 1]; int x max(lef, rig); auto it unused.lower_bound(x); p[i] *it; unused.erase(it); } return p; }