CF1728G Illumination

Alex_Wei · 2022-12-19 12:46:34 · 题解

将 p 从小到大排序。

多次询问序列只改变一个位置的相关信息，考虑维护前后缀再合并。

对于新加入的灯笼，只有距离它最远的未被点亮的景点的距离会影响到方案数。

设 pre_{i, j} 表示考虑 [1, i] 的所有灯笼，其中第一个未被覆盖的景点为 p_j 的方案数，suf_{i, j} 表示考虑 [i, d] 的所有灯笼，其中最后一个未被覆盖的景点为 p_j 的方案数。

求出 pre 和 suf，回答询问 f 时枚举 j 和 k，表示 pre_{f - 1, j} 和 suf_{f + 1, k}。若 j > k，则 f 的方案数为 d + 1，否则 f 的方案数为 d - \max(f - p_j, p_j - f) + 1。