/*
写完这篇博客有很多感慨,过去一段时间都是看完题解刷题,刷题,看会题解,没有了大一那个时候什么都不会的时候刷题的感觉,
这个题做了一天半,从开始到结束都是从头开始自己构思的很有感觉,找回到当初的感觉
*/

Disharmony Trees

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 90 Accepted Submission(s): 56
 
Problem Description
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.

 
Input
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.

 
Output
For each test case output the sum of every two trees’s Disharmony value among all trees. The answer is within signed 64-bit integer.
 
Sample Input
2
10 100
20 200
4
10 100
50 500
20 200
20 100
 
Sample Output
1
13
 
 
Source
2009 Multi-University Training Contest 12 - Host by FZU
 
Recommend
gaojie
 
/*
错误思路:
按照高度排好序之后整个的求值过程就变成了h[1]*abs((n*a[1]-(a[2]+a[3]+..+a[n])))+h[2]*abs(((n-1)*a[2]-(a[3]+a[4]+..+a[n])))+.....
然后用树状数组维护a序列的值
解析:
因为绝对值的问题所以(n*a[1]-(a[2]+a[3]+..+a[n]))这个位置不能直接减去,要考虑大小才能把括号去掉 正确思路:
按照高排好序之后,每棵树的min_h肯定是本身的h,abs_a的话需要考虑从i到n的a与本身的大小
树状数组维护两个值比自己小的有多少个,还有维护a数组,
*/
#include<bits/stdc++.h>
#define N 100005
#define ll long long
#define lowbit(x) x&(-x)
using namespace std;
struct node
{
ll x,h;
ll rankx,rankh;
node(){}
node(ll a,ll b)
{
x=a;
h=b;
}
};
ll n;
ll x,h;
ll c[N];//用来构建树状数组维护到当前结点比当前结点小的个数
ll sum[N];//用来维护到当前结点比当前结点小的数的总和
node f[N];
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)//这次排序从大到小排序,这样能使从0到i的所有计算中用到的h都是h[i];
{
return a.h>b.h;
}
void init()
{
memset(c,,sizeof c);
memset(sum,,sizeof sum);
}
void update1(ll x,ll val)
{
while(x<N)
{
c[x]+=val;
x+=lowbit(x);
}
}
void update2(ll x,ll val)
{
while(x<N)
{
sum[x]+=val;
x+=lowbit(x);
}
}
ll getsum1(ll x)//这个是获取有多少个比自己小的
{
ll s=;
while(x>)
{
s+=c[x];
x-=lowbit(x);
}
return s;
}
ll getsum2(ll x)//这个是获取比自己小的和
{
ll s=;
while(x>)
{
s+=sum[x];
x-=lowbit(x);
}
return s;
}
int main()
{
//freopen("C:\\Users\\acer\\Desktop\\in.txt","r",stdin);
while(scanf("%lld",&n)!=EOF)
{
init();
f[]=node(-,-);
for(int i=;i<=n;i++)
{
scanf("%lld%lld",&x,&h);
f[i]=node(x,h);
}//处理输入 sort(f+,f+n+,cmp1);//先按照坐标的大小进行排序
for(int i=;i<=n;i++)
{
if(f[i].x==f[i-].x)
f[i].rankx=f[i-].rankx;
else
f[i].rankx=i;
} sort(f+,f+n+,cmp2);//然后按照树的高度的大小进行排序
for(int i=;i<=n;i++)
{
if(f[i].h==f[i-].h)
f[i].rankh=f[i-].rankh;
else
f[i].rankh=i;
}
sort(f+,f+n+,cmp3);//第三次排序保证每次运算用到的h都是h[i](也就是使得h[i]在0到i中最小;
ll cur=;
ll total=;
ll same=;//和自己相同的个数
ll low=;//比自己小的个数
ll big=;//比自己大的个数
ll low_sum=;//比自己小的和
ll big_sum=;//比自己大的和
//for(int i=1;i<=n;i++)
// cout<<f[i].rankx<<" ";
//cout<<endl;
for(int i=;i<=n;i++)
{
total+=f[i].rankx;//表示到当前位置的总坐标值 /*更新当前的信息*/
update1(f[i].rankx,);
update2(f[i].rankx,f[i].rankx);
//和当前位置相同的个数
same=getsum1(f[i].rankh)-getsum1(f[i].rankh-);
//比自己小的个数;
low=getsum1(f[i].rankx-);
//比自己大的个数
big=i-same-low;
//比自己小的和
low_sum=getsum2(f[i].rankx-);
//比自己大的和
big_sum=total-low_sum-same*f[i].rankx;
//cout<<"total ="<<total<<endl;
//cout<<"getsum1(x) ="<<getsum1(x)<<endl;
//cout<<"i-getsum1(x)-1 ="<<i-getsum1(x)-1<<endl;
//cout<<"getsum2(x) ="<<getsum2(x)<<endl;
//cout<<"total-getsum2(x)="<<total-getsum2(x)<<endl;
//cout<<endl; //比自己大的和减去比当前值大的和
cur+=f[i].rankh*((low*f[i].rankx-low_sum)+(big_sum-big*f[i].rankx));
//a[i]乘上比自己小的个数减去比自己小的和
}
printf("%lld\n",cur);
}
return ;
}

最新文章

  1. phpinfo有mysqlnd没有mysql
  2. rpm 命令
  3. Linux-CentOS 6.5 mini 中没有curses.h的问题
  4. Android studio的深坑 导jar包重复的异常处理
  5. mysql zip install
  6. Javascript实现笛卡儿积算法
  7. 关于“心脏出血”漏洞(heartbleed)的理解
  8. 3D math primer for graphics and game development
  9. php调用linux命令
  10. ListActivity ListView 使用 介绍 用法
  11. UVa 10098: Generating Fast
  12. linux内核学习之四:进程切换简述
  13. hdu 5002 (动态树lct)
  14. [数]补题ver.
  15. JQ02
  16. linux 切割文件的命令
  17. UVA-10710 Skyscraper Floors (找规律+幂取模)
  18. 架构-LAMP特级学习(网站加速解决方案)
  19. 数论练习(5)——青蛙的约会(扩gcd)
  20. HTML5项目笔记4:使用Audio API设计绚丽的HTML5音乐播放器

热门文章

  1. JS中var和let
  2. Array Partition I
  3. Jmeter的安装和启动时出现unable to access jarfile apachejmeter.jar error value=1错误处理
  4. MongoDB的全文检索(Text Search)功能
  5. CentOS7.3下部署Rsyslog+LogAnalyzer+MySQL中央日志服务器
  6. ASP.NET没有魔法——目录
  7. 22.Linux-块设备驱动之框架详细分析(详解)
  8. JAVA提高一:静态导入、可变参数、增强型for循环、装拆箱
  9. java web 学习笔记 编码问题总结
  10. jQuery form插件使用详解