BOJ)13538 XOR 쿼리

문제: icpc.me/13538

5가지 종류의 쿼리를 처리하는 문제이다.

1번 쿼리를 x의 위치에 업데이트 시키는 새로운 세그먼트 트리를 생성한다고 가정하면

persistent segment tree 자료구조를 이용할 수 있다.

고로 1번 쿼리의 경우 트리의 개수 n을 증가시켜주면서 n번째 세그먼트 트리의 x의 위치에 업데이트 시켜준다.

이 방식으로 persistent segment tree를 구축시켜주면 3번 쿼리는 자연스럽게 n=n-k가 된다.

이제 2,4,5의 쿼리를 생각해보자

4번 쿼리의 경우 r번째 세그먼트 트리에서의 0~x의 sum에서 l-1번째 세그먼트 트리에서의 0~x의 sum을 빼줌으로서 처리가능하다.

5번 쿼리의 경우는 r번째 세그먼트 트리가 가지는 값에서 l-1번째 세그먼트 트리가 가지는 값을 뺀 값을 기준으로 이분탐색을 이용하여 처리 가능하다.

가장 까다로운게 2번 쿼리의 경우인데

2번 쿼리가 들어올 때 x값이 5라고 가정하자

5를 2진수로 표현하면 101인데 우리는 최대한 101과 어긋나는 방향으로(101과 피하면서 갈 수 있는 방향으로) 루트에서 부터 탐색을 해야한다.

즉 세그먼트 트리에서 자식 노드를 호출할 때 만약 현재 보고 있는 구간이 (0~7)이라면 

자식 노드의 구간은 (0~4) (5~7)을 보고 있을 것이다. 이 때 5와 XOR을하여 값이 커지려면 0~4쪽으로 이동해야함은 자명하다

하지만 0~4쪽에 값이 없다면 어쩔 수 없이 오른쪽 자식 노드를 호출해야 할 것이다. 이런 방법으로 2번 쿼리를 처리해줄 수 있다.

#include <cstdio>
#include <algorithm>
#include <vector>
#define MAX_X 524288
using namespace std;
struct node {
    int v;
    node *l, *r;
    node(int v, node *l, node *r) :v(v), l(l), r(r) {}
    node *update(int x, int y, int pos) {
        if (x <= pos&&pos <= y) {
            if (x == y)return new node(v + 1, NULL, NULL);
            int mid = (x + y) >> 1;
            return new node(v + 1, l->update(x, mid, pos), r->update(mid + 1, y, pos));
        }
        return this;
    }
}*seg[500050];
int sumquery(node *p, int x, int y, int lo, int hi) {
    if (y < lo || hi < x)return 0;
    if (lo <= x&&y <= hi)return p->v;
    int mid = (x + y) >> 1;
    return sumquery(p->l, x, mid, lo, hi) + sumquery(p->r, mid + 1, y, lo, hi);
}
int kthquery(node *lo, node *hi, int x, int y, int k) {
    if (x == y)return x;
    int mid = (x + y) >> 1;
    if (hi->l->v - lo->l->v >= k)
        return kthquery(lo->l, hi->l, x, mid, k);
    return kthquery(lo->r, hi->r, mid + 1, y, k - (hi->l->v - lo->l->v));
}
int xorquery(node *lo, node *hi, int x, int y, int k) {
    if (x == y)return x;
    int mid = (x + y) >> 1;
    if ((((y - x + 1) / 2)&k) && lo->l->v == hi->l->v)    //좌측조건이 성립하는 경우 왼쪽 자식으로 가야함 , 
        return xorquery(lo->r, hi->r, mid + 1, y, k);    //하지만 왼쪽에 값이 없는 경우 오른쪽으로 가야만 함
    if (!(((y - x + 1) / 2)&k) && lo->r->v != hi->r->v)    //좌측조건이 성립하는 경우 오른쪽 자식으로 가야함 .
        return xorquery(lo->r, hi->r, mid + 1, y, k);    //오른쪽에 값이 있는 경우에만 갈 수 있음
    return xorquery(lo->l, hi->l, x, mid, k);    //defalut
}
int m, q, x, y, z, n;
int main() {
    scanf("%d", &m);
    seg[0] = new node(0, NULL, NULL);
    seg[0]->l = seg[0]->r = seg[0];
    while (m--) {
        scanf("%d", &q);
        if (q == 1) {
            scanf("%d", &x);
            seg[++n] = seg[n - 1]->update(0, MAX_X - 1, x);
        }
        else if (q == 2) {
            scanf("%d%d%d", &x, &y, &z);
            printf("%d\n", xorquery(seg[x - 1], seg[y], 0, MAX_X - 1, z));
        }
        else if (q == 3) {
            scanf("%d", &x);
            n -= x;
        }
        else if (q == 4) {
            scanf("%d%d%d", &x, &y, &z);
            printf("%d\n", sumquery(seg[y], 0, MAX_X - 1, 1, z) - sumquery(seg[x - 1], 0, MAX_X - 1, 1, z));
        }
        else {
            scanf("%d%d%d", &x, &y, &z);
            printf("%d\n", kthquery(seg[x - 1], seg[y], 0, MAX_X - 1, z));
        }
    }
    return 0;
}