2023-01-14
题目传送门
翻译
难度&重要性(1~10):
题目来源
AtCoder
题目算法
区间覆盖，线段树，双堆
解题思路
可以将问题转化为区间覆盖问题和单点查询问题。
一共会有 \(3\) 种操作：
\(1.\) 插入一个区间。
\(2.\) 删除一个区间。
\(3.\) 查询一个区间。
想到这我是想用双堆去做。
一个小根堆存已经插入的区间，一个小根堆存已经被删除的区间。
当两个堆的堆顶相同时，就代表这个区间已经删除了可以去掉了。
此时的开始时间就会转化为 \(s-x\) 和 \(t-x\)，那么从 \(s-x\) 到 \(t-x\) 这段时间走到这的就必然停下。
建议将施工结束的时间从小到大排序，如果结束时间相同就比较施工开始时间。
完成状态
已完成
标签：双堆,题目,堆存,ABC128E,小根,区间,Roadwork From： https://www.cnblogs.com/OIerBoy/p/17357091.html