心灵突击队¶
- 参考时间限制：0.5 秒（参考环境：评测环境与性能；仅供预估）
- 实际时间限制：标准程序在目标评测环境中处理最慢正式测试文件的基准时间的 2 倍，按 0.5 秒的倍数向上取整；若平台仅支持更粗的粒度，再向上取整到平台可设置值。
- 内存限制：128 MB
背景故事¶
尤里准备把心灵突击队空投到一座训练基地。突击队擅长控制敌人，却没法用意念让辐射计少响两声。
演习中不断有轰炸向地面增加辐射，洗消车则负责降低指定区域的读数。洗消过头时，记录甚至可能变成负数。指挥部暂时不讨论仪器校准，只要求情报员按当前记录，准确汇报每块候选区域的辐射总和。
(本故事由GPT-6 Astra重写)
形式化问题描述¶
战场由整数坐标的格子组成。只记录矩形区域 \([X_{\min},X_{\max}]\times[Y_{\min},Y_{\max}]\) 中的格子，初始记录均为 \(0\) ；范围之外不参与更新或查询。\(x\) 从左向右增大，\(y\) 从上向下增大。
图 1：坐标标记在格子内部，表示整个格子的坐标。粗边框格为原点 \((0,0)\) .
用 \((u,v)\) 表示任意一个格子的坐标。依次处理 \(m\) 个操作：
0 x_1 y_1 x_2 y_2：查询闭矩形 \([x_1,x_2]\times[y_1,y_2]\) 与记录区域交集内的数值总和。交集为空时输出 \(0\) .1 x y r p：以 \((x,y)\) 为中心增加辐射。若 \(r=1\) ，仅中心格增加 \(p\) . 若 \(r\ge2\) ，所有满足 \(\lvert u-x\rvert<r\) 且 \(\lvert v-y\rvert<r\) 的格子增加 \(p\) ；满足下列任一条件的格子增加 \(\lceil p/4\rceil\) ：- \(\lvert u-x\rvert=r\) 且 \(\lvert v-y\rvert<r-1\) ；
- \(\lvert v-y\rvert=r\) 且 \(\lvert u-x\rvert<r-1\) .
2 x_1 y_1 x_2 y_2 p：将闭矩形内每个被记录的格子减少 \(p\) ，允许结果为负，不截断为零。
每次更新在已有数值上累加。轰炸中心、查询矩形和洗消矩形均可能位于记录区域外。
令 \(q=\lceil p/4\rceil\) .下图用格内的 \(p\) 、\(q\) 或 \(0\) 直接标明本次轰炸的增量；\(0\) 表示不改变该格的数值。横向和竖向分别为相对中心的偏移 \(u-x\) 与 \(v-y\) ，粗边框格为轰炸中心 \((x,y)\) .图中暂不考虑记录区域的裁剪。
图 2：\(r=1\) 时只影响中心格。
图 3：\(r=2\) 时，中间九格各增加 \(p\) ，四个外围格各增加 \(q\) ；四角不受影响。
图 4：橙色实线框表示一次洗消的闭矩形 \([0,2]\times[0,1]\) ，边界格也包含在内。图 A 假设所示格子均在记录区域内，因此六格各减少 \(p\) .图 B 的蓝色虚线框是记录区域 \([-1,1]\times[-1,1]\) ，只有交集中的四格减少 \(p\) ；灰底叉号格不参与记录。格内的 \(0\) 表示本次操作不改变该格的值。
输入格式¶
第一行包含 \(m,X_{\min},Y_{\min},X_{\max},Y_{\max}\) .
接下来 \(m\) 行，每行按上述格式描述一个操作。
输出格式¶
每个 0 操作输出一行一个整数。
样例 1¶
输入¶
8 0 0 10 10
2 0 5 0 5 50
0 0 3 0 5
1 5 5 1 100
0 5 5 5 5
1 5 5 2 40
0 5 5 6 6
1 5 5 5 400
0 6 10 6 10
输出¶
-50
100
260
100
解释¶
第一次洗消产生负值。第二次轰炸后，\([5,6]\times[5,6]\) 中的四格分别为 \(140,40,40,40\) . 最后查询的格子位于外围条带，增量为 \(400/4=100\) .
样例 2¶
输入¶
5 -1 -1 1 1
1 0 0 2 5
0 -100 -100 100 100
2 0 0 10 10 10
0 -1 -1 1 1
0 2 2 3 3
输出¶
45
5
0
解释¶
轰炸使记录区域的九格各增加 \(5\) . 洗消只影响交集中的四格，因此总和由 \(45\) 降至 \(5\) . 最后一个查询与记录区域不相交。
数据范围与保证¶
- \(1\le m\le30000\) ，所有输入坐标的绝对值不超过 \(10^8\) .
- \(X_{\min}\le X_{\max}\) ，\(Y_{\min}\le Y_{\max}\) ，两个坐标跨度均不超过 \(1000\) ；故每个维度至多有 \(1001\) 个格子。
- 查询和洗消矩形满足 \(x_1\le x_2\) ，\(y_1\le y_2\) .
- \(1\le r\le10^8\) ，\(0\le p\le10^4\) ，所有输入量均为整数。
- 操作类型仅为 \(0,1,2\) ，可没有查询；初值为零，数值允许为负。
数据分组¶
| 分值比例 | 额外条件 |
|---|---|
| 20% | \(m\le10000\) ，至少一个坐标跨度为 \(0\) |
| 20% | \(m\le10000\) ，至少一个坐标跨度不超过 \(50\) |
| 20% | \(m\le10000\) ，所有查询都在全部更新之后 |
| 20% | \(m\le10000\) |
| 20% | 无额外条件 |