HDU 3015 Disharmony Trees 【 树状数组 】

题意：给出n棵树，给出横坐标x，还有它们的高度h，先按照横坐标排序，则它们的横坐标记为xx,

再按照它们的高度排序，记为hh

两颗树的差异度为 abs(xx[i] - xx[j]) * min(hh[i],hh[j])，求所有的差异度的和

和上面一道题一样，只不过这题是要Min的值，就将h从大到小排序，保证每一个h都是当前最小的

然后维护比当前x小的坐标的个数，当前区间的总和，前面比x小的坐标的和

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include <cmath>

 #include<stack>

 #include<vector>

 #include<map>

 #include<set>

 #include<queue>

 #include<algorithm>

 using namespace std;

 typedef long long LL;

 const int INF = (<<)-;

 const int mod=;

 const int maxn=;

 int n;

 struct node{ int x,xx,h,hh,id;};

 node a[maxn],b[maxn],q[maxn];

 int c[maxn],d[maxn];

 int s[maxn];

 int cmp1(node n1,node n2){ return n1.x < n2.x; }

 int cmp2(node n1,node n2){ return n1.h < n2.h;}

 int cmp3(node n1,node n2){ return n1.h > n2.h;}

 int lowbit(int x){ return x & (-x);}

 LL sum(int c[],int x){

     LL ret=;

     while(x>){

         ret+=c[x]; x-=lowbit(x);

     }

     return ret;

 }

 void add(int c[],int x,int d){

     while(x < maxn){

         c[x]+=d;x+=lowbit(x);

     }

 }

 int main(){

     while(scanf("%d",&n) != EOF){

         memset(c,,sizeof(c));

         memset(d,,sizeof(d));

         for(int i=;i<=n;i++) scanf("%d%d",&a[i].x,&a[i].h);

         sort(a+,a+n+,cmp1);a[].xx = ;

         for(int i=;i<=n;i++){

             if(a[i].x == a[i-].x) a[i].xx = a[i-].xx;

             else a[i].xx = i;

         }

         sort(a+,a+n+,cmp2);a[].hh = ;

         for(int i=;i<=n;i++){

             if(a[i].h != a[i-].h) a[i].hh =i;

             else a[i].hh = a[i-].hh;

         }

         sort(a+,a+n+,cmp3);

         //for(int i=1;i<=n;i++)

         //printf("a[%d].x = %d a[%d].h = %d\n",i,a[i].xx,i,a[i].hh);

         LL ans = ;

         for(int i=;i<=n;i++){

             LL x = sum(c,a[i].xx);

             LL totalfront = sum(d,a[i].xx);

             LL total = sum(d,maxn);

             ans += a[i].hh * (x*a[i].xx - totalfront + total - totalfront - (i-x-)*a[i].xx);

         //    printf("x= %I64d  totalfront=%I64d total=%I64d  ans = %I64d\n",x,totalfront,total,ans);

             add(c,a[i].xx,);

             add(d,a[i].xx,a[i].xx);

         }

         printf("%I64d\n",ans);

     }

     return ;

 }