P7476 苦涩 题解

乎语百科 222 0

Link

一道很好的复杂度均摊题目。

只需要考虑删除操作时的时间复杂度。保证复杂度的重点之一是精确定位到所有包含最大值的区间,即不去碰多余的区间。每次删除操作会删除若干个整个区间,以及至多两个区间被删一半。

由于一共最多插入了 \(O(m\log n)\) 个区间,所以前一半的复杂度是对的。

对于后一半,直接暴力将区间切半向下递归,于是两个儿子要么一个留下一个递归,要么一个删掉一个递归,递归层数至多 \(O(\log n)\),于是这一步复杂度也至多 \(O(m\log n)\)。

总共复杂度就俩 \(\log\)(注意其中一个是 set 的,线段树只有一个 \(\log\)!)

标签:

留言评论

  • 这篇文章还没有收到评论,赶紧来抢沙发吧~