自动搬运

查看原文

来自洛谷，原作者为

	FunnyCreatress AFOed.

搬运于2025-08-24 22:37:25，当前版本为作者最后更新于2022-05-10 15:07:59，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

首先这个修改就显然要差分，容易发现修改的图形做二维差分后是个叉，主对角线是正的，副对角线是负的。

然后这个查询我们给他拆成四个二维前缀和，然后考虑算贡献。对于一个修改 $(x,y,w)$ 和一个询问 $(X,Y)$ 满足 $x\le X,y\le Y$，其贡献显然为 $w(X-x+1)(Y-y+1)$，拆开后发现需要维护的就是矩形内的 $\sum w,\sum wx,\sum wy,\sum wxy$ 四个信息，我们分别解决主对角线和副对角线的情况。

先看主对角线，显然一次修改可以拆成两条射线。假设我们现在要在射线 $x-x_0=y-y_0\ge 0$ 上的整点处 $+w$，查询位置 $(X,Y)$ 满足 $Y-X\ge y_0-x_0$，即射线先交到直线 $x=X$，推一推柿子可以得到

$$\Delta w=-wx_0+(X+1)w$$ $$\Delta wx=-\dfrac12wx_0^2+\dfrac 12wx_0+\dfrac{X(X+1)}2w $$$$\Delta wy=\dfrac12wx_0^2-wx_0y_0-(X+\dfrac12)wx_0+(X+1)wy_0+\dfrac{X(X+1)}2w $$$$\Delta wxy=\dfrac16wx_0^3-\dfrac12wx_0^2y_0+\dfrac12wx_0y_0-\dfrac{3X^2+3X+1}6wx_0+\dfrac{X(X+1)}2wy_0+\dfrac{X(X+1)(2X+1)}6w $$

$Y-X<y_0-x_0$ 的情况是对称的，互换 $x,y$ 即可。分母的处理就不必多说了吧。

可以看到，需要的东西都形如 $wx^iy^j(0\le i+j\le 3)$，而且是一个关于 $y-x,x$ 以及时间的三维偏序，离线下来做 cdq 分治就行。

然后看一下副对角线的情况，显然 $x+y>X+Y$ 的点是没有贡献的，剩下的点我们可以容斥一下，变成 $x\le X$ 的部分加上 $y\le Y$ 的部分再减去全体。全体是很容易用线段树维护的，于是我们只需要解决 $x\le X$ 的部分即可，$y\le Y$ 的部分是对称的。同样将修改拆成两条射线，推一下柿子可以得到类似的结论，是关于 $x+y,x$ 以及时间的三维偏序。

然后就 $O(n\log^2 n)$ 做完了。

因为退役了，所以没有代码。