M.Short Question

  题意:求\(\sum\limits_{i = 1} ^ {n}\sum\limits_{j = 1}^{n} \min\left(\left|p_i - p_j\right|, \left|q_i-q_j\right|\right)\)的值
  首先带上绝对值来计算不太方便，所以对原有的序列\(p,q\)都先排个序,这样就可以直接拿掉绝对值并且转化为求\(2 × \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{i - 1}\left(a_i - a_j\right)\),我们将这个式子先展开为\(2×\sum\limits_{i = 1}^{n}\left(\left(i - 1\right)×a_i - \sum\limits_{j = 1}^{i - 1}a_j\right) \Rightarrow 2×\left(\sum\limits_{i = 1}^{n}\left(i - 1\right)×a_i - \sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{i - 1}a_j\right)\), 将\(\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{i - 1}a_j\)展开，会得到\(\left(n - 1\right)a_1 + \left(n - 2\right)×a_2 \dots + \left(n - i\right)×a_i + \dots + \left(n - n\right)a_n\),也就是\(\sum\limits_{i = 1}^{n} \left(n - i\right)a_i\),所以原式可以合并为\(2×\sum\limits_{i = 1}^{n}\left(\left(i - 1\right)a_i - (n - i)a_i\right) \Rightarrow 2×\sum\limits_{i = 1}^{n}\left(2×i - n - 1\right)×a_i\),这样就将复杂的两个求和符号和绝对值转化成了只有一个线性的求和。

    auto calc = [&](std::vector<i64>& x) -> i64 {
        i64 ans = 0;
        rep(i,0,n) {
            ans += (2LL * i - n + 1) * x[i];
        }
        return ans * 2LL;
    };

  那么现在就需要去考虑\(\min\left(p_i - p_j, q_i - q_j\right)\)该怎么转化了.
  很显然有一个恒等式\(\min\left(a, b\right) \Leftrightarrow a + b - \max\left(a,b\right)\),也就将\(\min\left(p_i - p_j, q_i - q_j\right)\)转化成了\(p_i + q_j - p_j - q_j - \max\left(p_i - p_j, q_i - q_j\right)\)这里的\(\max\left(p_i - p_j, q_i - q_j\right)\)要将它看成是一个\(\left(p_i, q_i\right),\left(p_j, q_j\right)\)之间的切比雪夫距离,而切比雪夫距离和曼哈顿距离的转化关系是这样的

将曼哈顿距离转化为切比雪夫距离: \(A\left(x, y\right) \rightarrow A^{'}\left(x + y, x - y\right)或A^{'}\left(x - y, x + y\right)\)
将切比雪夫距离转化为曼哈顿距离: \(A\left(x, y\right) \rightarrow A^{'}\left(\frac{x + y}{2}, \frac{x - y}{2}\right)或A^{'}\left(\frac{x - y}{2}, \frac{x + y}{2}\right)\)

证明：切比雪夫距离和曼哈顿距离的转化及证明
  有了这个结论，那么就可以将\(\left(p_i - p_j, q_i - q_j\right)\)映射成\(\left(\frac{p_i - p_j + q_i - q_j}{2},\frac{p_i - p_j - q_i + q_j}{2}\right)到\left(0,0\right)\)的曼哈顿距离，也就是将\(\max\left(p_i - p_j, q_i - q_j\right)\)转化成\(\frac{\left|p_i + q_i - p_j - q_j\right| + \left|p_i - q_i - p_j + q_j\right|}{2}\), 此时可以将\(a_i = p_i + q_i, b_i = p_i - q_i\),简化为\(\frac{\left|a_i - a_j\right| + \left|b_i - b_j\right|}{2}\)
  这样就把原问题转化成了\(2×\sum\limits_{i = 1}^{n}\left(2×i - n - 1\right)×\left(p_i + q_i - \frac{1}{2}×\left(a_i + b_i\right)\right)\)

    int n; std::cin >> n;
    std::vector<i64> a(n), b(n), p(n), q(n);
    for (auto& x : p) std::cin >> x;
    for (auto& x : q) std::cin >> x;
    rep(i,0,n) a[i] = p[i] + q[i], b[i] = p[i] - q[i];
    
    std::sort(all(a)), std::sort(all(b)), std::sort(all(p)), std::sort(all(q));

    auto calc = [&](std::vector<i64>& x) -> i64 {
        i64 ans = 0;
        rep(i,0,n) {
            ans += (2LL * i - n + 1) * x[i];
        }
        return ans * 2LL;
    };

    std::cout << calc(p) + calc(q) - (calc(a) + calc(b)) / 2 << "\n";