POJ 1990 MooFest【树状数组】

题意：给出n头牛，每头牛有一个听力v,坐标x,两头牛之间的能量为max(v1,v2)*dist(v1,v2)，求总的能量值

先将每头牛按照v排序，排完顺序之后，会发现有坐标比当前的x小的，会有坐标比当前的x大的

假设坐标比x小的有num个

那么

距离之和 = x*num - 前面坐标的和 + 后面坐标的和 - （n-num-1）* x

又因为

后面坐标的和 = 整个区间坐标的和 - 前面坐标的和

所以用两个数组，一个数组用来算个数，另外一个数组用来算和

学习的这一篇题解--http://www.acmtime.com/?p=403

 1 #include<iostream>  
 2 #include<cstdio>  
 3 #include<cstring> 
 4 #include <cmath> 
 5 #include<stack>
 6 #include<vector>
 7 #include<map> 
 8 #include<set>
 9 #include<queue> 
10 #include<algorithm>  
11 using namespace std;
12 
13 typedef long long LL;
14 const int INF = (1<<30)-1;
15 const int mod=1000000007;
16 const int maxn=20005;
17 
18 LL a[maxn];//这个是用来求比x小的个数的
19 LL b[maxn];//这个是用来求前面的和
20 LL c[maxn];
21 int n;
22 
23 struct node{
24     int x,v;
25 }q[maxn];
26 
27 int cmp(node n1,node n2){
28     return n1.v < n2.v;
29 }
30 
31 int lowbit(int x){ return x & (-x);}
32 
33 LL sum(LL c[],int x){
34     LL ret=0;
35     while( x >0){
36         ret += c[x]; x-=lowbit(x);
37     }
38     return ret;
39 } 
40 
41 void add( LL c[],int x,int d){
42     while(x < maxn){
43         c[x]+=d;x+=lowbit(x);
44     }
45 }
46 
47 int main(){
48     scanf("%d",&n);
49     for(int i=1;i<=n;i++) scanf("%d %d",&q[i].v,&q[i].x);
50     sort(q+1,q+n+1,cmp);
51     
52     memset(a,0,sizeof(a));
53     memset(b,0,sizeof(b));
54     LL cnt =0;
55     for(int i=1;i<=n;i++){
56         int x = sum(a,q[i].x); //统计坐标比x小的有多少个 
57         LL alltotal = sum(b,maxn);//统计这个区间所有坐标的和 
58         LL total = sum(b,q[i].x);//统计前面坐标比x小的的和 
59         cnt += q[i].v * (x * q[i].x - total + alltotal - total - ( i - x -1) * q[i].x);
60         add(a,q[i].x,1);
61         add(b,q[i].x,q[i].x);
62     } 
63     printf("%I64d
",cnt);
64     return 0;
65 }

View Code

加油-------------

goooooooooooooo-------- -------

POJ 1990 MooFest【 树状数组 】

POJ 1990 MooFest【树状数组】