首先观察式子:
\[\sum_{i=1}^{n} \sum_{j=i}^{n} \max\{ i,j \} - \min\{i,j\} = \frac{ \sum_{i=1}^{n} \sum_{j=1}^{n} \max\{i,j\} - \min\{i,j\} }{2} = \frac{ \sum_{i=1}^{n} \sum_{j=1}^{i} \max\{i,j\} - \sum_{i=1}^{n} \sum_{j=1}^{n} \min\{i,j\} }{2}
\]
起初我并没有想到后面这个式子,于是考虑从小到大添加点,但发现记录最小值路径之和答案不可做。
遇到类似于极差这种式子中有最大 and 最小值时看看能否分开考虑,因为这样会让问题变得不严格
因此我们既然要分别计算 \(\sum_{i=1}^{n} \sum_{j=1}^{i} \max\{i,j\}\) 和 \(\sum_{i=1}^{n} \sum_{j=1}^{i} \min\{i,j\}\) ,问题就比较简单了。以求 \(\max\) 距离,值从小到大加点,加入点后包含这个点的路径最大值一定是这个点。找连通块用并查集。 \(\min\) 的计算同理
复杂度 \(O(n \alpha(n))\)