未知题目来源的问题

学术版

ppip @ 2021-09-25 12:33:07

给定两个长度分别为 n、m，求\sum_{i=1}^n\sum_{j=1}^m|A_i-B_j|\times(i-j)。

by Leap_Frog @ 2021-09-25 12:47:18

绝对值拆开，按照 A_i 和 B_i 大小排序，做两次
应该用树状数组、线段树等数据结构维护即可，具体没没想清楚，但感觉应该可以做

错了勿喷

by 囧仙 @ 2021-09-25 13:14:19

考虑枚举 i。

当 A_i\ge B_j 时，|A_i-B_j|(i-j)=A_ii-B_ji-A_jj+B_jj。那么就是统计不超过 A_i 的 B_j 有多少个、这些 B_j 的和是多少、这些 B_j 分别乘上 j 后的和是多少。显然是可以排序后用 \text{two pointer} 做的。

对于 A_i<B_j 的情况同理。

by Leap_Frog @ 2021-09-25 13:42:57

确实，可以不用数据结构，我 nt 了

by ppip @ 2021-09-26 07:00:03

@囧仙蟹蟹。已AC。