# 方伯伯浇水2## 题目描述方伯伯有一块玉米田玉米田可以视为平面直角坐标系上横纵坐标在 $-10^5$ 至 $10^5$ 范围内包括边界的一片正方形区域。玉米田内的每个整点横纵坐标均为整数的点上都种着一株玉米。方伯伯连续 $m$ 天对玉米田进行浇水每天他会选出一个圆心坐标为 $xy$半径为 $r$ 的圆形区域对其中不包括边界的每株玉米浇一次水如果圆形区域超过玉米田边界超过部分无需浇水。最开始所有

算法1

暴力模拟

对于每一天浇水，遍历所有的玉米，判断是否在圆形区域内，如果在则品质加1。

对于每一株需要调查的玉米，直接输出品质即可。

时间复杂度 $O(mn)$，其中 $n$ 为玉米数量，过不了本题。

算法2

前缀和优化

对于每一天浇水，不需要遍历所有的玉米，可以通过前缀和优化。

首先，需要统计出每个位置的玉米数量，可以使用二维前缀和进行预处理。

然后，对于每一天浇水，可以计算出圆形区域内的左上角和右下角位置，再利用二维前缀和计算圆形区域内的玉米数量，最后将圆形区域内的所有玉米品质加1。

对于每一株需要调查的玉米，可以直接查询其品质。

时间复杂度 $O(m+n\log n)$，其中 $n$ 为玉米数量，可以通过本题。

C++ 代码