呜呜呜，昨天打 CF 好拉跨。
59 P7220 [JOISC2020] 掃除
做到下面那道题的时候突然想起来忘记记录这题了。
一个结论是，所有被扫过一次的灰尘，两两之间位置关系都是“左上-右下”，而且相对顺序不会改变。
如果只有向右扫操作，它就是一个后缀取 max。加上向上扫操作，它事实上会让后面某些向右扫操作影响的灰尘范围变小。我们可以用线段树维护每个向右扫影响哪段后缀，向上扫影响哪段前缀。
于是我们需要找到灰尘第一次被扫到的位置，它只限制操作的 \(l\) 在某个区间，这很容易处理。
由于上面的算法不太能支持插入，我们对插入的过程线段树分治就好了，复杂度 \(O(q\log^2 q)\)。
好像还有一种比较暴力的做法，我们对直角三角形建出一棵线段树一样的结构，（大概每次从中点劈开，划分成一个大正方形和两个小直角三角形，递归处理三角形）它与动态开点线段树性质差不多，我们每个结点维护一个数据结构就好了。
60 uoj#712. 【北大集训2021】简单数据结构
和上面那题的思想类似。
我们记录进行了多少次操作 \(2\)，那么操作 \(1\) 就是全局对一条直线 chkmin。
我们发现，进行了有效的 chkmin 操作的点，操作 \(1\) 的影响范围会是一段后缀，这显然可以线段树二分。
我们只需找到每个数第一次被 chkmin 的时间，这个可以整体二分+李超树，复杂度 \(O(n\log^2 n)\)。
**61 **
标签：11,13,12,后缀,线段,我们,操作,灰尘,chkmin From： https://www.cnblogs.com/xiaoziyao/p/16978099.html