题解：P13780 「o.OI R2」愿天堂没有分块

fzitb7912 · 2025-08-19 21:21:13 · 题解

典。

分析

按题意模拟即可。

考虑一个询问区间 [L,R] 的所有子区间 [l_i,r_i] 的 \operatorname{MEX} 的 \operatorname{MEX} 为 x。那么显然这些区间可以删掉很多不重要的区间，让剩下区间的答案仍然为 x。根据 \operatorname{MEX} 的定义可以知道剩下了 x-1 个区间，记为 [l_1,r_1],[l_2,r_2],\dots,[l_{x-1},r_{x-1}]。

观察 [l_i,r_i]。如果存在 [l_i,r_i] 的一个子区间 [l',r']，满足 \operatorname{MEX}([l_i,r_i])=\operatorname{MEX}([l',r'])，那么将 [l_i,r_i] 替换为 [l',r'] 没有影响，因为 [l',r'] 也一定是 [L,R] 的子区间。所以这 x-1 个子区间一定都是极小的 \operatorname{MEX} 区间。

有个典的东西是极小的 \operatorname{MEX} 区间只有 O(n) 个，见 P9970。那么把这 O(n) 个极小的 \operatorname{MEX} 区间找出来，就变成一个二维数点的问题了。具体地，记这些区间为 [l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]，第 i 个区间的 \operatorname{MEX} 值为 a_i。那么询问 [L,R] 的答案等价于 \operatorname{MEX}(\{a_i|L\le l_i \le r_i \le R\})。双指针维护就相当于是个区间 \operatorname{MEX} 问题了。

找极小的 \operatorname{MEX} 区间和求区间 \operatorname{MEX} 都是 O(n\log n) 的。