[ABC128E] Roadwork
阅读原文时间:2023年08月22日阅读:5

2023-01-14

题目传送门

翻译

难度&重要性(1~10):4

题目来源

AtCoder

区间覆盖,线段树,双堆

可以将问题转化为区间覆盖问题和单点查询问题。

一共会有 \(3\) 种操作:

\(1.\) 插入一个区间。

\(2.\) 删除一个区间。

\(3.\) 查询一个区间。

想到这我是想用双堆去做。

一个小根堆存已经插入的区间,一个小根堆存已经被删除的区间。

当两个堆的堆顶相同时,就代表这个区间已经删除了可以去掉了。

此时的开始时间就会转化为 \(s-x\) 和 \(t-x\),那么从 \(s-x\) 到 \(t-x\) 这段时间走到这的就必然停下。

建议将施工结束的时间从小到大排序,如果结束时间相同就比较施工开始时间。

已完成

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章