MooFest

题意：有n头牛，每头牛有两个属性，音量v，在X轴上的坐标x。$牛_i$和$牛_j$想要通话，音量至少是$max(v_i, v_j) * abs(x_i - x_j)$，要求每对牛通话音量的和。

思路：
暴力做法就是$\sum_{i=0}^n\sum_{j=0}^{i-1}(max(v_i, v_j) * abs(x_i - x_j))$，复杂度$O(n^2)$。
我们按每头牛的$v_i$排序，可以把上面的式子化简为$\sum_i^n\sum_j^{i-1}(v_i * abs(x_i - x_j))$

我们知道第$i$头牛有$i-1$头牛比它的音量小，在把这$i-1$头牛分在这头牛$x_i$的左边和右边，把绝对值$abs$给去掉，设左边牛的$\sum x_j$为$sl\_dis$，总头数为$l\_num$；右边牛的$\sum x_j$为$sl\_dis$，总头数为$r\_num$；$i-1$头牛的总和为$s\_dis$，总头数为$num = i-1$。
就把公式变成了$\sum_{i=1}^nv_i *(l\_num*x_i -sl\_dis+sr\_dis-r\_num*x_i)$。
中间求$sl\_dis$，$sr\_dis$，$s\_dis$，$l\_num$，$r\_num$，$num$。就要用到树状数组，添加和查询每次操作都是$log(n)$复杂度。所以总复杂度就是$O(nlog(n))$。

在这题中构建了两个树状数组，一个记录了牛的距离，一个记录了牛的头数。
因为是边查询边构树，保证了：在第$i$头牛查询距离和头数时树状数组中都是$v$小于$v_i$的牛的和。
其中数组下标表示牛在X轴上的坐标。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
const ll N = 2e4+10;
ll tree[2][N];//1距离，0个数。
//每头牛的音量和距离，可以按音量大小从小到大排序
struct cow {ll v, x;inline bool operator < (cow U) const {return v < U.v;}
} C[N];
//对树状数组添加元素，每次都会在坐标x_i添加坐标和头数。
void add(ll p, ll val) {while(p <= N) {tree[1][p] += val;tree[0][p] += 1;p += (p & (-p));}
}
//找出在该坐标下（左边的坐标总和）和（左边牛的头数总和）
ll query(ll p, ll k) {ll ans = 0;while(p) {ans += tree[k][p];p -= (p & (-p));}return ans;
}int main() {// freopen("in.txt", "r", stdin);// freopen("out.txt", "w", stdout);ll n, l_num, num, r_num, sr_dis, sl_dis, s_dis, ans = 0;scanf("%lld", &n);for(int i=0; i<n; i++) {scanf("%lld%lld", &C[i].v, &C[i].x);}sort(C, C+n);for(int i=0; i<n; i++) {//从0开始，和上面有点偏差。num    = i;//小于v_i的牛的总头数l_num  = query(C[i].x, 0);//x_i左边的牛的头数r_num  = num - l_num;//x_i右边的牛的头数s_dis  = query(20000, 1);//牛的坐标总和sl_dis = query(C[i].x, 1);//x_i左边牛的坐标总和sr_dis = s_dis - sl_dis;//x_i右边牛的坐标总和ans += (C[i].x * l_num - sl_dis + sr_dis - C[i].x * r_num) * C[i].v;add(C[i].x, C[i].x);//添加元素，维护坐标和与牛的头数和。}printf("%lld", ans);return 0;
}