从今年集训队论文出发，揭秘一下《十字神名的预言者》慈悲（色彩）。
下文问题均为离线，信息均为交换群。
离线范围修改查询
当范围是区间时，我们可以利用线段树这一特化的分治结构解决问题。下面研究范围是半平面的情形。
给定平面上的 \(n\) 个点，初始点权为 \(0\)，要求支持两种操作：
- \(A_i,B_i,C_i,x_i\)，对于 \((A_i,B_i,C_i)\) 表示的半平面上的点，点权 \(+x_i\)。
- \(A_i,B_i,C_i\)，查询半平面 \((A_i,B_i,C_i)\) 的点权和。
对于这种问题，我们的做法是等价类分治（更经典的称呼是 tb5 分治）。对操作序列进行分治，对于分治过程中涉及到的操作序列的一段区间 \([L,R]\)，称 \(i\) 和 \(j\) 两个点在 \([L,R]\) 上等价，当且仅当 \(\forall L\leq k\leq R\)，\([i\in(A_k,B_k,C_k)]=[j\in(A_k,B_k,C_k)]\)。在分治过程中维护当前区间 \([L,R]\) 对应的所有等价类虚点，\(solve(L,R)\to solve(L,M)\) 时需要合并若干等价类，枚举所有等价类，求出该等价类在 \([L,M]\) 上对应的哈希值 \(h_i\)，合并 \(h\) 相同的等价类（新建一个虚点作为这些等价类的父亲，新点的信息是对应等价类信息的复合）。回溯时释放虚点上的标记。
难点在于求出 \(h_i\)。我们对于每个操作随机哈希值 \(H_i\)，进行 \([L,M]\) 的所有操作，查询单点哈希值。修改操作的总数是 \(O(m\log m)\)，查询次数则和整个分治过程中涉及到的等价类总数同阶。这个问题可以做，但我们将在后面介绍更好的方式。
分析“在代数结构上操作的次数”，设 \(G(m)\) 代表 \(m\) 次操作最多将点集划分成多少等价类，有 \(T(n,m)=O(\min(G(m),n))+2T(n,\frac m2)\)，此处 \(G(m)=O(m^2)\)，所以 \(T(n,m)=O(\min(m^2,n))+2T(n,\frac m2)\)，当 \(G(m)\) 在忽略对数因子后增长速率高于线性的情况下，等价类分治的时间复杂度是最优的。
通常情况下的实现是按照 \(B\) 分块，逐块处理，满足 \(G(B)\leq n\)。\(T(n,m)=O(m^2)+2T(n,\frac m2)=O(m^2)\)，复杂度为 \(\frac mB(O(n)+T(n,B))=O(mB+\frac{m^2}B)\)。
区间范围并
给出一个范围序列，求区间范围并的信息复合。
对于范围序列扫描线，新增范围 \(R_i\) 时，将 \(R_i\) 中的所有点打上 \(i\) 标记，则对于查询区间 \([l,i]\)，就是求标记 \(\geq l\) 的信息复合。打标记那一步，我们将其变为范围覆盖，需要在这个过程中用另一个数据结构维护标记后缀的信息复合。
- 范围为矩形的情形
使用 KDT 维护范围覆盖。需要支持清空，暴力实现即可。“另一个数据结构”使用分块即可。
想说明的是，不一定必须使用等价类分治处理范围覆盖。
- 范围为半平面的情形。
使用等价类分治维护范围覆盖。
清空依然暴力清空。
重点关注如何实现等价类合并。可以通过扫描线构造出初始 \(O(B^2)\) 个区域，然后分治过程中会不断删去半平面，处理区域的合并即可。
复杂度分析等醒来再说，难死我了。