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

oi_tuanzhang · 2026-08-10 22:32:09 · 题解

P17234 [Algo Beat Contest 017 C] 交互题

先将原序列的 mex 算出来，发现若为 0 则答案也为 0。

枚举同时为 mex 与 cmin 的 x。

考虑什么样的区间可使 x 同时为 mex 和 cmin，发现对于区间 [l,r]，其需满足 [l,r] 内无 x，保证 [0,x-1] 只出现在其中，也就是 <x 的都在，>x 的数随意。

发现前者是好维护的，考虑倒序枚举跑双指针，左右端点分别维护第一个、最后一个 <x 的数的位置，显然对于减小的 x，其是不断向内收缩的，那么这个指针对应的区间 [l',r'] 就满足所有 <x 的数都在。

但保证 [0,x-1] 都在就比较难维护，考虑记 lst_i 为 i 在序列中第一次出现的位置，初始化 lst_i = -inf，维护一个 mn_i = \min_{j=0}^{i}lst_j，表示所有 \le i 的数出现的最左端。

则发现在判断区间 [l',r'] 是否包含所有 [0,x-1] 时，只需判断是否有 mn_{x-1} \ge l 即可，因为若没全出现会有 mn_{x-1} = -inf（不知道有没有更好的方法，感觉用主席树搞这个有点大炮打蚊子的感觉），对于不合法的直接跳过即可，下面只考虑可找出合法区间的 x。

先对 a_i 维护其每一个出现位置，令使 x 目前合法的区间为 [ls,rs]（只未判断 x 是否出现的区间），还需进行判断 x 是否出现，对于合法情况考虑计算贡献：

1、x 只出现一次，判断其在 ls 左，rs 右，还是中间即可，最后这种是不合法的，前两种计算贡献是平凡的。

2、x 出现多次，判断其全在 ls 左，全在 rs 右，或是存在交叉。前两种情况是简单的，考虑最后的情况。使用 lower_bound 和 upper_bound 找出 x 在 ls 左和 rs 右第一次出现的位置 p,q，发现若找不到 p,q 或者 p,q 两位置在 x 的出现序列中不相邻，这些情况都代表着 [ls,rs] 中至少出现了一次 x，属于不合法情况。那么对于最终的合法的 p,q，其对答案贡献为 (ls-p) \times (q-rs)。