AT_abc470_g 题解

Guizy · 2026-08-10 19:43:41 · 题解

求子区间 mex 之和。要求做到 O(n\log n)。

考虑记 f_{i,j} 表示 [i,j] 的 mex。考虑暴力 O(n) 求出 i=1 时的情况之后怎么拓展到 i=2。

我们发现，唯一的区别就是没有了 a_1。它对于 f 的影响是，对于 f_{1,j}>a_1 且 [2,j] 内没有 a_1，f_{1,j} 会变为 a_1-1。

并且这个 f 肯定是递增的，所以我们只需要找到第一个 f_j>a_1 的位置（二分），然后一直到 nxt_{a_1}，将这个区间的数改为 a_1-1。

对于 i 更大的情况同理。每次二分和线段树都是 \log 的。总时间复杂度 O(n\log n)。