题解：AT_abc470_g [ABC470G] ΣШX

RiverBird208 · 2026-08-11 08:35:49 · 题解

不是，为什么这都有两发罚时啊……

先进行一步转化：\sum\limits_{l=1}^n\sum\limits_{r=l}^n\operatorname{mex}(a_l,a_{l+1},\cdots,a_r)=\sum\limits_{x=1}^n\sum\limits_{l=1}^n\sum\limits_{r=l}^n[\operatorname{mex}(a_l,a_{l+1},\cdots,a_r)\ge x]。

从左到右扫，考虑 \operatorname{mex}=x 的贡献。令 p_i 为 i 最右边出现的位置。特殊的，若 i 没有出现，则 p_i=0。

那么，x 的贡献就是 \min\limits_{i=0}^x p_i。考虑到现在的形式是前缀最小值的和，于是单边递归线段树维护即可。

时间复杂度：O(n\log^2n)。

代码：https://atcoder.jp/contests/abc470/submissions/78226031。