2014
02-27

# Disharmony Trees

One day Sophia finds a very big square. There are n trees in the square. They are all so tall. Sophia is very interesting in them.

She finds that trees maybe disharmony and the Disharmony Value between two trees is associated with two value called FAR and SHORT.

The FAR is defined as the following:If we rank all these trees according to their X Coordinates in ascending order.The tree with smallest X Coordinate is ranked 1th.The trees with the same X Coordinates are ranked the same. For example,if there are 5 tree with X Coordinates 3,3,1,3,4. Then their ranks may be 2,2,1,2,5. The FAR of two trees with X Coordinate ranks D1 and D2 is defined as F = abs(D1-D2).

The SHORT is defined similar to the FAR. If we rank all these trees according to their heights in ascending order，the tree with shortest height is ranked 1th.The trees with the same heights are ranked the same. For example, if there are 5 tree with heights 4,1,9,7,4. Then their ranks may be 2,1,5,4,2. The SHORT of two trees with height ranks H1 and H2 is defined as S=min(H1,H2).

Two tree’s Disharmony Value is defined as F*S. So from the definition above we can see that, if two trees’s FAR is larger , the Disharmony Value is bigger. And the Disharmony value is also associated with the shorter one of the two trees.

Now give you every tree’s X Coordinate and their height , Please tell Sophia the sum of every two trees’s Disharmony value among all trees.

There are several test cases in the input

For each test case, the first line contain one integer N (2 <= N <= 100,000) N represents the number of trees.

Then following N lines, each line contain two integers : X, H (0 < X,H <=1,000,000,000 ), indicating the tree is located in Coordinates X and its height is H.

There are several test cases in the input

For each test case, the first line contain one integer N (2 <= N <= 100,000) N represents the number of trees.

Then following N lines, each line contain two integers : X, H (0 < X,H <=1,000,000,000 ), indicating the tree is located in Coordinates X and its height is H.

2
10 100
20 200
4
10 100
50 500
20 200
20 100

1
13

http://acm.hdu.edu.cn/showproblem.php?pid=3015

/************hdu3015*****************/
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define N 100010

int num_small[N],sum_small[N];

int n;

struct tree
{
int x,h;
int cx,ch;//存x和h的rank
int id;
}t[N],t1[N],t2[N];

void add(int i,int num,int *a)
{
while(i<=n)
{
a[i]+=num;
i+=i&(-i);
}
}

__int64 sum(int i,int *a)
{
__int64 ans=0;
while(i>0)
{
ans+=a[i];
i-=i&(-i);
}
return ans;
}

bool cmp1(tree a,tree b)
{
return a.x<b.x;
}
bool cmp2(tree a,tree b)
{
return a.h<b.h;
}
bool cmp(tree a,tree b)
{
return a.ch>b.ch;//!!!!
}

void init()
{
sort(t1+1,t1+n+1,cmp1);
sort(t2+1,t2+n+1,cmp2);
int i,j,k;
k=t1[1].id;
t1[1].cx=1;
t[k].cx=1;
for(i=2;i<=n;i++)
{
if(t1[i].x==t1[i-1].x)
{
t1[i].cx=t1[i-1].cx;
k=t1[i].id;
t[k].cx=t1[i].cx;
}
else
{
t1[i].cx=i;
k=t1[i].id;
t[k].cx=t1[i].cx;
}
}
t2[1].ch=1;
k=t2[1].id;
t[k].ch=1;
for(i=2;i<=n;i++)
{
if(t2[i].h==t2[i-1].h)
{
t2[i].ch=t2[i-1].ch;
k=t2[i].id;
t[k].ch=t2[i].ch;
}
else
{
t2[i].ch=i;
k=t2[i].id;
t[k].ch=t2[i].ch;
}
}
/*for(i=1;i<=n;i++)
printf("%d ",t[i].cx);
printf("/n");
for(i=1;i<=n;i++)
printf("%d ",t[i].ch);
printf("/n");*/
}
int main()
{
//freopen("a.txt","r",stdin);
int i,j;
while(scanf("%d",&n)!=EOF)
{
for(i=1;i<=n;i++)
{
scanf("%d%d",&t[i].x,&t[i].h);
t[i].id=i;
t1[i]=t2[i]=t[i];
}
init();
sort(t+1,t+n+1,cmp);
memset(num_small,0,sizeof(num_small));
memset(sum_small,0,sizeof(sum_small));
__int64 ans=0;
__int64 sum_x=t[1].cx;//t[i]前面所有数总和
__int64 num_min,sum_min;
for(i=2;i<=n;i++)
{
num_min=sum(t[i].cx,num_small);//t[i]前面比a[i]小的数的个数
sum_min=sum(t[i].cx,sum_small);//t[i]前面比a[i]小的数的和
//printf("!%d/n", num_min*t[i].cx-sum_min+sum_x-sum_min-(i-num_min-1)*t[i].cx);
ans+=t[i].ch*(num_min*t[i].cx-sum_min + sum_x-sum_min-(i-num_min-1)*t[i].cx);//第i个与其他的差的和
sum_x+=t[i].cx;
}
printf("%I64d/n",ans);
}
return 0;
}

