题解：P14343 [JOISC 2019] 两个天线 / Two Antennas

happybob · 2025-10-30 21:38:27 · 题解

对 r 扫描线，对于每个 l 维护 [l,r] 内和 l 通信的最大权值。查询即在 r 时查询 [l,r] 区间最大值。

对于 r 来说，合法的 l 是一段区间，对于 l 来说，合法的 r 是一段区间。所以每个点相当于有一个区间 [x_i,y_i]，新加入 r 时，考虑区间 [a,b]，要更新所有 i \in [a,b],r\in [x_i,y_i] 的 i。随着 r 的增大，每个 i 会经历激活然后停止激活，然后这就容易使用线段树维护了。