BIT专项总结

ACM

最近频繁的考察BIT，有必要对其认真的总结一下。

hdu 4638

题解
统计连续子段的个数。
树状数组+离线查询//好像莫队也可以搞一搞，准备学一手莫队莫队

ac code

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
struct Node{
    int l, r, id;
}node[maxn];
int pos[maxn], id[maxn];
int n, q;
int ans[maxn];
int c[maxn];
bool cmp(Node a, Node b){
    return a.l<b.l;
}
bool vis[maxn];
void init(){
    memset(vis, 0, sizeof(vis));
    memset(c, 0, sizeof(c));
}
int lowbit(int x){
    return x&(-x);
}
void add(int x, int val){
    while(x<=n){
        c[x] += val;
        x += lowbit(x);
    }
}
int query(int x){
    int ans = 0;
    while(x>0){
        ans += c[x];
        x -= lowbit(x);
    }
    return ans;
}
int getsum(int l, int r){
    return query(r)-query(l-1);
}
int main()
{
    ios::sync_with_stdio(false);
    int _;
    cin>>_;
    while(_--){
        init();
        cin>>n>>q;
        for(int i=1; i<=n; i++){
            cin>>id[i];
            pos[id[i]] = i;
        }
        for(int i=1; i<=q; i++){
            cin>>node[i].l>>node[i].r;
            node[i].id = i;
        }
        sort(node+1, node+q+1, cmp);
        for(int i=1; i<=n; i++){
            vis[id[i]] = true;
            if(vis[id[i]-1]&&vis[id[i]+1]){
                add(pos[id[i]], -1);
            }
            else if(vis[id[i]-1]||vis[id[i]+1]){
                continue;
            }
            else add(pos[id[i]], 1);
        }
        int cur = 1;
        for(int i=1; i<=q; i++){
            while(cur<node[i].l){
                if(id[cur]!=1) add(pos[id[cur]-1], 1);
                if(id[cur]!=n) add(pos[id[cur]+1], 1);
                cur++;
            }
            ans[node[i].id] = getsum(node[i].l, node[i].r);
        }
        for(int i=1; i<=q; i++){
            cout<<ans[i]<<endl;
        }
    }
    return 0;
}

人工湖公路

题意就是一个城市只能和它相邻的城市进行连接，因此我们要判断任意两个城市是否连接的时候，我们可以前缀和进行维护。

二维树状数组的使用范围

支持单点更新，块区间和查询

poj 1195 ac code

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
53
54
55
56
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 1100;
int bit[maxn][maxn];
int n;
int l, b, r, t;
int low_bit(int x){
    return x&(-x);
}
void add(int x, int y, int val){
    for(int i=x; i<=n; i+=low_bit(i)){
        for(int j=y; j<=n; j+=low_bit(j)){
            bit[i][j] += val;
        }
    }
    return ;
}
int query(int x, int y){
    int ans = 0;
    for(int i=x; i>0; i-=low_bit(i)){
        for(int j=y; j>0; j -= low_bit(j)){
            ans += bit[i][j];
        }
    }
    return ans;
}
int getsum(int x1, int y1, int x2, int y2){
    return query(x1-1, y1-1)+query(x2, y2)
        -query(x1-1, y2)-query(x2, y1-1);
}
int main()
{
    ios::sync_with_stdio(false);
    int x;
    cin>>x>>n;
    memset(bit, 0, sizeof(bit));
    while(cin>>x){
        if(x == 3) break;
        else if(x == 1){
            cin>>l>>b>>r;
            add(l+1, b+1, r);
        }
        else if(x == 2){
            cin>>l>>b>>r>>t;
            cout<<getsum(l+1, b+1, r+1, t+1)<<endl;
        }
    }
    return 0;
}

询问单点的值，修改区间的值

和之前的更新顺序是相反的，从大到小的更新，从小到大的查询

poj 2155 Matrix

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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
const int maxn = 1100;
int bit[maxn][maxn];
int n, m;
int l, b, r, t;
int low_bit(int x){
    return x&(-x);
}
void add(int x, int y, int val){
    for(int i=x; i>0; i-=low_bit(i)){
        for(int j=y; j>0; j-=low_bit(j)){
            bit[i][j] += val;
        }
    }
    return ;
}
int query(int x, int y){
    int ans = 0;
    for(int i=x; i<=n; i+=low_bit(i)){
        for(int j=y; j<=n; j += low_bit(j)){
            ans += bit[i][j];
        }
    }
    return ans;
}
//int getsum(int x1, int y1, int x2, int y2){
//    return query(x1-1, y1-1)+query(x2, y2)
//        -query(x1-1, y2)-query(x2, y1-1);
//}
int main()
{
    ios::sync_with_stdio(false);
    int _;
    cin>>_;
    while(_--){
        cin>>n>>m;
        memset(bit, 0, sizeof(bit));
        string op;
        int x1, y1, x2, y2;
        for(int i=0; i<m; i++){
            cin>>op;
            if(op[0] == 'C'){
                cin>>x1>>y1>>x2>>y2;
                add(x1-1, y1-1, 1);
                add(x2, y2, 1);
                add(x1-1, y2, -1);
                add(x2, y1-1, -1);
            }
            else{
                cin>>x1>>y1;
                cout<<query(x1, y1)<<endl;
            }
        }
        if(_)cout<<endl;
    }
    return 0;
}
/*
1
2 10
C 1 1 2 2
C 1 1 2 2
C 1 1 2 2
Q 2 2
*/

cf E

题目链接

未解决的问题

本文标题:BIT专项总结

文章作者:Babydragon

发布时间:2018-08-04, 18:18:06

最后更新:2018-08-05, 08:21:26

原始链接:http://baolintian.github.io/2018/08/04/BIT专项总结/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. hdu 4638
    1. 1.1. ac code
  2. 2. 人工湖公路
  3. 3. 二维树状数组的使用范围
    1. 3.1. poj 1195 ac code
    2. 3.2. 询问单点的值，修改区间的值
      1. 3.2.1. poj 2155 Matrix
    3. 3.3. cf E
  4. 4. 未解决的问题
{{ live2d() }}