标签：limits min sum arc158e solution mid 玩意 短路

[ARC158E] All Pair Shortest Paths

还是挺牛逼的一题。但是为什么其他题解都说很板？看来还是我太菜了，见的题太少了。

主要参考 @TeneryTree

首先考虑 CDQ 分治，只考虑处理 \([l,mid]\) 中的到 \([mid+1,r]\) 这些点的路径和。

由于列数 \(m=2\) 所以我们考虑设 \(f_{i,0/1}\) 为左边的点 \((i,0/1)\) 到 \((mid,0)\) 的最短路距离，右边的点 \((i,0/1)\) 到 \((mid+1,0)\) 的最短路距离。设 \(g_{i,0/1}\) 为左边的点 \((i,0/1)\) 到 \((mid,1)\) 的最短路距离，右边的点 \((i,0/1)\) 到 \((mid+1,1)\) 的最短路距离。显然这两玩意每次直接 \(O(n)\) 递推即可。

然后考虑一下跨区间的贡献是什么。设贡献为 \(w\) 则有：

\[w = 2\sum\limits_{i=l}\limits^{mid}\sum\limits_{j=mid+1}\limits^{r} \min ( f_{i,0/1} + f_{j,0/1},g_{i,0/1} + g_{j,0/1}) \]

这玩意看着好像不太好直接计算。也不太知道怎么想到的，考虑这样子做：

\[w = 2\sum\limits_{i=l}\limits^{mid}\sum\limits_{j=mid+1}\limits^{r} \{ \min ( f_{i,0/1} + f_{j,0/1} - g_{i,0/1}- g_{j,0/1},0) + g_{i,0/1} + g_{j,0/1} \} \]

然后拎出去!

\[w = 2\sum\limits_{i=l}\limits^{mid}\sum\limits_{j=mid+1}\limits^{r} \{ \min ( f_{i,0/1} + f_{j,0/1} - g_{i,0/1}- g_{j,0/1},0)\} + 4\sum\limits_{i=l}\limits^{mid}g_{i,0/1}\cdot(r-mid) + 4\sum\limits_{i=mid+1}\limits^{r}g_{i,0/1}\cdot(mid-l+1) \]

现在这个式子好看多了qwq。后面那一整串直接计算即可了。而前面那一串取值也只有两种情况，非常好搞。设前面那一串值为 \(2w_2\)，一下省略 0/1 这一维。设 \(p_i = f_i - g_i\) 则有：

\[w_2 = \sum\limits_{i=l}\limits^{mid}\sum\limits_{j=mid+1}\limits^{r} \min (p_i+p_j,0) \]

\[= \sum\limits_{i=l}\limits^{mid}\sum\limits_{j=mid+1}\limits^{r}(p_i+p_j)[p_i>-p_j] \]

这玩意相当好弄，只需要排序二分一下做完了。

总的复杂度 \(O(n\log^2n)\)

code

标签：limits,min,sum,arc158e,solution,mid,玩意,短路
From： https://www.cnblogs.com/WRuperD/p/17988284