Bzoj 3378(树状数组)

BZOJ 3378
$O(n^2)$算法肯定不行，我们尝试拆公式
对于$max(V_i, V_j)$，我们把牛按$V$排序，然后就可以消除$V$的影响，不再考虑这部分
对于$|X_i-X_j|$,我们不妨把他分成两部分，$(X_i-X_j) +(X_j-X_i)$
然后$\sum((X_i-X_j) +(X_j-X_i))=NUM_l \times X_i - SUM_l +SUM_r - NUM_r \times X_i$
其中$SUM_l$是在$X_i$左边的牛到起点的距离和，$SUM_r$同理
$NUM_l$是在$X_i$左边的牛的头数，$NUM_r$同理

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
using namespace std;
const int MAXN = 20000 + 5;
struct data {
    LL x, v;
    bool operator < (const data &b) const {
        return v < b.v;
    }
}cow[MAXN];
LL sum[MAXN], num[MAXN], MaxX;
int n;
int lowbit(int x) {return x & (-x);}
void update(LL *a, int x, LL v) {
    for (int i = x; i <= MaxX; i += lowbit(i)) {
        a[i] += v;
    }
}
LL query(LL *a, int x) {
    LL ret = 0;
    for (int i = x; i > 0; i -= lowbit(i)) {
        ret += a[i];
    }
    return ret;
}
void clean() {
    ms(sum, 0), ms(num, 0);
}
void solve() {
    clean();
    for (int i = 1; i <= n; i++) scanf("%lld%lld", &cow[i].v, &cow[i].x), MaxX = max(MaxX, cow[i].x);
    sort(cow + 1, cow + 1 + n);
    LL ans = 0;
    for (int i = 1; i <= n; i++) {
        LL x = cow[i].x, v = cow[i].v;
        LL SUMl = query(sum, x - 1), SUMr = query(sum, MaxX) - query(sum, x);
        LL NUMl = query(num, x - 1), NUMr = query(num, MaxX) - query(num, x);
        ans += v * (NUMl * x - SUMl + SUMr - NUMr * x);
        update(sum, x, x);
        update(num, x, 1);
    }
    printf("%lld\n", ans);
}
int main() {
    scanf("%d", &n), solve();
    return 0;
}