算法常见题型之前缀和差分区间覆盖进阶平面圆覆盖例题https://www.luogu.com.cn/problem/P16684一、题目大意提炼给定nnn个圆心、半径均为整数的圆qqq次询问每次给出一个整数坐标点判断该点被多少个圆覆盖点在圆边界上也算覆盖若覆盖次数为奇数输出Yes区域为彩色若覆盖次数为偶数输出No区域为无色。二、基础回顾一维差分模板核心作用一维差分数组用于批量区间修改 单次前缀和还原可以在O(1)O(1)O(1)时间内给区间 [L,R] 的所有元素统一加上一个值最后通过一次前缀和得到最终数组是处理区间覆盖问题的基础工具。标准模板vectorintd(n2,0);// 差分数组// 给区间[L, R]所有元素加valvoidadd(intL,intR,intval){d[L]val;d[R1]-val;}// 前缀和还原原数组for(inti1;in;i){d[i]d[i-1];}时间复杂度区间修改O(1)O(1)O(1)还原数组O(n)O(n)O(n)三、思路分析从暴力到优化暴力法的局限最朴素的做法每次询问遍历所有nnn个圆通过距离公式判断点是否在圆内。时间复杂度O(q∗n)106∗103109O(q * n) 10^6 *10^3 10^9O(q∗n)106∗103109运算量过大必然超时。突破口坐标范围有限题目中所有坐标均为 1到1000 的整数整个平面只有 1000*1000 1e6 个整数点。我们可以预处理出所有整数点的覆盖次数之后每次询问O(1)O(1)O(1)直接查表适合百万级查询量。进阶思路降维 差分直接逐圆逐点标记覆盖最坏复杂度为 O(n*πr2)3e8依然偏高。利用圆的几何性质优化对任意一个圆固定每一行yyy该行上被圆覆盖的xxx坐标一定是一段连续区间。于是我们可以把二维圆覆盖问题拆解为「每一行上的一维区间加」再用一维差分快速完成区间标记最终通过前缀和得到所有点的覆盖次数。四、算法核心原理圆的行扫描公式对于圆心 (x0,y0)、半径rrr的圆任取一行yy0jjjj为行偏移量-r j r根据圆的方程 代入y−y0jy-y0jy−y0j可得该行x的覆盖范围即每一行对应一个连续区间 [L, R]其中Lx0−dL x0 - dLx0−dRx0dR x0 dRx0d差分标记 前缀和还原定义二维差分数组g[x][y]对每一行yyy独立维护x方向的差分对每个圆遍历所有行偏移量jjj计算对应行的区间 [L,R]执行差分操作g[L][y]、g[R1][y]--所有圆标记完成后对每一行yyy沿x方向做前缀和g[x][y]即为点(x,y)(x,y)(x,y)的覆盖次数查询时直接判断g[x][y]的奇偶性即可。五、正解代码变量定义与初始化#includebits/stdc.husingnamespacestd;constintN1010;// 坐标最大1000开1010防止越界intg[N][N];// x方向差分数组g[x][y]对应坐标(x,y)intn,m;// n个圆m次询问intx[N],y[N],r[N];// 存储每个圆的圆心与半径signedmain(){cinn;for(inti1;in;i){cinx[i]y[i]r[i];// 处理j0圆心所在的水平行inttlmax(1,x[i]-r[i]);inttrmin(1001,x[i]r[i]1);g[tl][y[i]];g[tr][y[i]]--;}for(inti1;in;i){for(intj1;jr[i];j){// 计算当前行对应的x方向半长dintdsqrt(r[i]*r[i]-j*j);intLmax(1,x[i]-d);intRmin(1001,x[i]d1);intshangy[i]j;// 上方第j行intxiay[i]-j;// 下方第j行if(shang1001){g[L][shang];g[R][shang]--;}if(xia0){g[L][xia];g[R][xia]--;}}}for(inti1;i1000;i){// 前缀和还原覆盖次数for(intj1;j1000;j){g[i][j]g[i-1][j];}}cinm;while(m--){// 处理询问inta,b;cinab;if(g[a][b]1)coutYes\n;elsecoutNo\n;}return0;}六、样例模拟样例输入2个圆圆心分别为 (1,1) 半径5、(11,1) 半径5查询点 (1,1)、(6,1)、(11,1)。差分标记圆1在 y1 行x区间 [1,5]差分g[1][1]g[7][1]--圆2在 y1 行x区间 [6,15]差分g[6][1]g[17][1]--。前缀和计算y1行x1值为 1奇数→ 输出Yesx6值为 112偶数→ 输出Nox11值为 011奇数→ 输出Yes。与样例输出完全一致。七、复杂度时间复杂度预处理每个圆遍历O(r)O(r)O(r)行总操作量约10610^6106次前缀和为 1000 *1000 10^6 次整体约 2e6 次运算效率极高。查询O(q)O(q)O(q)百万级查询无压力。八、总结本题是前缀和差分思想在二维几何问题中的经典进阶应用核心思路是降维处理将二维的圆覆盖拆解为逐行的一维区间覆盖用差分把区间修改从O(n)O(n)O(n)优化到O(1)O(1)O(1)最终通过预处理实现查询的极致效率。这种「网格覆盖 差分降维」的思路广泛适用于坐标范围有限、查询量巨大的平面覆盖类题目。