백준18798 OR과 쿼리

작성일 | In

문제 링크

  • http://icpc.me/18798

사용 알고리즘

  • 세그먼트 트리

시간복잡도

  • $O(N log N + N log X)$

풀이

1번 쿼리로 인해 값이 바뀌는 원소를 찾는다면 값을 변경하는 것은 쉽게 할 수 있습니다. 결국, 우리는 1번 쿼리로 인해 값이 바뀌는 원소들을 빠르게 찾아야 합니다.
각 원소는 1번 쿼리로 인해 최대 30번만 변한다는 점을 이용해 문제를 풀어봅시다.

만약 쿼리로 들어온 X가 구간 [s, e]를 모두 and한 값의 부분집합이라면 구간 [s, e]는 업데이트를 해줄 필요가 없습니다. 이것은 구간의 원소를 and한 값을 관리하는 세그먼트 트리를 이용해 빠르게 처리할 수 있습니다.
한 번의 쿼리는 $O(N)$이 걸릴 수는 있지만, 각 원소는 최대 30번만 변하기 때문에 주어지는 쿼리를 모두 적용해도 $O(30N) = O(N log X)$만 걸립니다.

값이 K인 원소의 개수를 세어주는 것은 펜윅트리 등을 이용해 쉽게 처리할 수 있습니다.
자세한 구현은 코드를 참고하면 됩니다.

비슷한 아이디어를 사용하는 문제로는 BOJ16136이 있습니다.

전체 코드

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
#include <bits/stdc++.h>
using namespace std;

int n, k, q;
int tree[252525];
void fen_update(int x, int v){
    for(; x<=n; x+=x&-x) tree[x] += v;
}
int fen_query(int x){
    int ret = 0;
    for(; x; x-=x&-x) ret += tree[x];
    return ret;
}
int arr[252525];
struct SegAnd{
    int tree[1 << 19];
    int bias = 1 << 18;
    void init(int node = 1, int s = 1, int e = n){
        if(s == e){
            tree[node] = arr[s]; return;
        }
        int m = s + e >> 1;
        init(node << 1, s, m);
        init(node << 1 | 1, m+1, e);
        tree[node] = tree[node << 1] & tree[node << 1 | 1];
    }
    void update(int l, int r, int v, int node = 1, int s = 1, int e = n){
        if(r < s || e < l) return;
        if(l <= s && e <= r && ((tree[node] & v) == v)) return;
        if(s == e){
            if(tree[node] == k) fen_update(s, -1);
            tree[node] |= v;
            if(tree[node] == k) fen_update(s, 1);
            return;
        }
        v = v & (~tree[node]);
        if(!v) return;
        int m = s + e >> 1;
        update(l, r, v, node << 1, s, m);
        update(l, r, v, node << 1 | 1, m+1, e);
        tree[node] = tree[node << 1] & tree[node << 1 | 1];
    }
}seg;

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> k;
    for(int i=1; i<=n; i++){
        cin >> arr[i];
        if(arr[i] == k) fen_update(i, 1);
    }
    seg.init();

    cin >> q;
    while(q--){
        int op, s, e, x; cin >> op >> s >> e;
        if(op == 1){
            cin >> x; seg.update(s, e, x);
        }else{
            cout << fen_query(e) - fen_query(s-1) << "\n";
        }
    }
}