传送门

题意是每个苍蝇有两个属性，a和b，前面的苍蝇要分别和后面的苍蝇决斗，每次的分数为max(ai-aj,bi-bj)-min(ai-aj,bi-bj) (i < j) 。

可以想到

• res = ai – aj – bi + bj (ai – aj > bi – bj)
• -> = (ai – bi) – (aj – bj) (ai – bi > aj – bj)
• 同理，当大小关系相反的时候，是Hj – Hi

所以可以先把 ai – bi 处理出来。

由于是前面的要和所有后面的决斗，所以把数据离线，从后面开始算，每加入一个点，找已经加入的点中，比他大的，比它小的，分别算入答案。

这里可以用离散化+普通权值rmq，也可以用动态开点线段树不用离散化

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 233;
int N;
unordered_map<int,int> ump,raw;
ll a[maxn];
ll c1[maxn], c2[maxn];
void add(int x, int v)
{
    for(; x <= N; x += x & -x) c1[x] += 1, c2[x] += v;
}
ll ask(int x, int &num)
{
    ll res = 0; num = 0;
    for(; x; x -= x & -x) res += c2[x], num += c1[x];
    return res;
}
int main()
{
    int t; cin >> t;
    while(t--)
    {
        int n; cin >> n;
        set<int> st;
        ump.clear(); raw.clear();
        for(int i = 1; i <= n; i++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            a[i] = x - y;
            st.insert(a[i]);
        }
        int cnt = 0;
        for(auto it = st.begin(); it != st.end(); it++)
        {
            ump[*it] = ++cnt;
            raw[cnt] = *it;
        }
        memset(c1, 0, sizeof c1);
        memset(c2, 0, sizeof c2);
        N = cnt;
        ll ans = 0, sum = 0;
        for(int i = n; i >= 1; i--)
        {
            int idx = ump[a[i]];
            int sm = 0, bg = 0;
            ll t = ask(idx - 1, sm);
            ll tt = ask(N, bg);
            //printf("%d %d %d %d\n",t,tt,sm,bg);
            ans += a[i] * sm - t;
            ans += (tt - t) - (bg - sm) * a[i];
            // ans += 2 * (tt - t) - tt;
            //cout << ans << endl;
            add(idx, a[i]);
        }
        cout<<ans<<endl;
    }
}