[CEOI 2025] Equal Mex 题解

[CEOI 2025] Equal Mex
虽然说是套路题，但是记录一下一些结论防止自己以后忘了。
首先不难发现你划分出的每个子段的 \(\operatorname{mex}\) 一定就是整个区间的 \(\operatorname{mex}\)，而且 \(k\) 合法 \(k-1\) 也一定合法，所以答案就是能划分的最大段数，不难写出 \(O(nq)\) 的贪心。
然后考虑正解，我们需要若干结论：
结论一：我们称一个区间 \([l,r]\) 是极小 \(\operatorname{mex}\) 区间当且仅当不存在他的一个真子区间 \([l',r']\) 使得 \(\operatorname{mex}[l,r]=\operatorname{mex}[l',r']\)。则极小 \(\operatorname{mex}\) 区间的数量是 \(\le 2n\) 的（为了避免 corner case 我们不讨论 \(l=r\) 的区间，这些区间的处理是简单的）。

证明：不妨先考虑所有 \(a_l>a_r\) 的区间，对于这样的一个极小 \(\operatorname{mex}\) 区间 \([l,r]\)，由于他是极小的，所以 \(\operatorname{mex}[l,r]>a_l>a_r\)，否则可以缩减某一个端点，那么：
- 对于一个 \(r'r,a_{r'}a_l>a_{r'}\) 所以 \(a_{r'}\) 在 \([l,r]\) 出现过了，减小 \(r'\) 不影响区间 \(\operatorname{mex}\)。
因此对于每个 \(l\) 只存在一个 \(r\) 满足 \(a_r

然后是如何 \(O(n\log n)\) 求出所有极小 \(\operatorname{mex}\) 区间：对区间左端点 \(l\) 从小到大扫描线，用 ODT 维护每个 \(r\) 对应的区间 \([l,r]\) 的 \(\operatorname{mex}\)（显然 \(\operatorname{mex}\) 具有单调性，可以用 ODT 维护）；每次 \(l\to l+1\) 时，不妨设 \(x\) 是下一个满足 \(a_x=a_l\) 的位置，则我们需要把 \([l,x)\) 末尾的若干 \(\operatorname{mex} > a_l\) 的区间推平成 \(a_l\)，如果在这个过程中推平了一个区间 \([l',r']\)，那么 \([l,l']\) 就是一个极小 \(\operatorname{mex}\) 区间；我们可以顺便求出每个询问区间的 \(\operatorname{mex}\)。
注意： 如果 \([l,x)\) 末尾不存在需要推平的区间，那么你可能需要把 ODT 一开始 split 出的两个区间 merge 回去，因为我们要保证 ODT 中维护的颜色段是极长的，否则求出的极小 \(\operatorname{mex}\) 区间会有问题。
结论二：对于一个区间 \([l,r]\) 总可以找到一个极小 \(\operatorname{mex}\) 区间 \([l',r']\subset [l,r]\) 满足 \(\operatorname{mex}[l',r']=\operatorname{mex}[l,r]\)。
我们把所有 \(\operatorname{mex}\) 相同的询问和极小 \(\operatorname{mex}\) 区间放到一起做，于是问题变成找到询问区间内尽可能多的互不相交的极小 \(\operatorname{mex}\) 区间。
显然这是个经典贪心，由于所有极小 \(\operatorname{mex}\) 区间互不包含，所以把这些区间按照左端点排序右端点也升序，先用双指针预处理每个区间跳到的下一个区间，回答询问可以直接倍增。
\(O((n+q)\log n)\)，目前最优解第二。
[code]#include #define Debug puts("-------------------------") #define eb emplace_back #define pb push_back #define iter set
::iterator  #define PII pair #define fi first #define se second  using namespace std; const int N=6e5+5,V=4e5+5; int n,m,a[N],pos[V],nxt[N],ans[N];  bool flag[V]; struct Que{ int l,r; } que[N]; vector vec[N]; struct P{ mutable int l,r,c; }; bool operator < (const P&x,const P&y){ return x.l