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

· · 题解

首先 Mex 有两个显然的性质，首先记询问 [l,r] 区间的答案为 ans(l,r)。

于是我们可以通过询问出每一个前缀 ans(1,i)，和每一个后缀 ans(i,n)，通过比较相邻的 i 可以确定一些 p_i。

那这样询问不是 2n 吗？考虑优化，发现当 ans(1,i) \ne 0 时 ans(i+1,n) =0，且对于所有 i+1 \le j \le n 都有 ans(j,n) = 0。对称的情况同理。所以说对于 i 要么询问 ans(1,i) 要么询问 ans(i,n)，然后再特判一下 ans(1,1) 和 ans(n,n)，然后再处理剩下的 2 \le i\le n-1，严格的控制了次数在 n 以内。

经过确定了必要的数之后，考虑如何填入剩下的数。

又由于性质一，从前往后时，询问结果是不递减的。而从后往前也是不递减的。所以说对于 1 \le i \le l 都有 \{1,2,\cdots,ans(1,l)-1\} \in \{p_1,p_2,\cdots,p_l\}。

由于比较难维护前缀满足且后缀满足。所以在维护前缀合法的情况下贪心的选，思想是从前往后填，能填大的就填大的。目的是将小的数尽量放后面。

维护着目前还没有填的数和位置。根据 \{1,2,\cdots,ans(1,l)-1\} \in \{p_1,p_2,\cdots,p_l\} 的条件，如果目前 p 中的空位能够刚好填够 \{1,2,\cdots,ans(1,l)-1\} 这些数，那么就在剩下的位置中开始填，从后往前，从小到大填。实现的话应该不难。

然后对于剩下的还没有填入序列中的数，从前往后，递减的填入，也是为了满足将小的放在后面处理的原则。