반응형

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

 

10464번: XOR

입력의 첫 번째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 1000)가 주어진다. 다음 T 개의 줄에는 두 개의 정수 S와 F가 주어진다. (1 ≤ S ≤ F ≤ 1 000 000 000)

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 1부터 N까지 XOR한 값을 구해보면 다음과 같은 규칙을 발견할 수 있습니다.

1 -> 1

2 -> 3

3 -> 0

4 -> 4

5 -> 1

6 -> 7

7 -> 0

8 -> 8

9 -> 1

.

.

.

N

즉, N % 4의 값이 1이면 1, 2이면 N + 1, 3이면 0 그리고 0이면 N입니다.

 

2. S부터 F까지의 값을 XOR한 값은 1부터 F까지 XOR한 값과 1부터 S - 1까지 XOR한 값을 XOR하면 됩니다.

 

3. 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
#include<iostream>
 
using namespace std;
 
int XOR(int num)
{
    int mod = num % 4;
 
    if (mod == 0) return num;
    if (mod == 1) return 1;
    if (mod == 2) return num + 1;
    if (mod == 3) return 0;
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int S, F;
        scanf("%d %d", &S, &F);
        
        printf("%d\n", XOR(S - 1) ^ XOR(F));
    }
}
cs

 

반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 2164번 - 카드2 (C++)  (0) 2023.06.17
[ 백준 ] 14497번 - 주난의 난(難) (C++)  (0) 2023.06.16
[ 백준 ] 7490번 - 0 만들기 (C++)  (0) 2023.06.14
[ 백준 ] 20437번 - 문자열 게임 2 (C++)  (0) 2023.06.13
[ 백준 ] 12919번 - A와 B 2 (C++)  (0) 2023.06.12
반응형

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

 

14245번: XOR

첫 번째 줄에 수열의 크기 n (0 < n ≤ 500,000)이 주어진다. 두 번째 줄에 수열의 원소가 0번부터 n - 1번까지 차례대로 주어진다. 수열의 원소는 100,000보다 크지 않은 음이 아닌 정수이다. 세 번째 줄

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

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

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

rudalsd.tistory.com

 

1. 초기 배열을 arr 배열에 저장합니다.

 

2. segmentTree의 리프 노드에 arr 배열의 값들을 넣습니다.

 

3. 느리게 갱신되는 세그먼트 트리를 이용하여 lazy 배열의 값들에 XOR한 값을 저장합니다.

 

4. 해당 쿼리를 출력합니다.

 

[ 소스코드 ]

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
94
95
96
97
98
99
#include<iostream>
 
using namespace std;
 
int n, m;
int segTree[1050000];
int lazy[1050000];
int arr[500000];
 
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);
}
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node] != 0) {
        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 a)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node] ^= a;
        if (s != e) {
            lazy[node * 2] ^= a;
            lazy[node * 2 + 1] ^= a;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, a);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, a);
}
 
void getTree(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (idx < s || e < idx) return;
    if (s == e) {
        printf("%d\n", segTree[node]);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, idx);
    getTree(node * 2 + 1, m + 1, e, idx);
}
 
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 i = 0; i < m; i++) {
        int cmd;
        scanf("%d", &cmd);
 
        if (cmd == 1) {
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
 
            updateTree(1, 0, n - 1, a, b, c);
        }
        else {
            int a;
            scanf("%d", &a);
 
            getTree(1, 0, n - 1, a);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25
[ 백준 ] 2934번 - LRH 식물 (C++)  (0) 2023.05.23
[ 백준 ] 3006번 - 터보소트 (C++)  (0) 2023.05.21
[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
[ 백준 ] 2517번 - 달리기 (C++)  (0) 2023.05.19
반응형

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

티스토리툴바