算法1:
考虑没有插入操作怎么办。
先考虑sub3。
定义一个点在边界上:它的右上角没有任何点。
注意到无论怎么进行操作,在边界的点还是会在边界,且顺序不会交换。
所以可以用线段树二分简单维护。
再考虑sub4。
sub4和sub3的区别:在sub3中每个点都在边界上,但是sub4并不。
但是注意到如果一个点在边界上,则它在之后的操作它还是在边界上。
所以可以使用线段树+平衡树维护。
开平衡树维护边界上的点的x/y坐标。
不能用线段树,因为要支持插入操作。
在修改时在平衡树二分+平衡树区间赋值维护。
在操作时,可能有新的点到达边界。
使用两个线段树找点即可。
(这个部分还是不太懂)
由于每个点会被插入到平衡树中至多1次,所以时间复杂度是\(O(n\log_2 n)\)
有插入操作时,注意到每个修改操作对答案的贡献是独立的,于是可以使用时间线段树规避删除。
算法2:
算法1太难写了,考虑一种更好写的算法。
(咕)
相关文章
- 11-03AI:2020年6月22日北京智源大会演讲分享之10:40-11:30 Zoubin教授《Probabilistic Machine Learning and AI》
- 11-03动手学深度学习 | 实战:Kaggle房价预测+课程竞赛:加州2020年房价预测 | 13
- 11-03安卓面试题2020,靠着这份190页的面试资料
- 11-032020-03 前端技术汇总
- 11-03最新 | 机械工程领域SCI期刊一览(2020JCR)
- 11-03高级综合英语写作(2020秋)Week1-Lesson1 讲解内容翻译笔记
- 11-032020-12-29
- 11-03浅尝Unity ECS的笔记 2020 System and Component(三)
- 11-03【题解】「P6832」[Cnoi2020]子弦
- 11-03SM NOIP2020模拟赛3 2020.9.9