题解：P15839 [蓝桥杯第一届国际赛] 莲蓬池

· · 题解

考虑莫队。

考虑如何处理莫队指针移动时产生的贡献。首先，x 和 y 两维的贡献互不影响，因此可以分开计算。

对于距离中的绝对值，加入或删除一个元素时，可以将当前区间内已有坐标按与当前坐标的大小关系分为两类分别统计。于是可以用树状数组在离散化后的值域上维护各坐标值的出现次数以及坐标值之和。由于 |x_i|,|y_i|\le 10^8，值域较大，因此需要先离散化。

最后卡卡常就过了。