PROG-1109: คู่ตัวเลขเด่น (Pair)

#include <bits/stdc++.h>

using namespace std;

using lli = long long;
using pll = pair <lli, lli>;
const int N = 2*(1<<18);
int n;
lli mx = 0;
pll ab[100010];
pll tree[N];// sum, cnt

pll update(int idx, lli l, lli r, lli pos, lli add){
    if(l == r) return tree[idx] = make_pair(add, 1);
    lli mid = (l + r)/ 2;
    if(pos <= mid){
        pll upd = update(2*idx, l, mid, pos, add);
        return tree[idx] = make_pair(upd.first + tree[2*idx+1].first, upd.second + tree[2*idx+1].second);
    }
    pll upd = update(2*idx+1, mid+1, r, pos, add);
    return tree[idx] = make_pair(tree[2*idx].first + upd.first, tree[2*idx].second + upd.second);
}

pll query(int idx, lli l, lli r, lli s, lli e){
    if(r < s or l > e) return make_pair(0, 0);
    if(s <= l and r <= e) return tree[idx];
    lli mid = (l + r)/ 2;
    pll Left = query(2*idx, l, mid, s, e);
    pll Right = query(2*idx+1, mid+1, r, s, e);
    return make_pair(Left.first + Right.first, Left.second + Right.second);
}

int main(){

    scanf("%d", &n);

    for(int i=1;i<=n;i++){
        lli a, b;
        scanf("%lld%lld", &a, &b);
        ab[i] = make_pair(a, b);
        mx = max(mx, b);
    }

    sort(ab + 1, ab + n + 1, greater <pll> ());

    lli sum = 0;
    for(int i=1;i<=n;i++){
        pll x = query(1, 1, mx, 1, ab[i].second-1);
        if(x.second > 0) sum += (lli) x.first + (ab[i].first * x.second);
        update(1, 1, mx, ab[i].second, ab[i].first);
    }

    printf("%lld", sum);

    return 0;
}