题解：AT_abc128_e [ABC128E] Roadwork

· · 题解

模拟题。

考虑从时间 D 出发往前走会碰到哪些被覆盖的点，发现当且仅当 S_i-X_i \le D 且 T_i-X_i>D。把所有的区间按 S_i-X_i 排序，则加点的次序是一段前缀。

将查询离线后按时间排序扫一遍，只需加点，求最小值和删点，可以优先队列实现。代码。