题解 CF559E

· · 题解

提供一种不同的思路。

首先发现值域很大，但有用的点数不多。那么可以离散化，只将所有的 a_i、a_i-b_i、a_i+b_i 存下。

下面使用的所有位置下标均为离散化后的下标。

考虑最终点亮的情况，将所有相交的线段并起来称为同一个连通块，那么最终局面就是若干个不交连通块的并。我们在 dp 时枚举每个连通块，算贡献即可。

具体地，我们记 g_{l,r} 表示只使用位置在 [l,r] 之间的灯，能否将 [l,r] 这一段完全覆盖，再记 f_i 表示考虑到位置 i 的最长长度。

当我们求出所有的 g_{l,r} 后，就容易得到 f_i=\max \{f_{j-1}+s_i-s_j\} ，其中 j \in [1,i-1] 且 g_{j,i} 为真，s_x 表示离散化数组中第 x 个位置的值。

接下来考虑如何求所有的 g_{l,r} 。

有一道很类似的题目：CF1476F 。

将所有灯按位置排序，对于每个 l ，我们将所有位置 \geq l 的灯拉出来 dp 。

一盏灯能向右照，当且仅当 $dp_{i-1} \geq pos_i$ 。 一盏灯向左照，则 $dp_i=\max r_j$ ，其中需要满足 $dp_j \geq l_j$ 。$l_j$ 和 $r_j$ 分别表示第 $j$ 盏灯向左或向右能照到的位置。 这个 $dp$ 可能还有一些细节，但对着样例不难调试。 对于每个 $l$ ，求出 $dp$ 数组后就容易得到 $g_l$ 数组了。 这样这道题目就做完了，时间复杂度 $O(n^3)$ 。