mex技巧总结

crs_line · 2022-10-02 21:47:33 · 个人记录

考虑莫队，将询问离线，在移动区间的时候维护每个元素是否出现，扩大区间时移动答案指针，缩小范围时判断当前元素是否已空且可更新答案。复杂度 O(n\sqrt{n})。

思考上述指针移动过程中，扩大区间往往容易带来超越常数的复杂度，但删除元素并无影响，因此考虑使用回滚莫队。将询问按照左端点所在块排序，预处理初始贡献，每次只右移左指针，优化移动过程。复杂度同上 O(n\sqrt{n})。

将限制转换为偏序信息，遍历原序列，记录每种元素出现的位置B_{i}，考1虑val_{i}对答案造成的贡献，当且仅当 \exists \ i 使得 B_{i}<l_{ask}\ \land \ r_{ask}<B_{i+1}，我们维护 m 个三元组 (i,j,k) 分别对应 (B_{i}+1,B_{i+1}-1,val_{i})，额外加入原序列中不存在且权值 \in\left[0,n\right] 的元素，cdq 分治即可，复杂度 O(n\log n)。

在原始序列上建立主席树，每个点维护该元素上次在序列中出现的位置，更新维护区间最小值，对于每个询问，在右边界对应的线段树上二分，先判断左子树的 min_{lastpos} 是否 < l，若有，递归左子树，否则，递归右子树，直到遍历到叶子节点，复杂度 O(n\log n)。

预处理出 \forall \ i \in \left[1,n\right]\ mex_{1,i}，以 mex 值建立线段树，now 指针初始化为 1，代表当前左端点，每个叶节点维护以当前枚举节点为左端点，i为右端点的区间的 mex 值。考虑离线，询问按照左端点排序，当 now<\ l_{ask} 时，删去 val_{now} 并更新贡献，类似 Solution-2 ，每种元素维护其在原序列中的 nextpos，那么 \forall\ r\in\left[now+1,next_{now}-1\right]\land mex_{now+1,i}>val_{now} 的区间，其 mex 值都将被更新为 val_{now}，在线段树上执行区间修改与单点查询即可。有多种实现方法 \colon

1. 维护区间 lazy_{min} 标记并每次下放。
2. 标记永久化，遍历时统计路径上信息。
3. 区间长度增大，mex值单调不降，利用单调性在线段树上二分修改左端点，直接区间赋值。
4. 吉司机线段树 (如果您愿意)

给定n，求

\sum\limits_{i=1}^n\sum\limits_{j=i}^n mex_{i,j}

利用Solution-4，每次改为区间查询就好了。