题解：P13693 [CEOI 2025] Equal Mex

· · 题解

根号！

首先注意到题意是将区间划分成很多 mex 等于整个区间 mex 的最大划分个数，容易想到就是贪心的选，然后当 [1,mex-1] 都出现一次的时候分一段，看能够分几段。

先求出区间 mex，这东西可以离线后线段树上二分做，然后注意到每一次划分时必须要 [1,mex-1] 都出现一次，发现 mex 越大能分的段就越小，考虑根号分治。

$mex < \sqrt V$，则我们对于每一个值处理 $mex$ 等于他的询问，可以处理出序列上每一个位置能跳的位置，发现转化成了[弹飞绵羊](https://www.luogu.com.cn/problem/P3203) ，序列分块即可。 时间复杂度 $O(n \sqrt V +q \sqrt V +q \sqrt n)$，空间线性。