P9000 [CEOI2022] Measures 题解

Exp10re · 2024-07-22 19:56:02 · 题解

挑战本题最幽默做法。

解题思路

以下默认 a 升序。

在第 t 秒，第 i 人与第 j 人 (i\lt j) 之间每一个人都能拉开至少 D 的距离，当且仅当 \frac {(a_i-Di)-(a_j-Dj)} {2} \leq t。

故答案 t 的最小值为 \max\limits_{i\lt j} \frac {(a_i-Di)-(a_j-Dj)} {2}。

记 w_i=a_i-Di。

静态的话遍历一遍，w 中每一个 i 的前缀最大值减去后缀最小值的最大值即为答案。

动态插入的话我们考虑该插入操作对 w 的影响：其中一个位置会多出一个数，后面的位置都减去 D。

动态插入，区间加，考虑块状链表。

每一块维护块内答案，最大值，最小值。

查询时枚举所有块，答案中 i 在块左端，j 在块右端的情况即为该块之前所有块的前缀最大值减去包括该块之后所有块的后缀最小值。

枚举所有块，得到上述情况的最大答案，然后与所有块的答案求最大值即为最终结果。