树状数组的修炼疑惑篇

洛谷p2345

奶牛叫不出の痛

 1 #include<bits/stdc++.h>
 2 #define ll long long
 3 using namespace std;
 4 const int maxn = 2e5 + 10;
 5 int n;
 6 ll cnt[maxn];//cnt[i]表示i位置及其左侧牛的个数 
 7 ll sum[maxn];
 8 ll res = 0;
 9 ll mx = 0;
10 struct cow
11 {
12     ll x, v;
13     bool operator < (const cow &a){
14         return v < a.v;
15     }
16 };
17 cow a[maxn]; 
18 
19 int lowbit(int x)
20 {
21     return x & -x;
22 }
23 
24 void updcnt(int x, int val)
25 {
26     for(int i = x ; i <= mx ; i += lowbit(i)){
27         cnt[i] += val;
28     }
29 }
30 
31 void updsum(int x, ll val)
32 {
33     for(int i = x ; i <= mx ; i += lowbit(i)){
34         sum[i] += val;
35     }
36 }
37 
38 ll getcnt(int x)
39 {
40     ll tmp = 0;
41     for(int i = x ; i >= 1 ; i -= lowbit(i)){
42         tmp += cnt[i];
43     }
44     return tmp;
45 }
46 
47 ll getsum(int x)//求原点到x的所有存在的点的距离 
48 {
49     ll s = 0;
50     for(int i = x ; i >= 1 ; i -= lowbit(i)){
51         s += sum[i];
52     }
53     return s;
54 }
55 
56 int main(){
57     scanf("%d",&n);
58     for(int i = 1 ; i <= n ; i++){
59         scanf("%lld%lld",&a[i].v,&a[i].x);
60         mx = max(mx, a[i].x);//最远距离 
61     }
62     sort(a + 1, a + n + 1);
63     
64     updcnt(a[1].x, 1);
65     updsum(a[1].x, a[1].x);
66     for(int i = 2 ; i <= n ; i++){//
67         updcnt(a[i].x, 1);
68         updsum(a[i].x, a[i].x);
69         ll cl = getcnt(a[i].x - 1), cr = getcnt(mx) - getcnt(a[i].x);//cnt of left/right
70         ll sl = getsum(a[i].x - 1), sr = getsum(mx) - getsum(a[i].x);//sum of left/right
71         res += a[i].v * (sr - cr * a[i].x + a[i].x * cl - sl);
72     }
73     printf("%lld
",res);
74     
75     return 0;
76 }

上来纠结了一会，但还是有点思路方向的。

将距离分类为该点左侧以及右侧进行处理。

每次更新一头奶牛，分别用树状数组维护记录cnt和sum，写两个upd和get。

但是代码就是想半天写不出。很棘手的问题。。。或许是因为思路不够清晰？还是要明确维护操作的细节才行啊。

欸。。。继续刷题（研究题解）吧

树状数组的修炼 疑惑篇

树状数组的修炼疑惑篇