出生点 题解
littleKtian
·
·
题解
考虑容斥。
于是只要求 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\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] 就是我们要求的，按顺序直接扫一遍即可。
复杂度 $O(k\log k)$。
（上面式子化到不同的程度就对应相应的部分分了）