[shitpost] CF1682F

· · 题解

完全不知道这题的题解在说什么？？？？把非常简单的东西搞得看上去很复杂。

注意到 a 是递增的。可以把图想象成这样：中间的边不是直接连 O(n^2) 条，而是在相邻之间连双向边，费用为 (a_i-a_{i-1})。

可以发现这个问题与 [LNOI2022] 盒 完全等价。考虑每条边被经过的次数，立得答案为

\sum_{l\le i<r}(a_{i+1}-a_i)|s_i-s_{l-1}|