赤石大王

· · 题解

每次修改操作可以用 d 次矩形加刻画：先将与 (x,y) 切比雪夫距离 <d 的点加 w，再将切比雪夫距离 <d-1 的点再次加 w，以此类推，即做一个回字形加法。

一次考虑每次矩形加，通过二阶差分可以使单次矩形加的修改位置数量变成 \mathcal{O}(1)，手模之后可以发现相当于让 (x_1,y_1) 和 (x_2+1,y_2+1) 位置加 w，让 (x_2+1,y_1) 和 (x_1,y_2+1) 位置减 w，其中 (x_1,y_1) 和 (x_2,y_2) 分别表示矩形的左下角和右上角。

那么整个回字形的加法在二阶差分下就相当于让 (x-d+1,y-d+1) 到 (x+d,y+d) 这条主对角线加上 w，(x+d,y-d+1) 到 (x-d+1,y+d) 这条副对角线减去 w。

主对角线

考虑每条主对角线加法再次差分变成两条射线加，每条射线的限制形如：对满足 a-b=d 且 a>x_0 的所有点 (a,b) 加上 w。

查询的 4-side 矩形先转化为 4 个 2-side 矩形，然后考虑每个射线的修改对一个 2-side 矩形 (X,Y) 的贡献。

不妨假设这条射线优先碰到 2-side 矩形 x=X 这条边。

显然需要满足修改在查询之前且 x_0<X，由于需要先碰到 x=X 这条边，所以还需要满足 X-Y\le d，三维偏序直接上 cdq 即可。

造成的贡献不难写出是 \displaystyle\sum_{i=x_0+1}^{X}w(X-i+1)(Y-(i-d)+1)，为了方便令 X+1\to X,Y+1\to Y，从而改写为 \displaystyle\sum_{i=x_0+1}^{X-1}w(X-i)(Y-(i-d))。

尝试直接展开：

\begin{align*} \displaystyle\sum_{i=x_0+1}^{X-1}w(X-i)(Y-(i-d)) \\ &=wX(Y+d)(X-1-x_0)-w(X+Y)\displaystyle\sum_{i=x_0+1}^{X-1}i-wd\displaystyle\sum_{i=x_0+1}^{X-1}i+w\displaystyle\sum_{i=x_0+1}^{X-1}i^2 \\ &=wX(Y+d)(X-1-x_0)-w(X+Y)(F_{1,X-1}-F_{1,x_0})-wd(F_{1,X-1}-F_{1,x_0})+w(F_{2,X-1}-F_{2,x_0}) \end{align*}

其中 F_{1,j}=\displaystyle\sum_{i=1}^{j}i,F_{2,j}=\displaystyle\sum_{i=1}^{j}i^2。

不难发现对于展开式需要维护 \sum w,\sum w\times x_0,\sum w\times d,\sum w\times d\times x_0,\sum w\times F_{1,x_0},\sum w\times d\times F_{1,x_0},\sum w\times F_{2,x_0}，开 7 个 BIT 即可。

对于先碰到 y=Y 这条线的情况，不难证明可以通过交换所有点的横纵坐标转化为刚才的问题。

副对角线

同理对副对角线的修改差分为：对满足 a+b=d 且 b>y_0 的所有点 (a,b) 加上 w。

发现一个射线的修改对一个 2-side 矩形能够贡献的形式有 2 种：

第一种情况（射线 FG）需要满足 d-X\le y_0\le Y 且 d\le X+Y，此时贡献为 \displaystyle\sum_{i=y_0+1}^{Y}w(X-(d-i)+1)(Y-i+1)，同理变形 \displaystyle\sum_{i=y_0+1}^{Y-1}w(X-(d-i))(Y-i)。

继续推式子不难得到：

wY(X-d)(Y-1-y_0)+w(Y-X)(F_{1,Y-1}-F_{1,y_0})+wd(F_{1,Y-1}-F_{1,y_0})-w(F_{2,Y-1}-F_{2,y_0})

同理继续上 7 个 BIT。

原限制是一个四维偏序，但是可以转化为 y_0\le Y 的答案减去 y_0<d-X 即 y_0-d<-X 的答案，就是两个三维偏序了。

第二种情况（射线 DE）的贡献是好算的，容易求出有封闭形式 \frac{w(D-d+3)(D-d+2)(D-d+1)}{6}，其中 D=X+Y，且满足限制 d\le D,y_0-d<-X。

所有分式在模 2^{30} 下均不好算，于是考虑 (a\times c)\bmod(b\times c)=(a\bmod b)\times c，所以将所有的贡献在计算时乘 4，即变为 unsigned 自然溢出，那么 F_1=2x(x+1),F_2=\frac{2x(x+1)(2x+1)}{3},\frac{w(D-d+3)(D-d+2)(D-d+1)}{6}\to\frac{2w(D-d+3)(D-d+2)(D-d+1)}{3}，此时 3 在模 2^{32} 意义下存在逆元。

最后在输出的时候把 4 除回来即可。

推导 \frac{2w(D-d+3)(D-d+2)(D-d+1)}{3}，得到：

\frac{2w}{3}\times(D^3-D^2(3d-6)+D(3d^2-12d+11)-(d-3)(d-2)(d-1))

仍然使用 BIT 维护即可。

复杂度 \mathcal{O}(m\log^2m)。

Submission.

代码中在维护分母 3 的时候做麻烦了，但是问题不大。