线套线
-
规定使用 OI 坐标系。
-
（按我的代码习惯）竖着关于 \(1\sim n\) 建一棵线段树，该线段树的每个节点都是一棵内层线段树，若该节点的管辖区间为 \([L,R]\)，则该内层线段树的管辖范围为 \(l,r\) 的节点的实际管辖矩形为 \((L,l)\sim (R,r)\)。
单点加，矩形查
-
修改：在外层树上找 \(x\)，经过的每个点（注意不是经过点。包括到达点）对应的内层树上都单点修 \(y\) 处。
-
询问：在外层树上找 \([xl,xr]\)，在每个到达点对应的内层树上区间查 \([yl,yr]\)。
-
容易看出，单次修改中修改到的内层树在询问中是互斥的，即只有一个会被询问到，毕竟区间询问的到达点不共链。故其正确性显然，单操作复杂度 \(O(\log^2)\)。
矩形加，单点查
- 做二维差分转化为单点加，矩形查。
矩形加，矩形查
-
考虑推广单点加，矩形查的做法。先假设我们的修改的到达点全部是叶节点，此时直接沿用单点加，矩形查的操作即可。
-
注意到这么做的问题在于，不妨举个例子，如果修改的到达点为 \([1,2]\)，而询问的为 \([1,1]\)，则没有算到这次修改的影响。
-
考虑把较大的内层树视为较小的内层树的标记，在询问的过程中，从 \([1,1]\) 退栈到 \([1,2]\) 后，用完全相同于在 \([1,1]\) 对应的树上查的方式上 \([1,2]\) 对应的树来查贡献，最后要乘上区间交的长度。
-
注意到此时可能一次修改中修改的一条链都会被当做标记永久化的标记来算贡献，显然算重了。故开标记树，其与内层树的区别在于内层树在修改中是每个经过的点都进去修，而标记树是仅在到达点进去修。然后退栈的时候在标记树而非内层树上查标记的贡献。
-
因为区间修改和询问的访问总点数是 \(O(\log)\) 的，所以这是 \(O(\log^2)\) 的。容易看出标记树的空间严格小于对应的内层树，所以空间还是 \(O(\log^2)\) 的。
-
如果想做区间覆盖之类奇怪的东西，则要使用扫描线模板中提到的奇怪的区间永久化方法。