心灵突击队题解¶

解法比较¶

出题人解法按行分块。每行各有一棵维护列区间的延迟线段树；每个行块另外保存各行基础值的合计，以及整个块统一增加的列区间标记。矩形操作遇到完整行块时修改或查询块树；边界不完整的块逐行处理，并维护块合计。整块标记与逐行基础值相加，恰好还原每格的值，所以矩形和可以分块相加。

设网格有 \(H\) 行、\(W\) 列，块长为 \(B\) ，出题人解法每次操作为 \(O((H/B+B)\log(W+1))\) ，空间为 \(O(HW)\) .Codex（GPT-6）采用的实现用四棵二维树状数组维护带权差分，把操作时间改为 \(O(\log(H+1)\log(W+1))\) ，空间仍为 \(O(HW)\) .收益是减少行块枚举，代价是每次前缀计算涉及四组带权数据；差分展开和正确性见下文。

将轰炸拆为矩形¶

\(r=1\) 是单点更新。\(r\ge2\) 时，中心部分是 \([x-r+1,x+r-1]\times[y-r+1,y+r-1]\) ，另有四条宽度为一格的外围矩形。例如左侧条带为 \(\{x-r\}\times[y-r+2,y+r-2]\) . 五块互不重叠，分别增加 \(p\) 或 \(\lceil p/4\rceil\) .

所有矩形先与记录区域求交。空交集直接跳过或回答零，再把坐标平移为从 \(1\) 开始的局部坐标。权重使用局部坐标，避免绝对坐标放大乘积。

四棵二维树状数组¶

以下均使用平移后的局部坐标。记格值数组为 \(A\) ，令第 \(0\) 行与第 \(0\) 列的值为零，定义二维差分

\[ D_{i,j}=A_{i,j}-A_{i-1,j}-A_{i,j-1}+A_{i-1,j-1} \]

给闭矩形 \([x_1,x_2]\times[y_1,y_2]\) 加上 \(\Delta\) ，等价于下面四个差分点更新：

差分位置	增量
\((x_1,y_1)\)	\(\Delta\)
\((x_1,y_2+1)\)	\(-\Delta\)
\((x_2+1,y_1)\)	\(-\Delta\)
\((x_2+1,y_2+1)\)	\(\Delta\)

超出记录区域的差分点无需存储。设 \(S(x,y)\) 为 \([1,x]\times[1,y]\) 内所有格子的总和；若 \(x=0\) 或 \(y=0\) ，规定其值为零。差分值 \(D_{i,j}\) 会影响该前缀内右下方的 \((x-i+1)(y-j+1)\) 个格子，所以

\[ S(x,y)=\sum_{i\le x,j\le y}D_{i,j}(x-i+1)(y-j+1) \]

展开得到

\[ S(x,y)=xy\sum D-y\sum (i-1)D-x\sum (j-1)D+\sum(i-1)(j-1)D \]

式中每个求和的范围都是 \(1\le i\le x,1\le j\le y\) . 用四棵二维树状数组分别维护 \(D\) 、\((i-1)D\) 、\((j-1)D\) 和 \((i-1)(j-1)D\) 的前缀和。更新一个差分点时，同时把对应的四个权值加入树状数组。

任意闭矩形的答案由容斥得到：

\[ S(x_2,y_2)-S(x_1-1,y_2)-S(x_2,y_1-1)+S(x_1-1,y_1-1) \]

源码把同一位置的四个权值存于一个数组元素中，更新和查询时一并处理。

正确性¶

矩形拆分逐格等价于轰炸定义，且各部分不重复计数。裁剪只丢弃题目明确不记录的格子。二维差分的四点更新恰好还原一次矩形加法；展开式累计每个差分值影响的格子数，得到前缀总和。最后的容斥精确选中查询矩形，因此所有操作顺序执行后答案正确。

复杂度与整数范围¶

令记录区域宽、高为 \(W,H\) ，均不超过 \(1001\) . 时间 \(O(WH+m\log(W+1)\log(H+1))\) ，空间 \(O(WH)\) . 一次轰炸至多执行五次矩形更新。

一次操作对同一格子的增量绝对值至多为 \(10^4\) ，因此格值绝对值不超过 \(3\times10^8\) ，区域和绝对值不超过 \(3\times10^8WH\) . 对中间结果取保守上界：每次操作至多产生 \(20\) 个差分点更新，每个权值最多额外乘上 \(WH\) ；前缀公式有四项，矩形容斥又有四项。因此计算过程中的绝对值可界定在 \(320m\cdot10^4WH<10^{17}\) 以内，有符号 64 位整数足够。

负值必须保留，不能截断为零。半径为 \(1\) 、单行或单列、完全越界、零强度均无需特殊的数据结构。