都是一类题目，推导调试比较烦，想出来还是不难的
/* 给定n个点对，按一维升序排序一次,每个点的序号为Di，按二维升序排序一次，每个点的序号为Hi 求sum{w(i,j)} w(i,j)=abs(Di-Dj)*min(Hi-Hj) 那么将所有的点按照H升序排列，两个树状数组，一个维护区间d的个数，一个维护区间d的总和 每个点的贡献值=树状数组中D小于其的+D大于其的abs 按升序遍历每个点后，将该点在树状数组中删掉 */ #include<bits/stdc++.h> using namespace std; #define ll long long #define maxn 100005 struct node { ll a,b;//x坐标，高度 int num1,num2;//D,H }t[maxn]; int n; ll bitc[maxn],bitd[maxn]; int cmpa(node x,node y){return x.a<y.a;} int cmpb(node x,node y){return x.b<y.b;} int cmpc(node x,node y){return x.num2<y.num2;} void add1(int x,int num){ for(int i=x;i<=100000;i+=i&-i) bitc[i]+=num; } void add2(int x,int num){ for(int i=x;i<=100000;i+=i&-i) bitd[i]+=num; } ll query1(int x){ ll res=0; for(int i=x;i;i-=i&-i) res+=bitc[i]; return res; } ll query2(int x){ ll res=0; for(int i=x;i;i-=i&-i) res+=bitd[i]; return res; } int main(){ while(scanf("%d",&n)==1){ memset(bitc,0,sizeof bitc); memset(bitd,0,sizeof bitd); for(int i=1;i<=n;i++) scanf("%lld%lld",&t[i].a,&t[i].b); sort(t+1,t+1+n,cmpa);//按x坐标升序排列 for(int i=1;i<=n;i++){ if(i==1) t[i].num1=i; else if(t[i].a==t[i-1].a) t[i].num1=t[i-1].num1; else t[i].num1=i; } int max=t[n].num1; sort(t+1,t+1+n,cmpb);//按高度升序排列 for(int i=1;i<=n;i++){ if(i==1) t[i].num2=i; else if(t[i].b==t[i-1].b) t[i].num2=t[i-1].num2; else t[i].num2=i; } sort(t+1,t+1+n,cmpc);//按照h升序排列 for(int i=1;i<=n;i++){add1(t[i].num1,1);add2(t[i].num1,t[i].num1);} ll ans=0; for(int i=1;i<n;i++){//最后一个点没有贡献度 ll tmp1=query1(t[i].num1-1);//第i个点严格左边的 ll tmp2=query2(t[i].num1-1); ll tmp3=query1(t[i].num1); ll tmp4=query2(t[i].num1); ans+=t[i].num2*(t[i].num1*tmp1-tmp2); ans+=t[i].num2*(query2(max+1)-tmp4-t[i].num1*(query1(max+1)-tmp3));// add1(t[i].num1,-1); add2(t[i].num1,-t[i].num1); } printf("%lld ",ans); } }