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

· · 题解

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

题意

给定一个长度为 n 的序列 a，有 q 次询问。

每次询问给定一个区间 [l,r]。

求 a 序列的该区间的所有子区间 [i,j]（l\le i\le j\le r）组成的集合的 \operatorname{mex} 的 \operatorname{mex} 的值。

定义 \operatorname{mex} 为集合内未出现过的最小正整数。

## 题解 知识点：主席树，扫描线。 启发： - 序列的极小 $\operatorname{mex}$ 区间数量级别为 $O(n)$。 与题目不同，以下对于 $\operatorname{mex}$ 的定义为集合内未出现过的**最小非负整数**，输入时将 $a_i$ 整体减 $1$，最后输出答案加上 $1$ 即可。 ### 追忆 如果你做过 [P9970 [THUPC 2024 初赛] 套娃](https://www.luogu.com.cn/problem/P9970)，那么这题就是纯纯的一眼题。 一个区间 $[l,r]$ 是序列的极小 $\operatorname{mex}$ 区间，当且仅当 $[l+1,r]$ 和 $[l,r-1]$ 的区间 $\operatorname{mex}$ 与 $[l,r]$ 的区间 $\operatorname{mex}$ 不同。 也就是说，把 $[l,r]$ 两端的数任意删除一个，它的 $\operatorname{mex}$ 都会改变。 那么有一个结论，序列的极小 $\operatorname{mex}$ 区间数量级别为 $O(n)$，在这里就不去证明了，详见那题的题解。 同理，预处理所有极小 $\operatorname{mex}$ 区间的做法在这里也不细讲，需要用到主席树来静态求区间 $\operatorname{mex}$。 ### 于预处理之后 现在来讲讲预处理出极小 $\operatorname{mex}$ 区间之后该怎么做。 对于一个询问区间 $[L,R]$，欲求其所有子区间的 $\operatorname{mex}$ 组成的集合的 $\operatorname{mex}$，显然只需要对每个数 $x$，知道其所有子区间中是否存在 $\operatorname{mex}=x$ 的子区间。 也就是说，并不需要知道有多少子区间满足 $\operatorname{mex}=x$。 那么有很多区间实际上是没有贡献的，对于一个区间 $[l,r]$，如果它包含一个真子区间 $[l',r']$，使得他们的 $\operatorname{mex}$ 相等，则 $[l,r]$ 就失去了意义。 为什么，因为包含 $[l,r]$ 的询问区间，一定包含 $[l',r']$，不包含 $[l,r]$ 的询问区间，也可能包含 $[l',r']$。 这就是求出极小 $\operatorname{mex}$ 区间的意义所在，由于区间的极小性，使得他们不存在上述情况，那么直接进行贡献的就是他们。 于是考虑离线询问，对区间的左端点进行**从大到小**的扫描线。 扫描到一个左端点 $l$ 时，将所有左端点为 $l$ 的极小 $\operatorname{mex}$ 区间加入贡献。 那么询问一个区间 $[l,r]$，就是查询所有右端点 $\le r$ 的极小 $\operatorname{mex}$ 区间，其 $\operatorname{mex}$ 组成的集合的 $\operatorname{mex}$。左端点不用管，显然扫描线已经保证了相应的偏序关系。 开一颗值域线段树，叶子节点的下标 $i$ 代表 $\operatorname{mex}$ 值，叶子节点的权值 $v$ 代表当前加入的所有极小 $\operatorname{mex}$ 区间中，满足 $\operatorname{mex}=i$ 的区间中右端点的最小值，只要询问 $[l,r]$ 的 $r\ge v$，那么一定存在 $\operatorname{mex}=i$ 的子区间，这是显而易见的。 加入一个极小 $\operatorname{mex}$ 区间 $[l,r]$，满足其 $\operatorname{mex}=x$，其实就是在线段树上对下标为 $x$ 的叶子的权值与 $r$ 取 $\min$。 现在已经维护好了当前所有 $\operatorname{mex}$ 的出现情况，考虑询问的查询。 具体地，让这颗线段树维护权值的区间最大值。对于询问 $[l,r]$，去线段树上二分，如果当前节点左子树的 $v_{max}> r$，说明肯定存在一个下标满足 $v>r$，那么就不存在右端点 $\le r$ 且 $\operatorname{mex}=v$ 的区间，也就是 $[l,r]$ 的子区间，递归进左子树，反之，递归进右子树。 而这样的下标中最小的就是询问的答案（$\operatorname{mex}$ 的定义），递归下去直到访问叶子节点，获取其下标即可。 总时间复杂度 $O((n+m)\log n)$，包括预处理极小 $\operatorname{mex}$ 区间和处理询问两个部分。 代码就不放了，赛时卡着时间限制和空间限制（真的非常极限）过的。