#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; struct node { ll x,h; } Tr[100005]; int n,tr1[100005],tr2[100005]; bool cmp(node s1,node s2) { return s1.x<s2.x; } bool cmp1(node s1,node s2) { return s1.h<s2.h; } int lowbit(int x) { return x&(-x); } void insert(int x,int c,int *s) //s为对应的传递过来的数组 { for(int i=x;i<=n;i+=lowbit(i)) s[i]+=c; } int sum(int x,int *s) { int ans=0; for(int i=x;i;i-=lowbit(i)) ans+=s[i]; return ans; } int main() { while(~scanf("%d",&n)) { for(int i=1; i<=n; i++) scanf("%lld %lld",&Tr[i].x,&Tr[i].h); //按照从小到大的把x顺序排序 sort(Tr+1,Tr+n+1,cmp); //离散化坐标 int ji=Tr[1].x; Tr[1].x=1; for(int i=2; i<=n; i++) { //如果等于前一个，那么排名也一样 if(Tr[i].x==ji) Tr[i].x=Tr[i-1].x; //不相等，说明小于，那么就赋离散化之后的值 else { ji=Tr[i].x; Tr[i].x=i; } } //记录最大的数下边用 int jilu=Tr[n].x; //按照高度从小到大进行排序 sort(Tr+1,Tr+n+1,cmp1); //离散化高度 ji=Tr[1].h; Tr[1].h=1; for(int i=2; i<=n; i++) { if(Tr[i].h==ji) Tr[i].h=Tr[i-1].h; else { ji=Tr[i].h; Tr[i].h=i; } } ll ans=0; //第三次进行排序 //按高度排序 sort(Tr+1,Tr+n+1,cmp1); memset(tr1,0,sizeof tr1); memset(tr2,0,sizeof tr2); for(int i=1; i<=n; i++) { //记录所有比这个数小的和 insert(Tr[i].x,Tr[i].x,tr1); //记录所有比这个数小的个数 每个点上记为1 insert(Tr[i].x,1,tr2); } //xiao表示比对应坐标小 int xiao; //da表示比对应坐标大 int da; for(int i=1; i<n; i++) { //找出比这个数小的个数*这个数-比这个数小的所有数之和 //相当于：当前这个数分别减去比他小的 xiao=sum(Tr[i].x-1,tr2)*Tr[i].x-sum(Tr[i].x-1,tr1); //找出比这个数大的数的和-这个数*比这个数大的个数 da=(sum(jilu,tr1)-sum(Tr[i].x,tr1))-(sum(jilu,tr2)-sum(Tr[i].x,tr2))*Tr[i].x; //高度取小 此时是按高度排序的 //坐标取差 ans+=(xiao+da)*Tr[i].h; //把这个用过的数从删除 insert(Tr[i].x,-Tr[i].x,tr1); //把这个数位置上减去1 insert(Tr[i].x,-1,tr2); } printf("%lld ",ans); } return 0; }