CF2084E Blossom

以下记 $\operatorname{mex}(l,r)$ 为区间 $[l,r]$ 的 $\operatorname{mex}$。

先考虑没有 $-1$ 怎么做。容易想到枚举 $\operatorname{mex}$，答案即 $\sum_{i=1}^ni\sum_{l,r}[\operatorname{mex}(l,r)=i]$。第二个求和号可以根据 $0\sim i-1$ 的数的最小下标 $mn$ 和最大下标 $mx$、$i$ 的下标 $p$ 得出，只需分讨 $p$ 与区间 $[mn,mx]$ 的相对位置即可，总复杂度 $O(n)$。

接下来考虑拓展到有 $-1$ 的情况。贡献显然与区间内 $-1$ 的个数 $c(l,r)$ 有关，而且数据范围允许我们枚举两个东西，那么自然可以再枚举 $c(l,r)$。记总共有 $C$ 个 $-1$，$0\sim i-1$ 中总共有 $w_i$ 个数需要填，则答案为：

然后我们发现接下来就不太会做了，其原因在于 $\operatorname{mex}(l,r)=i$ 这个限制太强，根据上文没有 $-1$ 的做法，甚至需要分讨，不好刻画。

观察式子结构，发现可以将其转化为

这样看起来就好做很多，因为 $\operatorname{mex}(l,r)\ge i$ 这个条件只要求 $[l,r]$ 包含 $0\sim i-1$ 出现的区间 $[mn_i,mx_i]$。设最后一个求和号的结果为 $f_{i,j}$，那么我们只需求出 $f$ 即可 $O(n^2)$ 计算答案。

至于计算 $f$，我们考虑对每个区间算出它的贡献。具体地，由于 $[mn_i,mx_i]$ 随着 $i$ 的增加而逐渐扩大，那么 $[l,r]$ 可贡献到的 $f_{*,c}$ 第一维就是一段前缀。考虑 $l$ 固定时，随着 $r$ 的增加，$[l,r]$ 能贡献到的位置单调不减，那么我们双指针维护 $[l,r]$ 能贡献到的右端点，前缀加用差分处理即可。

总复杂度 $O(n^2)$。