研究对象
在一个B维直角坐标系下，第i维坐标在一个整数范围[li,ri]间，内部的点集称为一个B维正交范围。
一般1维正交范围简称区间，2维正交范围简称矩形，3维正交范围简称立方体
对于B维正交范围，每一维都有两个限制，即有两条边（side），这样是一个2B-side的B维正交范围
如果部分维只有一个限制，则是一个A-side的B维正交范围
如果有一维没有限制，则这一维是平凡的，没有任何意义，可以简化到一个(B-1)维的问题
A-side的B维正交范围不能确定出是哪些维，如果维不对称的话需要特殊说明
模型
扫描线有两种模型：
- 对于一个静态的二维问题，我们可以使用扫描线扫一维，数据结构维护另一维
在扫描线从左到右扫的过程中，会在数据结构维护的那一维上产生一些修改与查询
如果查询的信息可差分的话直接使用差分，否则需要使用分治 - 另一种看待问题的角度是站在序列角度，而不站在二维平面角度
如果我们这样看待问题，则扫描线实际上是枚举了右端点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\) 轴表示权值。
先差分，去掉序列维度的左端，然后对序列维度扫描线，维护竖着的数据结构，支持单点加点和区间查询和。
能使用树状数组尽量使用树状数组，这里可以差分（加法有逆）所以可以使用树状数组维护。
问题 2. 给一个二维平面，上面有n个矩形，每个矩形坐标[1,n]
有m次查询，每次查询一个二维平面上的点被多少矩形包含
对某一维从左到右扫描线并且维护每个点被多少个矩形包含。有区间修改，单点查询，把区间修改差分掉变两个前缀修改，单点查询差分掉变两个前缀查询，可以用树状数组维护。
几个例子
一维数颜色
【题意】
给定长度为 \(n\) 的序列，\(m\) 次查询区间中不同的数个数。
【分析】
思路 1：
我只想计算第一次在区间内出现的数的个数。考虑记 \(pre_i\) 表示上一个和自己相同的数的位置，那么只统计 \(l \le i \le r, pre_i < l\) 的 \(i\) 个数。两个维度分别是 \(i, pre_i\)，是二维数点问题。可以扫描线树状数组。（直接用二维前缀和处理是 \(O(nm)\) 的，不适合本题，适合稠密的矩形）。
思路 2：
考虑扫描线扫右端点，维护所有左端点的答案。我们只对区间内第一次出现的数统计答案。也就是对 \(l > pre_r\) 的位置的答案加上 \(1\)。（也有些像 dp 数组一起进行递推，然后用数据结构维护）
思路 3：
扫描线的时候同时维护一个数组表示每个颜色最后一次出现的位置。然后修改是单点赋值为 \(r\)，查询是询问数组里面比 \(k\) 大的数有多少个。可以用 set 啥的做。而且插入都是从末尾插入。
思路 4：
分块，考虑每一块维护一个 bitset，线段树维护。
单次询问时间 \(O(\cfrac{n \log(\sqrt n)}{\omega})\)。这个不需要打乱询问次序。
思路 5：
莫队。
支持单点修改和区间查询颜色数
在线（存在单点修改）怎么做：
（待填坑）
二维数颜色
【分析】
思路 1：
依然使用之前的想法，记录两个属性 \(a_i\) 表示