【USACO04OPEN】MooFest G

题目链接

按$x_i$排序，再扫描线一刷，每次统计左侧的所有影响，即求：$$sum_{i=1}^n sum _{j=1}^i max{v_i,v_j} imes(x_i-x_j)$$

分类讨论一下，当$v_ige v_j$时，累加$v_i imes x_i-v_i imes x_j$；当$v_i<v_j$时，累加$v_j imes x_i-v_j imes x_j$。

发现可以用树状数组帮助计算，即在扫描的过程中不断更新：$v_j,x_j,v_j imes x_j,1$关于$v_j$的前缀和$q_v,q_x,q_{vx},q_c$，以及$v_j,v_j imes x_j$的总和$s_v,s_{vx}$。

那么，每次移动$i$，答案会增长$v_i imes x_i imes q_c-v_i imes q_x+x_i imes(s_v-q_v)-(s_{vx}-q_{vx})$

程序（100分）：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<set>
#define IL inline
#define RG register
#define _1 first
#define _2 second
using namespace std;
typedef long long LL;
const int N=2e4;

    int n,ri[N+3];
    LL v[N+3],x[N+3],tv[N+3],tx[N+3];
    
IL bool cmp(int i,int j){
    return x[i]<x[j];
}
    
IL void init(){
    for(int i=1;i<=n;i++)
        ri[i]=i;
    sort(ri+1,ri+n+1,cmp);
    
    memcpy(tv,v,sizeof v);
    memcpy(tx,x,sizeof x);
    for(int i=1;i<=n;i++){
        x[i]=tx[ri[i]];    v[i]=tv[ri[i]];
    }
    
}

    LL vs[N+3],xs[N+3],vxs[N+3],cs[N+3];
    
IL int lowbit(int x){
    return x&(-x);
}

IL void mdf(LL *s,int p,LL x){
    for(;p<=N;p+=lowbit(p))
        s[p]+=x;
}

IL LL qry(LL *s,int p){
    LL ret=0;
    for(;p;p-=lowbit(p))
        ret+=s[p];
    return ret;
}

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&v[i],&x[i]);
        
    init();
    
    memset(vs,0,sizeof vs);
    memset(xs,0,sizeof xs);
    memset(vxs,0,sizeof vxs);
    memset(cs,0,sizeof cs);
    LL ans=0,vxsum=0,vsum=0;
    for(int i=1;i<=n;i++){
        vxsum+=v[i]*x[i];
        vsum+=v[i];
        mdf(vs,v[i],v[i]);
        mdf(xs,v[i],x[i]);
        mdf(vxs,v[i],v[i]*x[i]);
        mdf(cs,v[i],1);
        
        ans+=x[i]*(vsum-qry(vs,v[i]))-(vxsum-qry(vxs,v[i]));
        ans+=qry(cs,v[i])*v[i]*x[i]-v[i]*qry(xs,v[i]);
        
    }
    
    printf("%lld",ans);

    return 0;

}