HDU 3015 Disharmony Trees

题解：在路边有一行树，给出它们的坐标和高度，先按X坐标排序。记录排名，记为rankx，再按它们的高度排序，记录排名，记为rankh。两颗树i,j的差异度为

fabs(rankx[i]-rankx[j])*min(rankh[i],rankh[j])

最后求出任异两颗树差异度的和。

题解：首先，需要解决的是min(rh)的问题，对于这个问题，只要离散化之后按rh从大到小排序顺序求解即可，然后用树状数组维护之前出现rx比当前值小的个数与总和，那么同时就可以计算rx比当前大的个数和总和了，那么就可以依次计算出答案了。

#include <cstdio>

#include <iostream>

#include <algorithm>

using namespace std;

const int N=100010;

struct node{long long x,h,rx,rh;}a[N];

int s[N],c[N],n;

long long ans,ns;

bool cmp1(node a,node b){return a.x<b.x;}

bool cmp2(node a,node b){return a.h<b.h;}

bool cmp3(node a,node b){return a.h>b.h;}

void updata(int x,int num){while(x<=n)c[x]++,s[x]+=num,x+=x&-x;}

int time(int x){int t=0;while(x>0)t+=c[x],x-=x&-x;return t;}

int sum(int x){int t=0;while(x>0)t+=s[x],x-=x&-x;return t;}

int main(){

    while(~scanf("%d",&n)){

        for(int i=1;i<=n;i++)s[i]=c[i]=0;

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

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

        for(int i=2;i<=n;i++)a[i].rx=(a[i].x==a[i-1].x?a[i-1].rx:i);

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

        for(int i=2;i<=n;i++)a[i].rh=(a[i].h==a[i-1].h?a[i-1].rh:i);

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

        ans=ns=0;

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

           long long t=time(a[i].rx),m=sum(a[i].rx);

           ans+=a[i].rh*(a[i].rx*t-m+ns-m-a[i].rx*(i-t-1));

           updata(a[i].rx,a[i].rx);

           ns+=a[i].rx;

        }

        cout<<ans<<endl;

    }

    return 0;

}

巴特西

HDU 3015 Disharmony Trees

最新文章

热门文章