题解：CF2146E Yet Another MEX Problem

沉石鱼惊旋 · 2025-09-25 14:49:30 · 题解

我们维护 f_i 表示 \operatorname{mex}=i 的方案数。

考虑新增一个数会发生什么：此时由于强制 i 为右端点，所以 a_i 一定出现了。此时对于 \operatorname{mex}\in[0,a_i-1] 的会有一个 1 的贡献，同时会把 a_i 这里的贡献清零。

所以直接线段树维护区间加法，单点清零，查询全局 max 即可。

cpp 提交记录：https://codeforces.com/contest/2146/submission/339811148

py 提交记录：https://codeforces.com/contest/2146/submission/339811164

py 写递归线段树被卡常了，让 AI 写了一份。