赫露艾斯塔/半平面莫队

莫队我们实际上把 \(m\) 个询问分成若干组，然后一组内 \(|S_i\oplus S_{i+1}|\) 有保证。跨组的总数不多。

半平面莫队是，我们随机 找出 \(B\) 个关键点，然后我们把一个半平面分配给它包含着，并且离他最近的关键点。

然后一个关键点组内按照斜率排序。

块间很显然贡献就是 \(O(Bn)\)。

块内这么考虑 \(|a\oplus b|\leq |a\oplus a'|+|a'\oplus b'|+|b'\oplus b|\)。

我们记 \(S_i'\) 为将 \(S_i\) 这个半平面平移到关键点后的半平面。

这样我们就可以把原先的放缩成：

\[ 2\sum |S_i\oplus S_{i}'|+\sum |S_i'\oplus S_{i+1}'| \]

不难分析出后面那个实际上就是 \(O(n)\) 的。

然后考虑 \(S_i\oplus S_{i}'\) 如果我们把整个平面旋转成 S_i 是竖直的。那么变成了一个序列上随便选 \(B\) 个关键点，问你一块内部点数的期望。

这就是 \(n/B\) 呀。

然后就能分析出来复杂度是 \(O(nB+\frac{mn}{B}\) 这个就是取到 \(\sqrt m\) 就行了。

---

数学啥都不会了。

\(Ax+By+C=0\) 的法向量是 \((A,B)\)......排序时候排法向量就行了。。。。。