题意：给出n棵树，给出横坐标x，还有它们的高度h，先按照横坐标排序，则它们的横坐标记为xx,
再按照它们的高度排序，记为hh
两颗树的差异度为 abs(xx[i] - xx[j]) * min(hh[i],hh[j])，求所有的差异度的和
和上面一道题一样，只不过这题是要Min的值，就将h从大到小排序，保证每一个h都是当前最小的
然后维护比当前x小的坐标的个数，当前区间的总和，前面比x小的坐标的和
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 typedef long long LL; 14 const int INF = (1<<30)-1; 15 const int mod=1000000007; 16 const int maxn=100005; 17 18 int n; 19 struct node{ int x,xx,h,hh,id;}; 20 21 node a[maxn],b[maxn],q[maxn]; 22 int c[maxn],d[maxn]; 23 int s[maxn]; 24 25 int cmp1(node n1,node n2){ return n1.x < n2.x; } 26 int cmp2(node n1,node n2){ return n1.h < n2.h;} 27 int cmp3(node n1,node n2){ return n1.h > n2.h;} 28 29 int lowbit(int x){ return x & (-x);} 30 31 LL sum(int c[],int x){ 32 LL ret=0; 33 while(x>0){ 34 ret+=c[x]; x-=lowbit(x); 35 } 36 return ret; 37 } 38 39 void add(int c[],int x,int d){ 40 while(x < maxn){ 41 c[x]+=d;x+=lowbit(x); 42 } 43 } 44 45 int main(){ 46 while(scanf("%d",&n) != EOF){ 47 memset(c,0,sizeof(c)); 48 memset(d,0,sizeof(d)); 49 for(int i=1;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].h); 50 51 sort(a+1,a+n+1,cmp1);a[1].xx = 1; 52 for(int i=2;i<=n;i++){ 53 if(a[i].x == a[i-1].x) a[i].xx = a[i-1].xx; 54 else a[i].xx = i; 55 } 56 sort(a+1,a+n+1,cmp2);a[1].hh = 1; 57 for(int i=2;i<=n;i++){ 58 if(a[i].h != a[i-1].h) a[i].hh =i; 59 else a[i].hh = a[i-1].hh; 60 } 61 sort(a+1,a+n+1,cmp3); 62 63 //for(int i=1;i<=n;i++) 64 //printf("a[%d].x = %d a[%d].h = %d ",i,a[i].xx,i,a[i].hh); 65 66 LL ans = 0; 67 for(int i=1;i<=n;i++){ 68 LL x = sum(c,a[i].xx); 69 LL totalfront = sum(d,a[i].xx); 70 LL total = sum(d,maxn); 71 ans += a[i].hh * (x*a[i].xx - totalfront + total - totalfront - (i-x-1)*a[i].xx); 72 // printf("x= %I64d totalfront=%I64d total=%I64d ans = %I64d ",x,totalfront,total,ans); 73 add(c,a[i].xx,1); 74 add(d,a[i].xx,a[i].xx); 75 } 76 printf("%I64d ",ans); 77 } 78 return 0; 79 }