洛谷P2345 奶牛集会

洛谷P2345 奶牛集会
树状数组
按 v 从小到大排序消除 max 影响
 1 #include <bits/stdc++.h>
 2 #define For(i, j, k) for(int i=j; i<=k; i++)
 3 #define Dow(i, j, k) for(int i=j; i>=k; i--)
 4 #define LL long long
 5 using namespace std;
 6 inline int read() {
 7     int x = 0, f = 1;
 8     char ch = getchar();
 9     while(ch<'0'||ch>'9') { if(ch=='-') f = -1; ch = getchar(); }
10     while(ch>='0'&&ch<='9') { x = x*10+ch-48; ch = getchar(); }
11     return x * f;
12 }
13 void write(int x) {
14     if(x<0) putchar('-'), x = -x;
15     if(x>9) write(x/10);
16     putchar(x%10+48);
17 }
18 inline void writeln(int x) { write(x); putchar('
'); }
19 
20 const int N = 20011; 
21 int n; 
22 struct node{
23     int v, pos; 
24 }a[N];
25 struct TT{
26     LL sum; 
27     int num; 
28 }tree[N];
29 LL sumpos, ans; 
30 
31 inline bool cmp_v(node a, node b) {
32     return a.v < b.v; 
33 }
34 
35 inline int lowbit(int x) { return x&(-x); }
36 
37 inline void add(int pos) {
38     for(int x=pos; x<=20000; x+=lowbit(x) ) {
39         ++tree[x].num;
40         tree[x].sum += pos; 
41     }
42 }
43 
44 inline TT Query(int pos) {
45     TT p; p.num = 0; p.sum = 0; 
46     for(int x=pos; x; x-=lowbit(x)) {
47         p.num += tree[x].num; 
48         p.sum += tree[x].sum; 
49     }
50     return p; 
51 }
52 
53 int main() {
54     n = read(); 
55     For(i, 1, n) {
56         a[i].v = read(); a[i].pos = read(); 
57     }
58     sort(a+1, a+n+1, cmp_v); 
59     For(i, 1, n) {
60         TT p = Query(a[i].pos); 
61         ans = ans+ a[i].v*(1ll*p.num*a[i].pos-p.sum + sumpos-p.sum-(1ll*i-1-p.num)*a[i].pos ); 
62         sumpos += a[i].pos; 
63         add(a[i].pos); 
64     }
65     printf("%lld
", ans); 
66     return 0; 
67 }