题意
给定平面上 \(n\) 个点，保证两两横纵坐标不同：
- 对于所有横坐标为 \(x\) 的点，权值 \(v_i = v_i ^ 2\)。
- 询问所有纵坐标为 \(y\) 的点的权值之和。
\(n \le 10 ^ 6\)。
Sol
根号分治，考虑对于所有横坐标相同的点分组。
对于修改操作，若当前修改的组大小 \(\le B\)，那么直接暴力修改，否则打上标记。
查询时需要对于当前的纵坐标，枚举所有在当前纵坐标出现的 \(> B\) 的组。
标记的处理直接快速幂复杂度为 \(O(n \sqrt{n \log n})\)。
考虑光速幂，由于不同的底数只有 \(n\) 个，因此考虑在二进制上分块，每块 \(8\) 位，这样预处理的复杂度变为了 \(2 ^ 8 \times 4\)。
离线下来，然后对于每组预处理跑光速幂，复杂度 \(O(n \sqrt n)\)。
但是实际上跑得比带 \(\log\) 快不了多少。。。。
标签：le,log,纵坐标,复杂度,P9994,Ynoi,2024,132,Easy From： https://www.cnblogs.com/cxqghzj/p/18514569