joisc 2020 扫除

算法1:
考虑没有插入操作怎么办。
先考虑sub3。
定义一个点在边界上:它的右上角没有任何点。
注意到无论怎么进行操作,在边界的点还是会在边界,且顺序不会交换。
所以可以用线段树二分简单维护。
再考虑sub4。
sub4和sub3的区别:在sub3中每个点都在边界上,但是sub4并不。
但是注意到如果一个点在边界上,则它在之后的操作它还是在边界上。
所以可以使用线段树+平衡树维护。
开平衡树维护边界上的点的x/y坐标。
不能用线段树,因为要支持插入操作。
在修改时在平衡树二分+平衡树区间赋值维护。
在操作时,可能有新的点到达边界。
使用两个线段树找点即可。
(这个部分还是不太懂)
由于每个点会被插入到平衡树中至多1次,所以时间复杂度是\(O(n\log_2 n)\)
有插入操作时,注意到每个修改操作对答案的贡献是独立的,于是可以使用时间线段树规避删除。
算法2:
算法1太难写了,考虑一种更好写的算法。
(咕)

上一篇:「JOISC 2019 Day2」两种运输


下一篇:LOJ2398. 「JOISC 2017 Day 3」自然公园