题目
问题描述
约翰的n 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i 头奶牛的坐标为Xi，没有两头奶牛的坐标是相同的。奶牛们的叫声很大，第i 头和第j 头奶牛交流，会发出max{Vi;Vj}×|Xi−Xj| 的音量，其中Vi和Vj分别是第i 头和第j 头奶牛的听力。
假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。
输入文件
第1行:一个整数n(1n20,000)
第2..n+1行:第i+1行有两个整数Vi(1Vi20,000)和Xi(1Xi20,000)
输出文件
仅一行:一个整数表示所有奶牛产生的音量之和。
样例输入输出：
moofest.in
4 3 1 2 5 2 6 4 3
moofest.out
57
分析
朴素暴力枚举：枚举i,j，O(n2）。N最大到20000，放弃吧。
首先来观察一下这个音量的计算公式：首先在两只牛的听力v当中取较大值，然后和两者的坐标差相乘。
既然取较大的v，我们不妨把所有奶牛按照v从大到小排序。这样每次取出的奶牛和它右边的奶牛计算即可。
然后再来看如何处理坐标差。因为当前选出的这头奶牛一定是和它右边，也就是较小的奶牛进行计算，所以公式的第一部分是一个定值。那么我们不难想到在这里可以合并同类项。对于一个奶牛它所对应的左半边音量之和的公式就是：当前奶牛听力*（左边奶牛的个数*当前奶牛的坐标-左边所有奶牛的坐标和）。右边也就不难同理得出了。
要计算坐标和，那就树状数组呗。
程序
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int MAXN = 20000 + 1; 4 struct node 5 { 6 int x,v,id; 7 }cow[MAXN]; 8 struct Tree 9 { 10 long long sum,num; 11 }c[MAXN]; 12 int n; 13 bool cmpv(node a,node b) 14 { 15 return a.v>b.v; 16 } 17 bool comp(node a,node b) 18 { 19 return a.x<b.x; 20 } 21 long long ans=0; 22 int main() 23 { 24 freopen("moofest.in","r",stdin); 25 freopen("moofest.out","w",stdout); 26 scanf("%d",&n); 27 for(int i = 1; i <= n; i++) 28 scanf("%d%d",&cow[i].v,&cow[i].x); 29 sort(cow+1,cow+n+1,comp); 30 for(int i = 1; i <= n; i++) 31 { 32 cow[i].id = i; 33 for(int j = i; j <= n; j += j&-j) 34 { 35 c[j].sum+=cow[i].x; 36 c[j].num++; 37 } 38 } 39 sort(cow+1,cow+n+1,cmpv); 40 long long ans=0; 41 for (int i = 1; i <= n; i++) 42 { 43 long long sum = 0, num = 0; 44 for(int j = cow[i].id; j > 0; j -= j&-j) 45 { 46 sum += c[j].sum; 47 num += c[j].num; 48 } 49 ans += (num*cow[i].x-sum)*cow[i].v; 50 sum =- sum, num=-num; 51 for (int j = n; j > 0; j -= j&-j) 52 { 53 sum += c[j].sum; 54 num += c[j].num; 55 } 56 ans += (sum-num*cow[i].x)*cow[i].v; 57 for(int j = cow[i].id; j <= n; j += j&-j) 58 { 59 c[j].sum -= cow[i].x; 60 c[j].num--; 61 } 62 } 63 printf("%lld",ans); 64 return 0; 65 }