poj 1990 MooFest

题目大意：

FJ有n头牛，排列成一条直线(不会在同一个点)，给出每头牛在直线上的坐标x。另外，每头牛还有一个自己的声调v，如果两头牛(i和j)之间想要沟通的话，它们必须用同个音调max(v[i],v[j])，沟通起来消耗的能量为：max(v[i],v[j]) * 它们之间的距离。问要使所有的牛之间都能沟通(两两之间)，总共需要消耗多少能量。

分析：

首先将这n头牛按照v值从小到大排序（后面说的排在谁的前面，都是基于这个排序）。这样，排在后面的牛和排在前面的牛讲话，两两之间所用的音量必定为后面的牛的v值，这样一来才有优化的余地。然后，对于某头牛i来说，只要关心跟排在他前面的牛交流就好了。我们必须快速地求出排在他前面的牛和他之间距离的绝对值之和ans，只要快速地求出ans，就大功告成。这里需要两个树状数组。

其实只需求出前面小于X的坐标数s2，和那些小于X的坐标之和s1，然后用total记录当前i个x坐标的所有和

距离为：s2*X0 - s1 + total - s1 - x -（i - count）*X;//分两部分来计算，小于X0的，和大于X0的。

因此考虑用两个树状数组来完成计算。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<map>
 4 #include<cstring>
 5 #include<cmath>
 6 #include<vector>
 7 #include<algorithm>
 8 #include<set>
 9 #include<string>
10 #include<queue>
11 #define N 20000
12 #define LL long long
13 using namespace std;
14 struct Node
15 {
16     int v,x;
17     bool operator<(const Node n)const
18     {
19         return v<n.v;
20     }
21 } a[N+5];
22 LL cnt[N+5],s[N+5];
23 int n;
24 int  lowbit(int x)
25 {
26     return ((x)&(-(x)));
27 }
28 void Update(LL *b,int x,LL val)
29 {
30     for(int i=x; i<=N; i+=lowbit(i))
31         b[i]+=val;
32 }
33 LL sum(LL *b,int x)
34 {
35     LL ret=0;
36     for(int i=x; i>0; i-=lowbit(i))
37         ret+=b[i];
38     return ret;
39 }
40 int main()
41 {
42     //freopen("in.txt","r",stdin);
43     while(scanf("%d",&n)!=EOF)
44     {
45         for(int i=0; i<n; i++) scanf("%d%d",&a[i].v,&a[i].x);
46         sort(a,a+n);
47        memset(cnt,0,sizeof(cnt));
48        memset(s,0,sizeof(s));
49         LL ans=0,total=0;
50         for(int i=0; i<n; i++)
51         {
52             Update(cnt,a[i].x,1);
53             Update(s,a[i].x,a[i].x);
54             total+=a[i].x;
55             LL s1=sum(cnt,a[i].x-1);
56             LL s2=sum(s,a[i].x-1);
57             //printf("%I64d %I64d====
",s1*a[i].x-s2, total-s2-a[i].x-a[i].x*(i-s1));
58             ans+=a[i].v*(s1*a[i].x-s2 +total-s2-a[i].x-a[i].x*(i-s1));
59         }
60         printf("%lld
",ans);
61     }
62     return 0;
63 }