Link
一道很好的复杂度均摊题目 。
只需要考虑删除操作时的时间复杂度 。保证复杂度的重点之一是精确定位到所有包含最大值的区间 ， 即不去碰多余的区间 。每次删除操作会删除若干个整个区间，以及至多两个区间被删一半 。
由于一共最多插入了 \(O(m\log n)\) 个区间，所以前一半的复杂度是对的 。
对于后一半，直接暴力将区间切半向下递归，于是两个儿子要么一个留下一个递归，要么一个删掉一个递归，递归层数至多 \(O(\log n)\)，于是这一步复杂度也至多 \(O(m\log n)\) 。
总共复杂度就俩 \(\log\)（注意其中一个是 set 的，线段树只有一个 \(\log\)?。?
【P7476 苦涩 题解】
推荐阅读
- [题解] Codeforces Global Round 22 1738 A B C D E F 题解
- 基础&进阶 线段树学习笔记（一） | P3372 【模板】线段树 1 题解
- 移动端touch拖动事件和click事件冲突问题解决
- 高中英语阅读理解解题技巧方法快速提高 高中英语阅读理解题解题技巧
- 如何培养学生问题解决的能力口诀 如何培养学生问题解决的能力
- 厦门中学转学热门问题解答电话 厦门中学转学热门问题解答
- 学车常见的16个问题解答 学车小知识
- 2020年泰山区中小学招生意见 2023泰山区中小学招生入学问题解读
- 科目一交通信号灯易错题解析 科目一交通信号灯题目
- 初一利润问题解题技巧