自动搬运

查看原文

来自洛谷，原作者为

	littleKtian MoVe yoUR BoDy

搬运于2025-08-24 22:23:08，当前版本为作者最后更新于2020-06-07 15:07:35，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

考虑容斥。

于是只要求 $m^2\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}(j-i)+n^2\sum\limits_{i=1}^{m-1}\sum\limits_{j=i+1}^{m}(j-i)-\sum\limits_{i=1}^k\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}(\left|x_i-x\right|+\left|y_i-y\right|)+\sum\limits_{i=1}^{k-1}\sum\limits_{j=i+1}^{k}(\left|x_i-x_j\right|+\left|y_i-y_j\right|)$ 即可。

md怎么这么复杂。

考虑将上面式子分成三部分。

• $m^2\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}(j-i)+n^2\sum\limits_{i=1}^{m-1}\sum\limits_{j=i+1}^{m}(j-i)$

上面式子是将行与列的贡献分开来单独计算的。

考虑改变枚举顺序，变成先枚举 $j-i$。

$\begin{aligned}m^2\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^{n}(j-i)+n^2\sum\limits_{i=1}^{m-1}\sum\limits_{j=i+1}^{m}(j-i)&=m^2\sum\limits_{i=1}^{n-1}i\times(n-i)+n^2\sum\limits_{i=1}^{m-1}i\times(m-i)\\&=m^2n\sum\limits_{i=1}^{n-1}i-m^2\sum\limits_{i=1}^{n-1}i^2+n^2m\sum\limits_{i=1}^{m-1}i-n^2\sum\limits_{i=1}^{m-1}i^2\end{aligned}$

$\sum i$ 跟 $\sum i^2$ 可以直接代公式 $O(1)$ 求出。

（如果你不知道的话我可以告诉你 $\sum\limits_{i=1}^{n}i=\dfrac{n(n+1)}{2},\sum\limits_{i=1}^{n}i^2=\dfrac{n(n+1)(2n+1)}{6}$）

当然如果你想式子好看一些可以将上面的 $\sum\limits_{i=1}^{n-1}$ 和 $\sum\limits_{i=1}^{m-1}$ 都换成$\sum\limits_{i=1}^{n}$ 和 $\sum\limits_{i=1}^{m}$，反正都会被消掉对答案无影响。

• $\sum\limits_{i=1}^k\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}(\left|x_i-x\right|+\left|y_i-y\right|)$

同样我们将行与列的贡献分开来计算。

$\begin{aligned}\sum\limits_{i=1}^k\sum\limits_{x=1}^{n}\sum\limits_{y=1}^{m}(\left|x_i-x\right|+\left|y_i-y\right|)&=\sum\limits_{i=1}^{k}(m\sum\limits_{x=1}^{n}\left|x_i-x\right|+n\sum\limits_{x=1}^{m}\left|y_i-y\right|)\\&=\sum\limits_{i=1}^{k}(m\sum\limits_{x=1}^{x_i-1}(x_i-x)+m\sum\limits_{x=x_i+1}^{n}(x-x_i)+n\sum\limits_{y=1}^{y_i-1}(y_i-y)+n\sum\limits_{y=y_i+1}^{m}(y-y_i))\end{aligned}$

同样直接 $\sum i$ 公式代进去即可。

• $\sum\limits_{i=1}^{k-1}\sum\limits_{j=i+1}^{k}(\left|x_i-x_j\right|+\left|y_i-y_j\right|)$

依然将行与列的贡献分开来计算。

$\sum\limits_{i=1}^{k-1}\sum\limits_{j=i+1}^{k}(\left|x_i-x_j\right|+\left|y_i-y_j\right|)=\sum\limits_{i=1}^{k-1}\sum\limits_{j=i+1}^{k}\left|x_i-x_j\right|+\sum\limits_{i=1}^{k-1}\sum\limits_{j=i+1}^{k}\left|y_i-y_j\right|$

考虑求 $\sum\limits_{i=1}^{k-1}\sum\limits_{j=i+1}^{k}\left|x_i-x_j\right|$。

将所有障碍点按 $x_i$ 从小到大排序。

$\sum\limits_{i=1}^{k-1}\sum\limits_{j=i+1}^{k}\left|x_i-x_j\right|=\sum\limits_{i=2}^{k}\sum\limits_{j=1}^{i-1}(x_i-x_j)$

（注意两条式子的枚举顺序）

设 $f[k]=\sum\limits_{i=1}^{k-1}(x_k-x_i),f[1]=0$。

容易发现 $f[k+1]=f[k]+k\times(x_{k+1}-x_k)$。

而 $\sum\limits_{i=1}^{k}f[i]$ 就是我们要求的，按顺序直接扫一遍即可。

$\sum\limits_{i=1}^{k-1}\sum\limits_{j=i+1}^{k}\left|y_i-y_j\right|$ 用同样的方式解决即可。

复杂度 $O(k\log k)$。

（上面式子化到不同的程度就对应相应的部分分了）