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}\) 为集合内未出现过的最小正整数。
\(n\le 10^6\)，\(1\le a_i\le n\)，不强制在线。
题解
知识点：主席树，扫描线。
启发：
- 序列的极小 \(\operatorname{mex}\) 区间数量级别为 \(O(n)\)。
与题目不同，以下对于 \(\operatorname{mex}\) 的定义为集合内未出现过的最小非负整数，输入时将 \(a_i\) 整体减 \(1\)，最后输出答案加上 \(1\) 即可。
追忆
如果你做过 P9970 [THUPC 2024 初赛] 套娃，那么这题就是纯纯的一眼题。
一个区间 \([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}\) 区间和处理询问两个部分。
代码就不放了，赛时卡着时间限制和空间限制（真的非常极限）过的。