P3600 随机数生成器

· · 题解

min-max 容斥，不错。

首先考察哪些区间是没用的。如果存在包含关系，则大一点的那个区间没有用，因为短一点那个区间的 \min 一定不小于那个大区间的 \min，因此最终算 \max 的时候只有小区间就好了。

把包含关系中大区间全撇掉，剩下的区间 [l,r] 两个端点分别递增。设剩下区间 m' 个，并重新标号为 1,2,\dots,m'。

然后你考察 minmax 容斥，可以把问题转化成某一个子集中包含的区间的并位置上的最小值的期望：

E(\max)&=\sum_{T\subset \{1,2,\dots,m'\}}(-1)^{|T|+1}E(\min_{i\in T}\min_{j\in [l_i,r_i]}a_j)\\ &=\sum_{T\subset \{1,2,\dots,m'\}}(-1)^{|T|+1}E(\min_{j\in \cup_{i\in T}[l_i,r_i]}a_j)\\ &=\sum_{T\subset \{1,2,\dots,m'\}}(-1)^{|T|+1}E_{|\cup_{i\in T}[l_i,r_i]|} \end{aligned}

容易发现这个东西只和区间并覆盖到的长度 len 有关，且这些期望容易 O(n^2) 得到，记作 E_{len}。

现在问题转化为，求有多少种选取一些区间的方式，使得选了偶数/奇数个区间，并起来长度是 len 的方案数 f_{0/1,len}，最终答案就是 \sum_{len=0}^n(-f_{0,len}+f_{1,len})E_{len}。

这咋做呢？你设 dp_{r,0/1,len} 表示当前已经选了的区间里最右端端点是 r 时，已经选了偶数/奇数个区间，并起来长度是 len 的方案数。

考虑转移，我们按照区间从小到大转移，recall that 撇完区间以后区间已经有单调性了。

考虑当前区间 [l,r]。如果这个区间不选，那么什么都不会发生；如果选了，那么会对 dp_{r,*,*} 产生影响。具体的：

dp_{r,0/1,len}=\sum_{R=l}^rdp_{R,1/0,len-(r-R)}+\sum_{R=0}^{l-1}dp_{R,1/0,len-(r-l+1)}

两部分都能前缀和优化，做完了。最终有 f_{0/1,len}=\sum_{r=0}^ndp_{r,0/1,len}。