题解：CF1774G Segment Covering

· · 题解

套路但是并不是很好理清楚思路。

首先把连续区间转化为离散区间，即 [l,r] \to [l,r-1]。容斥，设区间并包含于 S 的方案数为 f(S)，区间并恰好为 S 的方案数为 g(S)。

g([L,R]) = \sum_{S \subseteq [L,R]} f(S) (-1)^{R-L+1-|T|}

考虑写出 f(S) 的表达式，设 F(S) 是 m 个给定区间中被 S 完全包含的区间个数，那么只有这 F(S) 个区间可以被选中，其余区间一定不选，则：

f(S) = \sum_{i=0}^{F(S)} \binom{F(S)}{i} (-1)^i = [F(S) = 0]

好，那么现在问题转化为求所有满足 F(S)=0，即不完全包含任何一个区间的 S 的 (-1)^{R-L+1-|S|} 之和。现在 S 是钦定可选点集，取反变成钦定必须不选点集，即求所有满足任意一个给定区间中都有至少一个 S' 中的点的点集 S' 的带权和，其中 S' 的权值为 (-1)^{|S'|}。

发现如果区间 [l_1,r_1] 包含 [l_2,r_2] 那么 2 区间的限制严格强于 1 区间，所以去除所有包含关系，左/右端点单调递增。

考虑 dp，设 f_i 表示 dp 到前 i 个数，以 i 作为最大元素的所有合法 S' 的带权和，那么 f_i 就能贡献到第一个 l_j>i 的区间 j 的 r_j 之前的所有点。

我最开始的思路是维护 f_i 数组中有值的元素，一定是 +1/-1 交替出现，但是很快你发现这样修改需要记录上一次和这一次跳到的位置，无法倍增，必须更换思路，这里借鉴了 Kubic 大佬的思路。

为了方便，将“人人为我”换成“我为人人”，则 f_i 的权值可以表示为：

f_i = \sum_{j = lim_i}^{i-1} f_j

设前缀和数组 S_i 以简化转移方程，则：

\left\{\begin{aligned} &f_{L - 1} = S_{L-1} = 1 \\ &f_i = S_i - S_{i-1} = S_{i - 1} - S_{lim_i - 1}\\ &\operatorname{Ans} = S_{R} - S_{lim_{R+1} - 1}\\ \end{aligned}\right.

移项可得：

S_i = S_{lim_i-1}

所以从后往前倍增可以轻易求出 S_R 和 S_{lim_{R+1} - 1} 的值。

code。

应该是不需要那么多的观察的一个做法。