Link

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

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

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

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

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

最新文章

1. Azure底层架构的初步分析
2. 外网无法访问本地IIS站点
3. js循环添加事件的问题
4. PDF 生成插件 flying saucer 和 iText
5. Asp.net Identity 2.0 作弊条
6. hiveql basic
7. mysql慢查日志分析工具 percona-toolkit
8. PHP中的session
9. python学习day4--python基础--字典
10. Android apk获取系统权限
11. nat网络穿透整理笔记（思维导图）
12. java使用验证码进行登录验证
13. [HMLY]12.iOS中的Protocol
14. Domain=com.alamofire.error.serialization.response Code=-1016 "Request failed: unacceptable content-type: text/html"
15. 实操代码研究各种Java技术-java.toutiao.im
16. 用Python玩转微信（一）
17. c++实现一个小算法
18. [LeetCode] Trim a Binary Search Tree 修剪一棵二叉搜索树
19. 560. Subarray Sum Equals K 求和为k的子数组个数
20. 如何将爬取的数据写入ES中

热门文章

1. Hadoop-HA 搭建高可用集群Hadoop Zookeeper
2. 第十七天python3 文件IO(三)
3. 常用的函数式接口Function接口和常用的函数式接口Function接口默认方法andThen
4. 物无定味适口者珍，Python3并发场景(CPU密集/IO密集)任务的并发方式的场景抉择(多线程threading/多进程multiprocessing/协程asyncio)
5. JavaScript 权威指南-学习笔记（一）
6. Luogu4084 [USACO17DEC]Barn Painting （树形DP）
7. Java jdk常用工具集合
8. 痞子衡嵌入式：浅析IAR下调试信息输出机制之半主机(Semihosting)
9. 👍CleanShot X 3.1.1 破解版 (超强屏幕截图录像工具) (TNT + 免激活)
10. 我用开天平台做了一个字符串检查API，hin 简单~~