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 个数需要填，则答案为：

\sum_{i=1}^n i\sum_{j=w_i}^C\binom{j}{w_i}w_i!(C-w_i)!\sum_{l,r}[\operatorname{mex}(l,r)=i\land c(l,r)=j]

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

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

\sum_{i=1}^n\sum_{j=w_i}^C\binom{j}{w_i}w_i!(C-w_i)!\sum_{l,r}[\operatorname{mex}(l,r)\ge i\land c(l,r)=j]

这样看起来就好做很多，因为 \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)。