题解

思路

一次查询与一次修改的贡献等于两个闭矩形交集中的整数点数乘以修改量。小操作数时可以逐对求交；坐标范围较小时可以直接在网格上做二维差分。

满分范围需要离线处理。令 $F(X,Y)$ 表示所有满足 $x\le X,y\le Y$ 的整数点权值和，则任意查询矩形可由四个二维前缀值容斥得到。

考虑一次修改 $[x_1,x_2]\times[y_1,y_2]$，增量为 $v$。它对 $F(X,Y)$ 的贡献可以写成两个一维覆盖长度的乘积：

其中 $A_X(X)$ 是区间 $[1,X]$ 与 $[x_1,x_2]$ 的交集中整数点数量，$A_Y$ 同理。

对 $X\ge x_1$，先加入 $v(X-x_1+1)A_Y(Y)$；对 $X\ge x_2+1$，再减去 $v(X-x_2)A_Y(Y)$。这样每次修改产生两个横坐标事件。

同理，$A_Y(Y)$ 可由在 $y_1$ 加入一次线性函数、在 $y_2+1$ 减去一次线性函数表示。展开横纵两个线性函数的乘积后，贡献形如

因此按 $X$ 排序扫描横坐标事件和前缀询问，并用四棵树状数组按 $Y$ 维护上述四类系数即可。

做法

子任务 1

枚举每个查询和每次修改，计算两个闭矩形在横纵方向上的交集长度。交集为空时贡献为零，否则把交集整数点数乘以 $v$ 加入答案。

时间复杂度为 $O(nq)$，空间复杂度为 $O(n)$。

子任务 2

在 $(W+2)\times(W+2)$ 数组上对每次矩形修改做四角差分，再做二维前缀和得到每个点的最终权值。随后再做一次二维前缀和，即可常数时间回答每个矩形查询。

时间复杂度为 $O(W^2+n+q)$，空间复杂度为 $O(W^2)$。

满分算法

把每个查询矩形拆为四个二维前缀询问。将修改拆成两个横向事件，每个横向事件再拆成两个纵向系数更新。所有横向事件和询问按 $X$ 排序，先加入横坐标不超过当前询问的全部事件，再从四棵树状数组取得 $Y$ 前缀系数并代入线性式。

坐标 $x_2+1$ 或 $y_2+1$ 可能等于 $W+1$，树状数组和事件范围必须为此额外保留一个位置。所有系数、乘积与答案都使用 64 位有符号整数。

正确性证明

每次修改对二维前缀 $F(X,Y)$ 的贡献，正好是修改矩形在 $[1,X]\times[1,Y]$ 内的整数点数乘以 $v$，即两个一维交集长度的乘积。

横向的两个事件分别建立并截断 $A_X(X)$ 的线性表达式，纵向的两个更新分别建立并截断 $A_Y(Y)$ 的线性表达式，所以四棵树状数组维护的展开式在任意 $(X,Y)$ 上都等于该修改对 $F(X,Y)$ 的真实贡献。对全部修改求和后，得到的就是二维前缀权值和。

每个查询矩形通过四个二维前缀值按包含—排除原理组合，因此得到的答案恰为查询闭矩形内所有整数点的最终权值和。

复杂度分析

每次修改产生常数个事件，每次查询产生四个前缀询问。排序和树状数组操作的总时间复杂度为 $O((n+q)\log(n+q))$，空间复杂度为 $O(n+q+W)$。