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\n",res);
84 //cout<<res<<endl;
85 printf("%I64d\n",res);
86 }
87 return 0;
88 }