# 心灵突击队题解

## 解法比较

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

设网格有 $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$ 、单行或单列、完全越界、零强度均无需特殊的数据结构。