题解 P8259【[CTS2022] 回】

· · 题解

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

然后这个查询我们给他拆成四个二维前缀和，然后考虑算贡献。对于一个修改 (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 可以看到，需要的东西都形如 $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)$ 做完了。 因为退役了，所以没有代码。