题解：在路边有一行树，给出它们的坐标和高度，先按X坐标排序。记录排名，记为rankx，再按它们的高度排序，记录排名，记为rankh。两颗树i,j的差异度为
fabs(rankx[i]-rankx[j])*min(rankh[i],rankh[j])
最后求出任异两颗树差异度的和。
题解：首先，需要解决的是min(rh)的问题，对于这个问题，只要离散化之后按rh从大到小排序顺序求解即可，然后用树状数组维护之前出现rx比当前值小的个数与总和，那么同时就可以计算rx比当前大的个数和总和了，那么就可以依次计算出答案了。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34 |
#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,布布扣,bubuko.com
原文：http://www.cnblogs.com/forever97/p/3581136.html