《范围修改查询问题相关算法及其应用》学习笔记
简单写一下，主要是原来有一个不懂的东西可以在这里做完，但真很难用到。
抽象信息的定义
半群：在集合 \mathcal{D} 上的二元运算 \mathcal {D*D\to D}，满足结合律。
幺半群：在半群基础上存在幺元 \epsilon 满足 \forall a\in \mathcal{D},\epsilon*a=a*\epsilon=a
交换半群：在半群基础上运算 \mathcal {D*D} 满足交换律。
离线范围修改查询
更广的范围，一个范围代表初始点集的一个子集。
可以用一个信息表示范围内点的信息和，用一个信息表示对范围的一个修改。这两个信息满足的条件是：
- 两个范围可以 O(1) 合并；
- 一个相邻范围的两次修改可以 O(1) 合并；
- 知道一个范围的信息可以 O(1) 计算一次修改后的信息。
问题形式：
给出交换半群 (\mathcal{D,+})，半群 (\mathcal{M,*})，二元运算符 *,\mathcal{D*M\to D}，其中 * 满足结合律 a*b*c=a*(b*c) 和分配律 (a+b)*c=a*c+b*c。
给定初始集合 I_0，有限集合 I\subseteq I_0 满足 I 每个点都有权值 d_0(x)\in \mathcal{D}，询问集合 Q。
定义以下操作：
- 范围修改：给出范围 q_i\in Q,f_i\in \mathcal{M}，将 x\in q_i,d(x)\leftarrow d(x)*f_i。
- 范围查询：给出范围 q_i\in Q 查询 \sum\limits_{x\in q_i} d(x)。
点数 |I|=n，操作次数 m。
等价关系：点 x_1,x_2 当且仅当对于操作序列 q_{1\sim n},\forall i\in [1,n], x_{1}\in q_i\leftrightarrow x_2\in q_i。
将等价的点归于一个等价类，有若干等价类。
可以建出一个森林，满足叶节点是一个单点，非叶子节点储存子树信息下传标记，每个节点对应一个等价类。
考虑如何在减少等价类的时候动态维护有根森林：
首先对每个点储存两个东西：对子树点的修改标记，子树内点的和。我们有一些合并某些等价类操作，相当于合并一些有根树，可以新建一个节点，上传信息。考虑需要撤销合并操作的时候就删除节点，下传标记。
做法：
如果 x 次操作能把点集划分成 F(x) 个等价类，那么按照 B 对操作分块，对块内进行分治。
当前在区间 [l,r]，那么先用当前 F(r-l+1) 个等价类合并出左区间划分的 F(mid-l+1) 个等价类，然后
做左区间的询问和修改，然后撤销合并再合并到右区间的 F(r-mid) 个等价类，再做右区间。
这样分治的时间是 T(n)=2T(\frac{n}{2})+O(F(n)C)，C 为定位要合并的子树以及合并子树的复杂度，此时暂时认为点定位是 O(1) 的。
这样操作分块的复杂度为 O((n+T(B))\frac{m}{B})，在 T(B)=O(n) 的时候有最优复杂度。
比如树上和序列上 F(n)=O(n)，此时 B=m 得到 O(n+m\log \min(n,m)) 的复杂度。
任意点集子集操作复杂度其实能做到 $O(n+\frac{nm}{\log n})$ 的，此时 $T(B)=2^B=n$。
平面修改有 $O(\log n)$ 单次询问的平面图定位算法，不过是离线的，但是也够用了。
**P7881 [Ynoi2006] rmpq**
二维正交平面半平面对所坐标点权进行幺半群运算，查一个坐标的单点值。
强制在线交互题，要求调用计算幺半群运算 $x*y$ 的结果次数（次数不计入包含幺元的查询）不超过 $2\times 10^7$。
> 技巧：看着这个操作分块是离线的，能不能强制在线？
>
> 直接暴力做是对的。
>
> 单点修改：考虑二进制分组，合并两个区间的原因是考虑左区间修改对右区间询问的贡献，合并左区间之后对右区间再做询问的贡献即可，二进制分组的时候组的大小只要保证不超过 $B$ 即可，但是因为相当于分块块长只有 $2$ 的整数次方，可能修改常数略大，但是因为是单点，询问可以在 $O(\log B)$ 个散块中定位等价类，这样会快一点。
按照 $O(\sqrt n)$ 分块，等价类森林的点只用维护修改 tag，查询的时候直接查询每一个块的 tag 然后合并即可。
注意每一个块定位等价类需要在 $x,y$ 坐标里面二分，按 $x,y$ 两维升序排序，找到第一个两维都比它大的即可。
### 半平面范围查询
在该问题中，没有修改操作，只有查询操作，查询为半平面的一侧的交换半群信息。
若可以离线，则使用上述的修改查询算法，就可以达到运算次数的下界 $O(m\sqrt n)$；但在仅有查询，没有修改的情况下，有另一些复杂度可能更低、或可以强制在线的算法。
#### 旋转扫描线
把点集按 $B$ 分块，注意一个直线可以做一个等价变换：向一个方向平移直到碰到第一个点，某个方向旋转碰到第二个点，这样发现点集不变，于是只有 $O(B^2)$ 个平面标准型， 考虑直接对每个标准型预处理答案。
考虑选一个点为源点，然后对其它点按 $(u,v)$ 的极角排序，发现扫描线的斜率角度 $\theta$ 变化时按照 $x\cos \theta+y\sin \theta$ 排序，但是发现斜率递增只有 $O(B^2)$ 次交换相邻两项就能保证顺序了，现在相当于做交换两个点，维护点集前后缀信息，可以快速修改，发现这一部分瓶颈在于极角排序，如果使用基数排序能做到 $O(nB)$，否则是 $O(nB\log B)$ 的。注意这部分可以离线的话再旋转扫描线的时候直接把询问的斜率也加入，每次只用找前驱后继，这样查询复杂度是 $O(\frac{mn\log B}{B})$，最后 $B=\sqrt m$ 可以做到 $O(n\sqrt m\log m)$，使用基数排序能做到 $O(n\sqrt {m\log m})$。
强制在线的话，预处理块之后瓶颈在于确定每个半平面对应的标准型，据说也是 $O(\log B)$ 的，实现不是很懂。
#### 点集划分树
OI 范围在二维平面中内几乎没用，不随机 non-practical，随机能 KDT 但感觉不如平面分块。
#### 平面分块
随机数据下可以按 $\sqrt n\times \sqrt n$ 分块，这样块内期望只有 $O(1)$ 个点，然后 $O(\sqrt n)$ 个散块就能暴力做了。
然后整块相当于对行列有 $O(\sqrt n)$ 次前后缀查询，可以预处理。
但是某些题不太好做
> 技巧：询问和点集反演。
>
> $(a,b)$ 满足 $cx+dx<e$ 可以化为 $(\frac{c}{e},\frac{d}{e})$ 满足 $ax+by<1$，也是一个半平面范围。
#### 基于随机的期望最优半平面莫队
**[Ynoi2003] 赫露艾斯塔**
有若干点和半平面，构造一个半平面的排列，使得相邻两个半平面包含点集的对称差集合大小之和 $\leq M$。
考虑对称差大小就是两个集合移动时删除和增加的点数的规模。
随机选取 $B$ 个点，然后询问挂到直线向上平移遇到的第一个关键点，不难发现期望只要移动 $O(\frac{n}{B})$ 个点就能找到一个关键点，考虑上移动回去的代价就不超过 $\frac{mn}{B}$。
对于每个点的询问直线按斜率大小排序，以这个点为中心进行旋转扫描线，这部分代价 $nB$。
最后时间复杂度为 $O(nB+\frac{mn}{B})$，$B$ 取 $\sqrt m$ 能做到 $O(n\sqrt m)$ 级别的移动。
如果暴力找最近的关键点还要暴力遍历关键点算距离，这样会有一个 $O(m\sqrt m)$ 的时间，感觉不好避免。
这题只是构造遍历顺序所以好写，但是实际做的时候还是感觉非常复杂的。