1. 那边有本地人专门绑架抢劫外地来的游客，大前年我们去那边的时候开快艇路过一小岛，远远看见一家大小被绑在几颗树上，大喊救命呢，旁边站着几个应该是本地海盗，有刀有枪的，嘴巴都不堵你

2. 怨气大的不光是美团外卖，而是整个社会，特别是现在网络信息发达以后，各种装X炫富的人存在导致好逸恶劳的啃老的人更多了，说个我身边的例子，我堂侄女，一年的时间换了几份工作了，最近好像又辞职去四川玩了，上班的地方公交车非常方便非得开我哥的车去，回家不爽就和我嫂

3. 怨气大的不光是美团外卖，而是整个社会，特别是现在网络信息发达以后，各种装X炫富的人存在导致好逸恶劳的啃老的人更多了，说个我身边的例子，我堂侄女，一年的时间换了几份工作了，最近好像又辞职去四川玩了，上班的地方公交车非常方便非得开我哥的车去，回家不爽就和我嫂

4. 怨气大的不光是美团外卖，而是整个社会，特别是现在网络信息发达以后，各种装X炫富的人存在导致好逸恶劳的啃老的人更多了，说个我身边的例子，我堂侄女，一年的时间换了几份工作了，最近好像又辞职去四川玩了，上班的地方公交车非常方便非得开我哥的车去，回家不爽就和我嫂

5. 怨气大的不光是美团外卖，而是整个社会，特别是现在网络信息发达以后，各种装X炫富的人存在导致好逸恶劳的啃老的人更多了，说个我身边的例子，我堂侄女，一年的时间换了几份工作了，最近好像又辞职去四川玩了，上班的地方公交车非常方便非得开我哥的车去，回家不爽就和我嫂

6. 怨气大的不光是美团外卖，而是整个社会，特别是现在网络信息发达以后，各种装X炫富的人存在导致好逸恶劳的啃老的人更多了，说个我身边的例子，我堂侄女，一年的时间换了几份工作了，最近好像又辞职去四川玩了，上班的地方公交车非常方便非得开我哥的车去，回家不爽就和我嫂

7. 怨气大的不光是美团外卖，而是整个社会，特别是现在网络信息发达以后，各种装X炫富的人存在导致好逸恶劳的啃老的人更多了，说个我身边的例子，我堂侄女，一年的时间换了几份工作了，最近好像又辞职去四川玩了，上班的地方公交车非常方便非得开我哥的车去，回家不爽就和我嫂

8. 怨气大的不光是美团外卖，而是整个社会，特别是现在网络信息发达以后，各种装X炫富的人存在导致好逸恶劳的啃老的人更多了，说个我身边的例子，我堂侄女，一年的时间换了几份工作了，最近好像又辞职去四川玩了，上班的地方公交车非常方便非得开我哥的车去，回家不爽就和我嫂

9. #include <stdio.h>
int main(void)
{
int arr[] = {10,20,30,40,50,60};
int *p=arr;
printf("%d,%d,",*p++,*++p);
printf("%d,%d,%d",*p,*p++,*++p);
return 0;
}

为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下？

10. “可以发现,树将是满二叉树,”这句话不对吧，构造的树应该是“完全二叉树”，而非“满二叉树”。