티스토리 뷰

알고리즘 관련/BOJ

BOJ)13538 XOR 쿼리

JASON 자손9319 2017. 6. 5. 23:30

문제: 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번 쿼리를 처리해줄 수 있다.


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
#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&&<= 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->- lo->l->>= k)
        return kthquery(lo->l, hi->l, x, mid, k);
    return kthquery(lo->r, hi->r, mid + 1, y, k - (hi->l->- 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->== hi->l->v)    //좌측조건이 성립하는 경우 왼쪽 자식으로 가야함 , 
        return xorquery(lo->r, hi->r, mid + 1, y, k);    //하지만 왼쪽에 값이 없는 경우 오른쪽으로 가야만 함
    if (!(((y - x + 1/ 2)&k) && lo->r->!= 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]->= seg[0]->= 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 - 11, z) - sumquery(seg[x - 1], 0, MAX_X - 11, 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;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)10838 트리  (0) 2017.06.07
BOJ)14590 KUBC League (Small)  (0) 2017.06.06
BOJ)13538 XOR 쿼리  (0) 2017.06.05
BOJ)1322 X와K  (0) 2017.06.05
BOJ)1837 암호제작  (2) 2017.06.05
BOJ)14577 일기예보  (0) 2017.06.04
댓글
댓글쓰기 폼