挑战程序设计竞赛，283页， 树状数组
题目意思：
一群牛参加完牛的节日后都有了不同程度的耳聋，第i头牛听见别人的讲话，别人的音量必须大于v[i]，当两头牛i，j交流的时候，
交流的最小声音为max{v[i],v[j]}*他们之间的距离。现在有n头牛，求他们之间两两交流最少要的音量和
本题要点：
1、 先对牛按照V从小到大排序, 所有第i头牛和i之前的牛说话需要的总能量
sum{v[i] * abs(x[i] - x[j])}(i > j), 对于绝对值 abs(x[i] - x[j]，
我们可以将牛i之前的所有牛分成两部分:
横坐标x小于牛i的， 在数轴上表示,就是在i的左边;
横坐标x大于牛i的， 在数轴上表示,就是在i的右边;
2、开两个树状数组：
LL c1[MaxN], c2[MaxN]; //c1 维护比 e[i].x 小的牛有多少头，c2维护比 e[i].x 小的牛 的x的总和
参考网址：https://blog.csdn.net/bestsort/article/details/80853221
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define lowbit(i) ((i)&(-i))
using namespace std;
typedef long long LL;
const int MaxN = 100010;
int n;
LL c1[MaxN], c2[MaxN]; //c1 维护比 e[i].x 小的牛有多少头，c2维护比 e[i].x 小的牛 的x的总和struct edge
{
LL v, x;bool operator<(const edge & rhs) const{
return v < rhs.v;}
}e[MaxN];LL getSum(int x, LL c[])
{
LL sum = 0;for(int i = x; i > 0; i -= lowbit(i)){
sum += c[i];}return sum;
}void update(int x, LL v, LL c[])
{
for(int i = x; i < MaxN; i += lowbit(i)){
c[i] += v;}
}void solve()
{
sort(e + 1, e + n + 1);LL ans = 0, sum = 0;for(int i = 1; i <= n; ++i){
// sump 表示 在 e[i]的左边，有多少头牛的横坐标 比 e[i].x 小// sumx 表示 在 e[i]的左边，所有牛的横坐标 比 e[i].x 小 总和// sum - sumx 表示在 e[i]的左边，所有牛的横坐标 比 e[i].x 大 总和// i - 1 - sump, 表示 在 e[i]的左边，有多少头牛的横坐标 比 e[i].x 大// 对于牛 i，和左边的横坐标比 牛i小的牛交流的总能量 = (sump * e[i].x - sumx) * e[i].v// 和左边的横坐标比 牛i大的牛交流的总能量 = (sum - sumx - e[i].x * (i - 1 - sump)) * e[i].vLL sumx = getSum(e[i].x, c2), sump = getSum(e[i].x, c1);ans += (sump * e[i].x - sumx + sum - sumx - e[i].x * (i - 1 - sump)) * e[i].v;sum += e[i].x;update(e[i].x, 1, c1);update(e[i].x, e[i].x, c2);}printf("%lld\n", ans);
}int main()
{
scanf("%d", &n);for(int i = 1; i <= n; ++i){
scanf("%lld%lld", &e[i].v, &e[i].x);}solve();return 0;
}/* 4 3 1 2 5 2 6 4 3 *//* 57 */