반응형

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

 

12844번: XOR

크기가 N인 수열 A0, A1, ..., AN-1이 주어졌을 때, 다음 두 종류의 쿼리를 수행해보자. 1 i j k: Ai, Ai+1, ..., Aj에 k를 xor한다. 2 i j: Ai, Ai+1, ..., Aj를 모두 xor한 다음 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 세그먼트 트리와 lazy값을 저장할 배열을 만듭니다.

 

2. 현재 쿼리의 노드 개수가 홀수일 때만 XOR을 해주고, 짝수라면 lazy 값만 넘겨줍니다.

 

3. 느리게 갱신되는 세그먼트 트리를 활용하여 Update를 하고 XOR 값을 출력합니다.

 

[ 소스코드 ]

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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
#include<iostream>
 
using namespace std;
 
int N, M;
int arr[500001];
int segTree[1050000];
int lazy[1050000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = arr[s];
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node] = segTree[node * 2] ^ segTree[node * 2 + 1];
}
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node] != 0) {
        if ((e - s + 1) % 2 == 1) {
            segTree[node] ^= lazy[node];
        }
 
        if (s != e) {
            lazy[node * 2] ^= lazy[node];
            lazy[node * 2 + 1] ^= lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int k)
{
    updateLazy(node, s, e);
 
    if (e < sidx || s > eidx) return;
    if (sidx <= s && e <= eidx) {
        lazy[node] ^= k;
        updateLazy(node, s, e);
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, k);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, k);
 
    segTree[node] = segTree[node * 2] ^ segTree[node * 2 + 1];
}
 
int getTree(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (e < sidx || s > eidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    return getTree(node * 2, s, m, sidx, eidx) ^ getTree(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 0, N - 1);
 
    scanf("%d", &M);
 
    for (int q = 0; q < M; q++) {
        int n, i, j, k;
        scanf("%d %d %d", &n, &i, &j);
 
        if (n == 1) {
            scanf("%d", &k);
            updateTree(1, 0, N - 1, i, j, k);
        }
        else {
            printf("%d\n", getTree(1, 0, N - 1, i, j));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 14267번 - 회사 문화 1 (C++)  (0) 2023.05.08
[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
[ 백준 ] 11003번 - 최솟값 찾기 (C++)  (0) 2023.05.05
[ 백준 ] 1395번 - 스위치 (C++)  (0) 2023.05.03
[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02

+ Recent posts

티스토리툴바