题解

Step1：公式分析

先把坐标从小到大排序，记第jj头牛为(vj,xj)(v_j,x_j)。

∑i∈Amax{vi,vj}∣xi−xj∣\sum_{i \in A}max\{ v_i,v_j \}|x_i-x_j|

我们对每个jj，分为两个集合来处理：

A={i<j ∣ vi≤vj},max(vi,vj)=vjB={i<j ∣ vi>vj},max(vi,vj)=viA=\{ i \lt j \space | \space v_i \le v_j \}, max(v_i,v_j)=v_j \\ B=\{ i \lt j \space | \space v_i \gt v_j \}, max(v_i,v_j)=v_i \\

那么每个集合的贡献可拆分为：

=∑i∈Avj(xj−xi)+∑i∈Bvi(xj−xi)=∑i∈Avjxj−∑i∈Avjxi+∑i∈Bvixj−∑i∈Bvixi=vj(∣A∣xj−∑i∈Axi)+xj∑i∈Bvi−∑i∈Bvixi\begin{aligned} =&\sum_{i \in A}v_j(x_j-x_i)+\sum_{i \in B}v_i(x_j-x_i) \\ =&\sum_{i \in A}v_jx_j-\sum_{i \in A}v_jx_i + \sum_{i \in B}v_ix_j-\sum_{i \in B}v_ix_i \\ =&v_j(|A|x_j-\sum_{i \in A}x_i) + x_j\sum_{i \in B}v_i - \sum_{i \in B}v_ix_i \end{aligned}

Step2：树状数组维护

我们分析上式中的四个变量： ∣A∣|A|、∑i∈Axi\sum_{i \in A}x_i、∑i∈Bvi\sum_{i \in B}v_i、∑i∈Bvixi\sum_{i \in B}v_ix_i

从左到右扫描jj时，能够得到：

以强度描vv为索引的前缀： ∣A∣|A|、∑i∈Axi\sum_{i \in A}x_i

以强度描vv为索引的后缀：∑i∈Bvi\sum_{i \in B}v_i、∑i∈Bvixi\sum_{i \in B}v_ix_i

我们构建4颗树状数组维护即可

树状数组：

struct BIT {
    int n;
    vector<ll> t;
    BIT(int n = 0) : n(n), t(n + 1, 0) {}
    void add(int i, ll v) {
        for (; i <= n; i += i & -i)
            t[i] += v;
    }
    ll sum(int i) {
        ll r = 0;
        for (; i > 0; i -= i & -i) {
            r += t[i];
        }
        return r;
    }
};

维护处理：

ll solve() {
    BIT bit_cnt(N), bit_sumx(N), bit_sumv(N), bit_sumvx(N);
    ll ans = 0;
    for (auto [v, x] : a) {
        int idx = v;
        ll cnt_le = bit_cnt.sum(idx);
        ll sumx_le = bit_sumx.sum(idx);
        ll sumv_le = bit_sumv.sum(idx);
        ll sumvx_le = bit_sumvx.sum(idx);
        ll sumv_all = bit_sumv.sum(N);
        ll sumvx_all = bit_sumvx.sum(N);
        ll sumv_gt = sumv_all - sumv_le;
        ll sumvx_gt = sumvx_all - sumvx_le;

        ans += 1ll * v * (cnt_le * x - sumx_le) +
            1ll * x * sumv_gt - sumvx_gt;

        bit_cnt.add(idx, 1);
        bit_sumx.add(idx, x);
        bit_sumv.add(idx, v);
        bit_sumvx.add(idx, 1ll * x * v);
    }
    return ans;
}

完整代码：

时间复杂度：O(NlogN)O(NlogN)

空间复杂度：O(N)O(N)

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e4 + 10;

int n;
vector<pair<int, int>> a;
struct BIT {
    int n;
    vector<ll> t;
    BIT(int n = 0) : n(n), t(n + 1, 0) {}
    void add(int i, ll v) {
        for (; i <= n; i += i & -i)
            t[i] += v;
    }
    ll sum(int i) {
        ll r = 0;
        for (; i > 0; i -= i & -i) {
            r += t[i];
        }
        return r;
    }
};

ll solve() {
    BIT bit_cnt(N), bit_sumx(N), bit_sumv(N), bit_sumvx(N);
    ll ans = 0;
    for (auto [v, x] : a) {
        int idx = v;
        ll cnt_le = bit_cnt.sum(idx);
        ll sumx_le = bit_sumx.sum(idx);
        ll sumv_le = bit_sumv.sum(idx);
        ll sumvx_le = bit_sumvx.sum(idx);
        ll sumv_all = bit_sumv.sum(N);
        ll sumvx_all = bit_sumvx.sum(N);
        ll sumv_gt = sumv_all - sumv_le;
        ll sumvx_gt = sumvx_all - sumvx_le;

        ans += 1ll * v * (cnt_le * x - sumx_le) +
            1ll * x * sumv_gt - sumvx_gt;

        bit_cnt.add(idx, 1);
        bit_sumx.add(idx, x);
        bit_sumv.add(idx, v);
        bit_sumvx.add(idx, 1ll * x * v);
    }

    return ans;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    a.resize(n);
    for (int i = 0; i < n; i ++) {
        cin >> a[i].first >> a[i].second;
    }
    sort(a.begin(), a.end(), [](auto &p, auto &q){
        if (p.second != q.second) {
            return p.second < q.second;
        }
        return p.first < q.first;
    });
    cout << solve() << endl;
    return 0;
}