题解

思路

对村庄 $x$，能够覆盖它的基站位置在有序村庄下标中形成连续区间 $[L_x,R_x]$。可以分别对 $D_x-S_x$ 与 $D_x+S_x$ 二分求出两端点。

设上一座基站在 $j$，当前新建基站在 $i$。当扫描到 $i=R_x+1$ 时，村庄 $x$ 已不可能被当前或未来基站覆盖；若同时 $j<L_x$，它也未被上一座或更早的基站覆盖，此时应加入补偿 $W_x$。

做法

设上一层状态为恰好建立若干座基站、最后一座在位置 $j$ 的最小费用。固定层数并从左到右扫描下一座基站 $i$，用线段树的叶子 $j$ 保存上一层状态。

将每个村庄 $x$ 挂在事件位置 $R_x+1$。扫描到该事件时，对所有 $j<L_x$ 的叶子区间加上 $W_x$。随后查询 $j<i$ 的最小值并加上 $C_i$，即可得到当前层在 $i$ 的状态。

扫描到虚拟位置 $N+1$ 时，所有未覆盖补偿都已加入；此时线段树全局最小值是当前建站数量的最终费用。对建站数 $0$ 到 $K$ 取最小值，恰好对应“不超过 $K$ 座”。

覆盖区间的连续性保证事件前缀加不重不漏；分层只从更少一座基站转移且查询 $j<i$，因此枚举了全部合法站点集合。由此算法正确。

复杂度

时间复杂度为 $O(KN\log N)$，空间复杂度为 $O(N)$。