BOJ 18798. OR과 쿼리

https://www.acmicpc.net/problem/18798

18798번: OR과 쿼리

---

쿼리 문제이고, l, r 범위를 주고 하다 보니 자연스럽게 세그먼트 트리가 생각납니다.

 

쿼리 문제에서 세그먼트 트리가 유용한 이유는 특정 구간에 대한 연산을 O(구간의 크기)보다 작은 시간복잡도에 처리할 수 있는 경우가 많기 때문인데, 이 문제의 1번 쿼리는 그럴 방법이 없어보입니다. Bitwise OR 연산이라서 구간 내의 수마다 더해지는 값도 다를테고, 2번 쿼리를 처리하려면 결국 모든 수를 직접 관리하긴 해야 하기 때문이죠.

 

하지만 또 다시 다행인 점은, 1번 쿼리에서의 연산이 OR 연산이라는 점입니다. 쿼리를 처리하는 과정에서 각 수가 절대 감소하지 않을테니 총 연산 횟수를 줄일 수 있을지도 모릅니다. $ 0 \leq A_{i} \lt 2^{30} $라는 조건과 연관지어 생각해보면, 최대한 효율적으로 처리한다고 가정했을 때 최대 30N 번의 연산만으로 수열의 실질적인 변화를 전부 처리할 수 있습니다. 이 '효율적인 처리'를 위해 세그먼트 트리를 사용합니다.

 

세그먼트 트리에서 두 노드의 부모 노드는 필요에 따라 두 노드 내지는 그 아래의 두 서브트리를 전부 아우르는 값을 가지는데, 결국 이 관계를 어떻게 할 것인지가 핵심이라고 할 수 있습니다. 목표는 필요 없는 OR 연산을 걸러내는 것, 즉 쿼리로부터 영향을 받지 않는 노드들을 최대한 빠르게 판별하는 것입니다. $ A_i $의 값이 바뀌지 않는다는 것은 다시 말해 $ A_{i} \vee x = x $라는 것인데, 부모 노드는 $ A_{i} \wedge A_{i+1} $을 가지고 있을 시 $ (A_{i} \wedge A_{i+1}) \vee x = x $인지를 확인하여 자식 노드들이 "$ \vee x $"에 의해 영향을 받는지 알 수 있습니다. Bitwise AND 연산을 통해 두 노드에서 공통된 비트만 봐도 $ x $의 비트는 전부 가지고 있을테니 $ (A_{i} \wedge A_{i+1}) \vee x = x $입니다. 반면, 두 노드 중 하나라도 "$ \vee x $"에 의해 변화가 일어난다면 $ (A_{i} \wedge A_{i+1}) \vee x \neq x $이죠. 이렇게만 하면 30N에 준하는 연산으로 모든 쿼리 처리가 가능하느냐에는 살짝 물음표가 붙지만 완전한 증명이 쉽지는 않네요.

 

2번 쿼리는 $ A_i $가 K인지 여부만 따져서 합 세그먼트 트리로 관리하면 쉽습니다.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<int, pi> pii;
typedef pair<ll, ll> pl;
typedef pair<ll, pl> pll;
#define fi first
#define se second
#define pb push_back

const int MAX = 2.5e5, MAX_ST = 1<<19, start = MAX_ST/2;
int N, M, K, q, l, r, x, seg[MAX_ST][2];

void mod(int s, int e, int x, int node, int ns, int ne)
{
    if(e <= ns || ne <= s) return;
    if(s <= ns && ne <= e){
        if((seg[node][0] | x) == seg[node][0]) return;
    }
    if(node >= start){
        seg[node][0] |= x;
        if(seg[node][0] == K) seg[node][1] = 1;
        else seg[node][1] = 0;
        return;
    }
    int mid = (ns + ne) / 2;
    mod(s, e, x, node*2, ns, mid);
    mod(s, e, x, node*2+1, mid, ne);
    seg[node][0] = seg[node*2][0] & seg[node*2+1][0];
    seg[node][1] = seg[node*2][1] + seg[node*2+1][1];
}

int sum(int s, int e, int node, int ns, int ne)
{
    if(e <= ns || ne <= s) return 0;
    if(s <= ns && ne <= e) return seg[node][1];
    int mid = (ns + ne) / 2;
    return sum(s, e, node*2, ns, mid) + sum(s, e, node*2+1, mid, ne);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> N >> K;
    for(int i = 0; i < N; i++){
        cin >> seg[start+i][0];
        if(seg[start+i][0] == K) seg[start+i][1] = 1;
    }
    for(int i = start-1; i > 0; i--){
        seg[i][0] = seg[i*2][0] & seg[i*2+1][0];
        seg[i][1] = seg[i*2][1] + seg[i*2+1][1];
    }
    cin >> M;
    while(M--){
        cin >> q >> l >> r;
        if(q == 1){
            cin >> x;
            mod(l-1, r, x, 1, 0, start);
        }
        else{
            cout << sum(l-1, r, 1, 0, start) << '\n';
        }
    }
    return 0;
}