백준 13538번 XOR 쿼리

문제 요약

다섯 종류의 쿼리를 처리해야 합니다.

1. 배열의 끝에 원소를 하나 추가한다.
2. $A_L \cdots A_R$에서 x와 xor한 값이 가장 큰 $y(=A_i)$를 출력한다.
3. 배열의 끝에서 k개를 제거한다.
4. $A_L \cdots A_R$에서 x보다 작거나 같은 원소의 개수를 출력한다.
5. $A_L \cdots A_R$에서 K번째 수를 출력한다.

쿼리는 최대 50만개가 들어오고, 입력되는 수는 최대 50만이다.

풀이

A의 최대 길이는 50만입니다. 그래서 그냥 50만짜리 배열이 있고 원소가 추가된다고 치면 추가될 자리에 변경이 일어난다고 치고, 삭제 쿼리는 그냥 길이를 줄인다고 생각합시다.

이제 등장가능한 원소의 범위를 커버하는 세그먼트 트리를 만듭시다.

$n$번째 원소의 제일 최근 업데이트를 가지고 있는 세그먼트 트리를 roots[n]이라고 합시다. 이런 식의 처리는 PST로 가능합니다.

그렇게 보면 1, 3, 4, 5번 쿼리는 쉽게 처리가 가능합니다.

1번 쿼리는 그냥 업데이트 쿼리고, 3번 쿼리는 관리중인 루트노드의 개수를 k개만큼 버리면 됩니다.

4번 쿼리는 roots[R]에서 1...x의 구간합에서 roots[L-1]에서 1...x의 구간합을 빼주면 됩니다.

5번 쿼리는 여기서 다뤘습니다. 확인해주세요

2번 쿼리가 문제인데 세그먼트 트리를 만들 때, Perfect Binary Tree로 만듭니다.

세그먼트 트리의 높이를 h라고 합시다. 그러면 루트 노드에서부터 아래로 내려갈 때, 왼쪽 자식의 합이 0보다 크다는 것은 오른쪽에서 부터 h번째 비트가 0인 수가 존재한다는 뜻이고, 오른쪽 자식의 합이 0보다 크다는 것은 h번째 비트가 1인 수가 존재한다는 뜻입니다

이런식으로 세그먼트 트리를 타고 내려가면 하나를 내려갈 때마다 최상위비트에서 오른쪽으로 넘어가고 그 비트가 켜져있는 수의 존재를 오른쪽 자식과 왼쪽 자식을 확인함으로 알 수 있습니다.

xor을 해서 큰 수를 만들기 위해서는 x의 최상위 비트부터 보면서 이 비트를 1로 만들어 줄 수 있으면 1로 만들어 주는 것이 제일 큰 수를 만드는 방법입니다.

따라서, roots[R]에서 roots[L-1]을 빼준 세그먼트 트리에서 위와 같은 방식으로 내려가면 최대가 되는 값을 찾을 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
const int MAX = 1 << 19;

struct Node {
    int l, r, val;
    Node() : l(0), r(0), val(0) {};
    Node(int l_, int r_, int val_) : l(l_), r(r_), val(val_) {};
};

int N, Q;
vector<Node> tree(1 << 20);
int roots[500005];

void init() {
    for (int i = 1; i < MAX; ++i) {
        tree[i].l = i << 1;
        tree[i].r = i << 1 | 1;
    }
}

void update(int node, int s, int e, int val, int idx) {
    tree[node].val += val;
    if (s != e) {    // not leaf node
        int mid = (s + e) >> 1;
        int n1 = tree[node].l, n2 = tree[node].r;
        if (idx <= mid) {
            tree[node].l = tree.size();
            tree.push_back(tree[n1]);
            update(tree[node].l, s, mid, val, idx);
        }
        else {
            tree[node].r = tree.size();
            tree.push_back(tree[n2]);
            update(tree[node].r, mid + 1, e, val, idx);
        }
    }
    else assert(s == idx);
}

int xor_query(int s, int e, int x) {
    int l = 0, r = MAX - 1;
    int shift = 18;
    int ret = 0;
    while (l != r) {
        int mid = (l + r) >> 1;
        int lsz = tree[tree[e].l].val - tree[tree[s].l].val;
        int rsz = tree[tree[e].r].val - tree[tree[s].r].val;
        if (x & (1 << shift)) {
            if (lsz > 0) {
                s = tree[s].l; e = tree[e].l;
                r = mid;
            }
            else {
                ret |= (1 << shift);
                s = tree[s].r; e = tree[e].r;
                l = mid + 1;
            }
        }
        else {
            if (rsz > 0) {
                ret |= (1 << shift);
                s = tree[s].r; e = tree[e].r;
                l = mid + 1;
            }
            else {
                s = tree[s].l; e = tree[e].l;
                r = mid;
            }
        }
        --shift;
    }
    assert(l == r);
    assert(shift == -1);
    return ret;
}

int sum_query(int s, int e, int x) {
    int l = 0, r = MAX - 1;
    int ret = 0;
    while (l != r) {
        int mid = (l + r) >> 1;
        if (x <= mid) {
            s = tree[s].l; e = tree[e].l;
            r = mid;
        }
        else {
            ret += tree[tree[e].l].val - tree[tree[s].l].val;
            e = tree[e].r; s = tree[s].r;
            l = mid + 1;
        }
    }
    assert(l == r);
    return ret + (tree[e].val - tree[s].val);
}

int get_kth(int s, int e, int k) {
    int l = 0, r = MAX - 1;
    while (l != r) {
        int mid = (l + r) >> 1;
        int lsz = tree[tree[e].l].val - tree[tree[s].l].val;
        if (lsz >= k) {
            s = tree[s].l; e = tree[e].l;
            r = mid;
        }
        else {
            s = tree[s].r; e = tree[e].r;
            k -= lsz;
            l = mid + 1;
        }
    }
    assert(l == r);
    return l;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> Q;
    init(); roots[0] = 1;
    for (int i = 0; i < Q; ++i) {
        int q; cin >> q;
        if (q == 1) {
            int x; cin >> x;
            roots[++N] = tree.size();
            tree.push_back(tree[roots[N - 1]]);
            update(roots[N], 0, MAX-1, 1, x);
        }
        else if (q == 2) {
            int l, r, x; cin >> l >> r >> x;
            cout << xor_query(roots[l - 1], roots[r], x) << '\n';
        }
        else if (q == 3) {
            int x; cin >> x;
            N -= x;
        }
        else if (q == 4) {
            int l, r, x; cin >> l >> r >> x;
            cout << sum_query(roots[l - 1], roots[r], x) << '\n';
        }
        else if (q == 5) {
            int l, r, k; cin >> l >> r >> k;
            cout << get_kth(roots[l - 1], roots[r], k) << '\n';
        }
        else assert(false);
    }
    return 0;
}