静态复杂区间 mex 问题考虑极小 mex 区间。
极小 mex 区间个数是 \(\mathcal{O}(n)\)，证明考虑对于对于 \(a_l>a_r\) 的区间，每个 \(l\) 只有一个对应的 \(r\)。这个是好证的，对于 \(a_r>a_l\) 同理。
于是一个区间的 mex 就是它包含的所有极小 mex 区间代表的 mex 的最大值。现在问题相当于要使若干区间找出的不交区间数最大，这个首先把包含关系去掉，然后就是每次跳到理当前区间最近的合法区间，这个东西可以直接倍增维护，即设 \(f(i,j)\) 表示从高 \(i\) 开始跳 \(2^j\) 个区间最后会停在哪。
于是我们的算法是，从左到右扫描线，将极小区间按 mex 分类，对于每一种 mex 分别考虑。我们的倍增是可以动态维护的，我们可以容易维护出当前加入的区间的倍增数组，询问时我们还需要维护询问区间的 mex，这个直接线段树即可。
极小 mex 区间我们则有两种维护方式，一种是我们发现每个极小区间一定可以被另一个极小区间拓展得到，证明考虑不妨令 \(a_l>a_r\)，此时我们删掉 \(a_l\)，则区间 mex 变为 \(a_l\)，而该区间的极小 mex 为 \(a_l\) 的子区间右端点一定为 \(r\)，否则完全可以更优。于是我们可以利用原来的极小 mex 区间拓展，不过拓展出来的区间可能不是极短 mex 区间，判一下就好了。
还有一种就是考虑其证明方式。我们直接对于每个 \(l\)，找它的 \(r\)。我们从后往前扫描线，对每个值维护 \(p_i\) 表示其最靠前的出现位置，则 \(r=\max_{i=0}^{a_l-1}p_i\)，不难证明这是对的，对于每个 \(r\) 也如此。