POJ

题目的数学模型：求，和号：|Xi-Xj|*max(Vi,Vj)，i != j.

按照大小顺序枚举可以处理取max的问题，假如从小到大枚举到Vi，对另外一部分，

X<Xi且V≤Vi的可以求和(sumX)一起处理，只要维护满足有多少个(cnt)，

这部分是Vi*（Xi*cnt sum-X）。由条件X<Xi，可知sumX是一个前缀和，而另一个条件V小于等于Vi，

只要从小到大的枚举时候更新就好了。总的来说就是，BIT维护两个值sumX和cnt。

对于X>Xi的情况，维护一下总和减一减。

#include<cstdio>
#include<iostream>
#include<string>
#include<cstring>
#include<queue>
#include<vector>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<cmath>
#include<numeric>
using namespace std;

typedef long long ll;

const int MAX_N = 2e4;

typedef pair<int,int> pii;
pii dat[MAX_N];
#define vol first
#define pos second
#define sum first
#define cnt second

pii C[MAX_N+1]; //x coordinate O(2e4*2e4) , x number

int N, X;

void add(int x)
{
    int d = x;
    while(x <= X){
        C[x].sum += d;
        C[x].cnt++;
        x += x&-x;
    }
}

pii prefix(int x)
{
    pii re(0,0);
    while(x>0){
        re.sum += C[x].sum;
        re.cnt += C[x].cnt;
        x &= x-1;
    }
    return re;
}



//#define LOCAL
int main()
{
#ifdef LOCAL
    freopen("in.txt","r",stdin);
#endif
    scanf("%d",&N);
    for(int i = 0; i < N; i++){
        scanf("%d%d",&dat[i].vol,&dat[i].pos);
        X = max(X, dat[i].pos);
    }
    sort(dat,dat+N);
    long long ans = 0;
    int tot = 0;
    for(int i = 0; i < N; i++) {
        pii prv = prefix(dat[i].pos);
        ans += (ll)dat[i].vol*((dat[i].pos*prv.cnt - prv.sum) + ((tot-prv.sum) - dat[i].pos*(i-prv.cnt)));
        add(dat[i].pos);
        tot += dat[i].pos;
    }
    printf("%I64d
", ans);
    return 0;
}