CF1924B 题解

EuphoricStar · 2024-01-28 11:05:09 · 题解

不知道为什么好像大家在这题上花了挺久的。

发现对于一对相邻的港口 (x_i, x_{i + 1})，x \in (x_i, x_{i + 1}) 的花费是 y_i (x_{i + 1} - x)。拆开得 y_i x_{i + 1} - y_i x。

考虑用 set 维护所有港口，这样可以知道一个港口左边和右边的港口的坐标和价值。那么前一项 y_i x_{i + 1} 可以线段树区间覆盖，后一项 -y_i x 也可以线段树区间覆盖处理，相当于让一个代表 [l, r] 区间的线段树结点的和变成 - y_i \frac{(l + r)(r - l + 1)}{2}。这个标记是可以下传的。

总时间复杂度为 O((m + q) \log n)。

code