ABC351E

E - Jump Distance Sum

题意简述

Just it.

思路

兔子斜着走->国际象棋里的象->黑象只能到达黑格，白象只能到达白格（横纵坐标相加的奇偶性）。

将点分成两组，则每组内的点之间都有答案。

可以发现可以先朝着那个方向斜着走，然后超出的部分向着那个方向迂回是最优的。如图

不难发现距离是 \(\max(x_1-x_2,y_1-y_2)\)，这就是切比雪夫距离。

根据公式转曼哈顿：\(x_1'=(x_1+x_2)\div2,x_2'=(x_1-x_2)\div2\)。

可以把所有距离 \(\times 2\)，最后把 \(ans\div2\)，这样就不会出现小数了，即 \(x_1'=x_1+x_2,x_2'=x_1-x_2\)。

我们需要求的就是每组内部两两之间的曼哈顿距离的总和。

横纵坐标独立，直接拆掉。

贡献没有顺序，可以排序，去掉绝对值。

然后如：\(1,2,3,4,5\)。

\(2-1\)

\(3-1+3-2\)

\(4-1+4-2+4-3\)

\(5-1+5-2+5-3+5-4\)

不难发现对于第 \(i\) 个数，记前 \(i-1\) 个数的和为 \(sum\)，答案为 \(x_i\times(i-1)-sum\)，\(sum\) 用前缀和维护即可。

\(O(n\log n)\)。

https://atcoder.jp/contests/abc351/submissions/52980476