P14154 [ICPC 2022 Nanjing R] 索道 题解

先考虑不带修怎么做。容易想到设 $f_i$ 表示当前考虑了前 $i$ 个位置，且第 $i$ 个位置放了支撑塔，最少所花费的代价是多少。容易想到 $O(n^2)$ 转移：枚举上一个设支撑塔的位置 $j$，转移为 $f_i=(\min\limits_{j}f_j)+a_i$，其中 $j$ 需要满足 $j+1\sim i-1$ 中不能存在一个必须设立支撑塔的位置，且 $i-j\le k$。容易想到用单调队列优化，时间复杂度为 $O(n)$。

然后考虑带修。注意到 $kq\le 9\times 10^6$，因此想到每次询问可能时间复杂度带一个 $O(k)$。容易发现任意一个长度为 $k$ 的连续子段中都至少存在一个支撑塔，因此考虑对于每次修改，先提前再处理出 $g_i$ 表示当前考虑了 $i\sim n$ 的位置，且第 $i$ 个位置放了支撑塔，最少所花费的代价是多少。暴力的处理出 $[p-k,p+k]$ 区间内的 dp 值，然后直接拼接到 $f$ 和 $g$ 两个 dp 数组上，时间复杂度为 $O(n+kq)$ 可以通过。