题目背景
MooFest, 2004 Open
题目描述
约翰的N 头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的活动很
多，比如堆干草，跨栅栏，摸牛仔的屁股等等。它们参加活动时会聚在一起，第i 头奶牛的坐标为Xi，没有两头奶牛的坐标是相同的。奶牛们的叫声很大，第i 头和第j 头奶牛交流，会发出max{Vi; Vj}×|Xi − Xj | 的音量，其中Vi 和Vj 分别是第i 头和第j 头奶牛的听力。假设每对奶牛之间同时都在说话，请计算所有奶牛产生的音量之和是多少。
输入输出格式
输入格式：
• 第一行：单个整数N，1 ≤ N ≤ 20000
• 第二行到第N + 1 行：第i + 1 行有两个整数Vi 和Xi，1 ≤ Vi ≤ 20000; 1 ≤ Xi ≤ 20000
输出格式：
• 单个整数：表示所有奶牛产生的音量之和
输入输出样例
输入样例#1：
43 12 52 64 3
输出样例#1：
57
说明
朴素O(N2)
类似于归并排序的二分O(N logN)
树状数组O(N logN)
$$V*+abs(a_1-X)+V*abs(a_2-X)+V*abs(a_3-X)+....
\\=V*(abs(a_1-X)+abs(a_2-X)+abs(a_3-X)+.......)\\=V*(a_1-X+a_2-X+X-a_3)\\=V*((-N*X+(a_1+a_2+..+a_N)) +M*X-(a_3+...a_M)$$推公式的题目
设当前奶牛的音量为V,坐标为X,ai表示第i头奶牛的坐标假定a1,a2>X,a3<X(方便理解)我们发现abs不满足分配率(就是abs(a+b)!=abs(a)+abs(b) )此时我们分情况讨论设有n个奶牛的坐标比X大，有m个奶牛的坐标比X小,把上面的abs拆开 
那么对于N,M,a1+a2+...,a3+,,,
利用用树状数组求逆序对的思想我们可以用两个树状数组维护1 #include2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #define LL long long 9 #define lb(x) ((x)&(-x))10 using namespace std;11 const LL MAXN=40000001;12 inline LL read()13 {14 char c=getchar();LL x=0,f=1;15 while(c<'0'||c>'9') { if(c=='-') f=-1;c=getchar();}16 while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();return x*f;17 }18 struct node19 {20 LL v,x;21 }cow[MAXN];22 LL n;23 int comp(const node &a,const node &b)24 {25 return a.v