POJ

题意：

给定 $N$ 头牛的位置$(x)$和听力阈值$(v)$，每两头牛之间交流需要的声音是 $max( v1, v2) * | x1 - x2 |$ ，现在要求所有牛之间交流的声音总值。

思路：

对于每两头牛之间，总是取最大的$V$ , 我们就可以按照$V$的大小排序；

那么我们就可以用当前牛的 $V *$ 已经存在的牛到当前牛的距离总和，并更新答案。

这里要用树状数组记录一下下标之和 $and$ 个数，于是我们就两个树状数组。

 1 /*
 2 * @Author: windystreet
 3 * @Date:   2018-08-07 15:13:40
 4 * @Last Modified by:   windystreet
 5 * @Last Modified time: 2018-08-07 15:52:16
 6 */
 7 #include<stdio.h>
 8 #include<string.h>
 9 #include<algorithm>
10 
11 using namespace std;
12 
13 #define X first
14 #define Y second
15 #define eps  1e-5
16 #define gcd __gcd
17 #define pb push_back
18 #define PI acos(-1.0)
19 #define lowbit(x) (x)&(-x)
20 #define bug printf("!!!!!
");
21 #define mem(x,y) memset(x,y,sizeof(x))
22 
23 typedef long long LL;
24 typedef long double LD;
25 typedef pair<int,int> pii;
26 typedef unsigned long long uLL;
27 
28 const int maxn = 2e4+7;
29 const int INF  = 1<<30;
30 const int mod  = 1e9+7;
31 
32 struct node
33 {
34     int x,v;
35 }s[maxn];
36 
37 LL tree[maxn][3];     // 0 下标和
38 int n;                // 1  个数
39 
40 bool cmp(node a,node b){
41     return a.v<b.v||(a.v==b.v&&a.x<b.x);
42 }
43 
44 
45 void add(int x,int v,int flag){
46     for(int i=x;i<maxn;i+= lowbit(i)){
47         tree[i][flag] += v;
48     }
49     return ;
50 }
51 LL query(int x,int flag){
52     LL res = 0;
53     for(int i=x;i;i-=lowbit(i)){
54         res += tree[i][flag];
55     }
56     return res;
57 }
58 
59 
60 void solve(){
61     scanf("%d",&n);
62     for(int i=1;i<=n;i++){
63         scanf("%d%d",&s[i].v,&s[i].x);
64     }
65     sort(s+1,s+1+n,cmp);
66     LL ans = 0,a1,a2,b1,b2;
67     for(int i=1;i<=n;i++){
68         a1 = query(s[i].x,0);         // s[i].x之前的牛的下标和
69         a2 = query(maxn-1,0) - a1;    // 所有的牛的下标和
70         b1 = query(s[i].x,1);         // s[i].x之前的牛的数量
71         b2 = query(maxn-1,1) - b1;    // 所有牛的数量
72         ans += (b1*s[i].x - a1 + a2 - s[i].x * b2) * s[i].v;  
73         add(s[i].x,s[i].x,0);         // b1 * s[i].x - a1 表示s[i].x 之前的牛到s[i].x 的距离之和
74         add(s[i].x,1,1);              // a2 - s[i].x * b2 表示s[i].x 之后的牛到s[i].x 的距离之和
75 
76     }
77     printf("%lld
",ans);
78 
79     return;
80 }
81 
82 int main()
83 {
84 //    freopen("in.txt","r",stdin);
85 //    freopen("out.txt","w",stdout);
86 //    ios::sync_with_stdio(false);
87     int t = 1;
88     //scanf("%d",&t);
89     while(t--){
90     //    printf("Case %d: ",cas++);
91         solve();
92     }
93     return 0;
94 }