扫描线

研究对象

在一个B维直角坐标系下，第i维坐标在一个整数范围[li,ri]间，内部的点集称为一个B维正交范围。
一般1维正交范围简称区间，2维正交范围简称矩形，3维正交范围简称立方体
对于B维正交范围，每一维都有两个限制，即有两条边（side），这样是一个2B-side的B维正交范围
如果部分维只有一个限制，则是一个A-side的B维正交范围
如果有一维没有限制，则这一维是平凡的，没有任何意义，可以简化到一个(B-1)维的问题
A-side的B维正交范围不能确定出是哪些维，如果维不对称的话需要特殊说明

模型

扫描线有两种模型：

1. 对于一个静态的二维问题，我们可以使用扫描线扫一维，数据结构维护另一维
   在扫描线从左到右扫的过程中，会在数据结构维护的那一维上产生一些修改与查询
   如果查询的信息可差分的话直接使用差分，否则需要使用分治
2. 另一种看待问题的角度是站在序列角度，而不站在二维平面角度
   如果我们这样看待问题，则扫描线实际上是枚举了右端点r=1…n，维护一个数据结构，支持查询对于当前的r，给定一个值l，l到r的答案是什么
   即扫描线扫询问右端点，数据结构维护所有左端点的答案

Notice：
其实看到任何范围修改查询问题，如果能差分的话，想都不想就差分是不会有问题的，我推荐直接这样做
典型的差分方法：
序列区间[l,r]差分为[1,r]-[1,l-1]的前缀
树上差分
二维前缀和的差分

处理二维正交范围的扫描线

问题可差分的时候，我们通过差分可以将一个4-side矩形查询问题变为两个3-side矩形查询问题的差
将第一维的1-side的区间（即前缀）扫描线扫掉，数据结构维护2-side的区间查询（这里两条边是相对的而不是相邻的），支持：
1.单点修改，区间查询
2.区间修改，单点查询
3.区间修改，区间查询
中的一种
（不要忘记了差分）

两大基础问题：

问题 1. 给一个长为n的序列，有m次查询，每次查区间[l,r]中值在[x,y]内的元素个数

我们考虑 \(x\) 轴表示序列，\(y\) 轴表示权值。

先差分，去掉序列维度的左端，然后对序列维度扫描线，维护竖着的数据结构，支持单点加点和区间查询和。

能使用树状数组尽量使用树状数组，这里可以差分（加法有逆）所以可以使用树状数组维护。

第二维度可以看作时间维度，那么这时候修改从左到右并且强制在线，是主席树最经典的应用。主席树利用较少位置被修改的性质，最小化了开点的个数。对于区间修改也是可以主席树的。
当然，本着能不线段树就不线段树的原则，依然是可以树状数组做。考虑树状数组进行一次修改也是只需要修改 \(\log n\) 个节点，可以做可持久化树状数组。

问题 2. 给一个二维平面，上面有n个矩形，每个矩形坐标[1,n]
有m次查询，每次查询一个二维平面上的点被多少矩形包含

对某一维从左到右扫描线并且维护每个点被多少个矩形包含。有区间修改，单点查询，把区间修改差分掉变两个前缀修改，单点查询差分掉变两个前缀查询，可以用树状数组维护。