AtCoder
区间覆盖,线段树,双堆
可以将问题转化为区间覆盖问题和单点查询问题。
一共会有 \(3\) 种操作:
\(1.\) 插入一个区间。
\(2.\) 删除一个区间。
\(3.\) 查询一个区间。
想到这我是想用双堆去做。
一个小根堆存已经插入的区间,一个小根堆存已经被删除的区间。
当两个堆的堆顶相同时,就代表这个区间已经删除了可以去掉了。
此时的开始时间就会转化为 \(s-x\) 和 \(t-x\),那么从 \(s-x\) 到 \(t-x\) 这段时间走到这的就必然停下。
建议将施工结束的时间从小到大排序,如果结束时间相同就比较施工开始时间。
已完成
手机扫一扫
移动阅读更方便
你可能感兴趣的文章