题意：给你n棵树，每棵树上有两个权值X H
对于X离散化 ：3 7 1 5 3 6 -> 2 6 1 4 2 5,对于H一样
然后F = abs(X1-X2) S=min(H1,H2)
求出每一对F*S的总和
可以看到一边是求每个数与其他数的最小值，一边是求每个数与其他数的差距。因此我们可以排序一边，处理另一边。
我们排序H，因为这样对于固定一个Xi Hi，从小到大每次都是Hi去乘以Xi与剩下的所有X的差的总和。
这样我们就可以使用树状数组维护两个值：每个位置值的个数，每个位置值的总大小，接着细心点处理就好了
#include<set>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<string>
#include<cstdio>
#include<cstring>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define eps 1E-8
/*注意可能会有输出-0.000*/
#define Sgn(x) (x<-eps? -1 :x<eps? 0:1)//x为两个浮点数差的比较,注意返回整型
#define Cvs(x) (x > 0.0 ? x+eps : x-eps)//浮点数转化
#define zero(x) (((x)>0?(x):-(x))<eps)//判断是否等于0
#define mul(a,b) (a<<b)
#define dir(a,b) (a>>b)
typedef long long ll;
typedef unsigned long long ull;
const int Inf=<<;
const double Pi=acos(-1.0);
const int Mod=1e9+;
const int Max=;
struct node
{
int sub,minx;
} tree[Max];
int n;
bool cmpt(struct node p1,struct node p2)
{
return p1.sub<p2.sub;
}
bool cmp(struct node p1,struct node p2)
{
return p1.minx<p2.minx;//按照最值排序才能固定一个值
}
int lowbit(int x)
{
return x&(-x);
}
void Add(ll *bit,int x,ll y)
{
while(x<=n)
{
bit[x]+=y;
x+=lowbit(x);
}
return;
}
ll Sum(ll *bit,int x)
{
ll sum=0ll;
while(x)
{
sum+=bit[x];
x-=lowbit(x);
}
return sum;
}
ll bit[Max],bit2[Max];//存个数 存大小
ll Solve()
{
ll ans=0ll;
memset(bit,0ll,sizeof(bit));
memset(bit2,0ll,sizeof(bit2));
for(int i=;i<n;++i)
{
Add(bit2,tree[i].sub,(ll)tree[i].sub);
Add(bit,tree[i].sub,1ll);
}
for(int i=;i<n;++i)
{
Add(bit2,tree[i].sub,(ll)-tree[i].sub);
Add(bit,tree[i].sub,-1ll);
// printf("%d\n",tree[i].sub);
ans+=(ll)tree[i].minx*(
Sum(bit2,n)-Sum(bit2,tree[i].sub)-(ll)tree[i].sub*(Sum(bit,n)-Sum(bit,tree[i].sub))+
(ll)tree[i].sub*Sum(bit,tree[i].sub)-Sum(bit2,tree[i].sub));//关键
//printf("%I64d %I64d\n",ans,Sum(bit2,n)-Sum(bit,n)*tree[i].sub);
}
return ans;
}
int main()
{
int tmp;
while(~scanf("%d",&n))
{
for(int i=; i<n; ++i)
scanf("%d %d",&tree[i].sub,&tree[i].minx);
sort(tree,tree+n,cmpt);//离散化
tree[n].sub=tree[n].minx=-;
tmp=;
for(int i=; i<n; ++i)
{
if(tree[i].sub!=tree[i+].sub)
{
tree[i].sub=tmp;
tmp=i+;
}
else
{
tree[i].sub=tmp;
}
}
sort(tree,tree+n,cmp);
tmp=;
for(int i=; i<n; ++i)
{
if(tree[i].minx!=tree[i+].minx)
{
tree[i].minx=tmp;
tmp=i+;
}
else
{
tree[i].minx=tmp;
}
}
// for(int i=0;i<n;++i)
// printf("%d %d\n",tree[i].sub,tree[i].minx);
printf("%I64d\n",Solve());
}
return ;
}