题解：P17234 [Algo Beat Contest 017 C] 交互题

· · 题解

考虑枚举 \operatorname{mex} 的值 k，判断所有满足 \operatorname{mex}(l, r) = k 且符合条件的 [l, r] 有多少个。

对于 k = 0 的情况，将 0 作为分割线，会划分出若干个区间，设这些区间的长度依次是 b_{1} \sim b_{m}，显然的，

ans = \sum_{i = 1}^{m} \frac{b_{i} \cdot b_{i} + 1}{2}

注意也要将位置 0 与 n + 1 放进来。

对于 k+1 的情况，将题目描述转换一下，不难得出一个区间 [l, r] 合法当且仅当整个序列 \{ a\} 包含 k 且 [l, r] 内不包含 k 但包含 0 \sim k - 1 中的所有数，然后你就用类似于前缀和的方法记一下就好了。