树状数组

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10, M = 1e6;
struct node{int v,x;}a[N];
int c[2][M+10];
void add(int x,int k,int *cc){for(;x <= M;x +=x&-x)cc[x] += k;}
int getsum(int x,int *cc){
    int res = 0;
    for(;x;x -= x&-x)res += cc[x];
    return res;
}

signed main(){
    int n;scanf("%lld",&n);
    for(int i = 1;i <= n;i ++)scanf("%lld%lld",&a[i].v,&a[i].x);
    sort(a + 1,a + n + 1,[](node x,node y){return x.v < y.v;});
	memset(c,0,sizeof(c));
	int ans = 0,presum=0;
    for(int i = 1;i <= n;i ++){
        int num = getsum(a[i].x,c[0]);
        int sum = getsum(a[i].x,c[1]);
        ans += (num * a[i].x - sum) * a[i].v;//小于它
        ans += ((presum - sum) - (i - num - 1) * a[i].x) * a[i].v;//大于它
        add(a[i].x,1,c[0]);//更新
        add(a[i].x,a[i].x,c[1]);
        presum += a[i].x;//前缀和
    }
    printf("%lld\n",ans);
    return 0;
}

归并排序

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e4+10;
struct node{LL v, x;} a[N], b[N];
LL ans;
bool cmp(node n1, node n2){
    return n1.x>n2.x;
}
void mergesort(int l, int r){
    if(l==r) return ;
    int mid=(l+r)/2;
    mergesort(l, mid); mergesort(mid+1, r);
    int lp=l, rp=mid+1, len=0; LL suml=0, sumr=0;
    for(int i=l; i<=mid; i++)   suml+=a[i].x;
    for(int i=mid+1; i<=r; i++) sumr+=a[i].x;
    while(lp<=mid && rp<=r){
        if(a[lp].v>a[rp].v){
            ans+=a[lp].v*abs((r-rp+1)*a[lp].x-sumr);
            suml-=a[lp].x;
            b[++len]=a[lp++];
        }
        else{
            ans+=a[rp].v*abs(suml-(mid-lp+1)*a[rp].x);
            sumr-=a[rp].x;
            b[++len]=a[rp++];
        }
    }
    while(lp<=mid) b[++len]=a[lp++];
    while(rp<=r)   b[++len]=a[rp++];
    for(int i=l; i<=r; i++) a[i]=b[i-l+1];
}
int main(){
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%lld%lld", &a[i].v, &a[i].x);
    sort(a+1, a+n+1, cmp);
    ans=0; mergesort(1, n);
    printf("%lld\n", ans);
    return 0;
}

树状数组：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+10, M = 1e6;
struct node{int v,x;}a[N];
int c[2][M+10];
void add(int x,int k,int *cc){for(;x <= M;x +=x&-x)cc[x] += k;}
int getsum(int x,int *cc){
int res = 0;
for(;x;x -= x&-x)res += cc[x];
return res;
}

signed main(){ int n;scanf("%lld",&n); for(int i = 1;i <= n;i ++)scanf("%lld%lld",&a[i].v,&a[i].x); sort(a + 1,a + n + 1,[](node x,node y){return x.v < y.v;}); memset(c,0,sizeof(c)); int ans = 0,presum=0; for(int i = 1;i <= n;i ++){ int num = getsum(a[i].x,c[0]); int sum = getsum(a[i].x,c[1]); ans += (num * a[i].x - sum) * a[i].v;//小于它 ans += ((presum - sum) - (i - num - 1) * a[i].x) * a[i].v;//大于它 add(a[i].x,1,c[0]);//更新 add(a[i].x,a[i].x,c[1]); presum += a[i].x;//前缀和 } printf("%lld\n",ans); return 0; }</pre>

归并排序：

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e4+10;
struct node{LL v, x;} a[N], b[N];
LL ans;
bool cmp(node n1, node n2){
return n1.x>n2.x;
}
void mergesort(int l, int r){
if(l==r) return ;
int mid=(l+r)/2;
mergesort(l, mid); mergesort(mid+1, r);
int lp=l, rp=mid+1, len=0; LL suml=0, sumr=0;
for(int i=l; i<=mid; i++)   suml+=a[i].x;
for(int i=mid+1; i<=r; i++) sumr+=a[i].x;
while(lp<=mid && rp<=r){
if(a[lp].v>a[rp].v){
ans+=a[lp].v*abs((r-rp+1)a[lp].x-sumr);
suml-=a[lp].x;
b[++len]=a[lp++];
}
else{
ans+=a[rp].vabs(suml-(mid-lp+1)*a[rp].x);
sumr-=a[rp].x;
b[++len]=a[rp++];
}
}
while(lp<=mid) b[++len]=a[lp++];
while(rp<=r)   b[++len]=a[rp++];
for(int i=l; i<=r; i++) a[i]=b[i-l+1];
}
int main(){
int n; scanf("%d", &n);
for(int i=1; i<=n; i++) scanf("%lld%lld", &a[i].v, &a[i].x);
sort(a+1, a+n+1, cmp);
ans=0; mergesort(1, n);
printf("%lld\n", ans);
return 0;
}