Time Limit: 1000MS
Memory Limit: 30000K
Total Submissions: 8141
Accepted: 3674
Description
Every year, Farmer John's N (1 <= N <= 20,000) cows attend "MooFest",a social gathering of cows from around the world. MooFest involves a variety of events including haybale stacking, fence jumping, pin the tail on the farmer, and of course, mooing. When the cows all stand in line for a particular event, they moo so loudly that the roar is practically deafening. After participating in this event year after year, some of the cows have in fact lost a bit of their hearing.
Each cow i has an associated "hearing" threshold v(i) (in the range 1..20,000). If a cow moos to cow i, she must use a volume of at least v(i) times the distance between the two cows in order to be heard by cow i. If two cows i and j wish to converse, they must speak at a volume level equal to the distance between them times max(v(i),v(j)).
Suppose each of the N cows is standing in a straight line (each cow at some unique x coordinate in the range 1..20,000), and every pair of cows is carrying on a conversation using the smallest possible volume.
Compute the sum of all the volumes produced by all N(N-1)/2 pairs of mooing cows.
Input
* Line 1: A single integer, N
* Lines 2..N+1: Two integers: the volume threshold and x coordinate for a cow. Line 2 represents the first cow; line 3 represents the second cow; and so on. No two cows will stand at the same location.
Output
* Line 1: A single line with a single integer that is the sum of all the volumes of the conversing cows.
Sample Input
4 3 1 2 5 2 6 4 3
Sample Output
57
Source
题意：
给定一个序列，序列两点之间的花费为 两点之间的距离*（两点之间价值大者），求所有N(N-1)/2个点对的花费之和
思路：
对某个点来说，其等级可以作为乘数的情况是 它与它左右两边比它的等级小的组成点对
设某个点，坐标为 Xc，它的等级为val，其左边比它小的有n1个，右边比它小的有n2个，左边比比它小的坐标为Xi（1<=i<=n1），右边比它小的坐标为 Xj（1<=j<=n2）
则经过推导，我们可以得到其对答案的贡献为：
(n1-n2) * Xc * val + val ( segma(Xi) – segma(Xj) )
所以我们需要统计两个类型的值：左右两边比它等级小的点的个数，左右两边比它等级小的点的坐标和。
这两个类型的值需要分别求出来，但只要知道了其中一个就可得到另外一个（知道了左边的就可以推导出右边的）
我们利用树状数组来统计这些值，具体做法如下：
将所有点按照等级排序，则某个点现在的标号即为比它小的所有点（包括左和右）的总个数。
我们使用两个树状数组，从左到右一次插入每个节点，一个树状数组统计左边比它等级小的点的个数，另一个统计点的坐标和
第一个树状数组好理解，主要困难在于构造第二个树状数组
只需要每次 update（x[i], x[i]）即可
这样的话, x[i] 插入之前，getsum（x[i]）就是左边比i点等级小的点的坐标和
代码：
1 /* 2 * @FileName: D:代码与算法2017训练比赛七月训练四1013.cpp 3 * @Author: Pic 4 * @Date: 2017-08-04 21:31:01 5 * @Last Modified time: 2017-08-05 20:21:10 6 */ 7 8 #include <iostream> 9 #include <algorithm> 10 #include <cstdio> 11 #include <string.h> 12 #include <queue> 13 using namespace std; 14 typedef __int64 ll; 15 const int MAXN=20000+30; 16 //注意，这道题的vol有相同的情况出现。这样的话就不能先按x坐标排序，统计左右比这个点小的个数，然后按照vol排序统计左右比这个点小的点的vol和 17 //而是应该同步地统计这两个量，防止相同的情况 18 struct BIT{ 19 void init() 20 { 21 memset(Tree_sum,0,sizeof(Tree_sum)); 22 } 23 ll Tree_sum[MAXN];//存储树状数组的数组 24 //int maxn=20000+30; //树状数组的下标最大值 25 ll lowbit(ll x) //lowbit函数, 找到x与与 *最近的一个末位连续0比他多的数* 的距离 26 { 27 return x&(-x); 28 } 29 ll getsum(ll x) //获取0至x区间的和 30 { 31 ll sum=0; 32 for(;x>0;x-=lowbit(x)){ 33 sum+=Tree_sum[x]; 34 } 35 return sum; 36 } 37 void update(ll x,ll v) //更新某点的值 38 { 39 for(;x<=MAXN;x+=lowbit(x)){ 40 Tree_sum[x]+=v; 41 } 42 } 43 }; 44 BIT tr,tr2; 45 struct node 46 { 47 ll vol,x,id; 48 }a[MAXN]; 49 ll n1[MAXN]; 50 bool cmp(node a,node b) 51 { 52 return a.vol<b.vol; 53 } 54 bool cmp1(node a,node b) 55 { 56 return a.x<b.x; 57 } 58 int main(){ 59 //freopen("data.in","r",stdin); 60 ll n; 61 while(~scanf("%I64d",&n)){ 62 for(int i=0;i<n;i++){ 63 //scanf("%d%d",&a[i].vol,&a[i].x); 64 //cin>>a[i].vol>>a[i].x; 65 scanf("%I64d%I64d",&a[i].vol,&a[i].x); 66 a[i].id=i; 67 } 68 tr.init(); 69 tr2.init(); 70 sort(a,a+n,cmp1); 71 sort(a,a+n,cmp); 72 ll res=0,sum=0,sumn=0; 73 for(int i=0;i<n;i++){ 74 sumn=tr.getsum(a[i].x); 75 ll suma=tr2.getsum(a[i].x); 76 res+=((sum-suma-suma)*a[i].vol); 77 res+=((2*sumn-i)*a[i].vol*a[i].x); 78 //cout<<res<<endl; 79 tr2.update(a[i].x,a[i].x); 80 tr.update(a[i].x,1); 81 sum+=a[i].x; 82 } 83 //printf("%lld ",res); 84 //cout<<res<<endl; 85 printf("%I64d ",res); 86 } 87 return 0; 88 }