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$同理

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#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;
}
------ 本文结束 ------