반응형

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

 

15967번: 에바쿰

재성이가 재혁이를 때린 날수 N과 재성이가 변덕을 부린 날의 개수 Q1, 재혁이가 얼마나 맞았는지 궁금한 구간의 개수 Q2가 주어진다. (1 ≤ N ≤ 1,000,000, 0 ≤ Q1, Q2 ≤ 10,000) 그 다음줄엔 재혁이가 i

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

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

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

rudalsd.tistory.com

 

1. 느리게 갱신되는 세그먼트 트리를 이용하여 세그먼트 트리를 업데이트해줍니다.

 

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
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
100
101
#include<iostream>
#define ll long long
 
using namespace std;
 
ll segTree[2100000];
int lazy[2100000];
int N, Q1, Q2;
int arr[1000001];
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node]) {
        segTree[node] += 1LL * lazy[node] * (1LL * e - s + 1);
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
 
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 updateTree(int node, int s, int e, int sidx, int eidx, int diff)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node] += 1LL * diff * (1LL * e - s + 1);
        if (s != e) {
            lazy[node * 2] += diff;
            lazy[node * 2 + 1] += diff;
        }
        return;
    }
    
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, diff);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, diff);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
ll getTree(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = getTree(node * 2, s, m, sidx, eidx);
    ll right = getTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q1 >> Q2;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < Q1 + Q2; i++) {
        int cmd;
        cin >> cmd;
 
        if (cmd == 1) {
            int n, m;
            cin >> n >> m;
            cout << getTree(1, 1, N, n, m) << '\n';
        }
        else {
            int s, e, l;
            cin >> s >> e >> l;
            updateTree(1, 1, N, s, e, l);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
[ 백준 ] 16978번 - 수열과 쿼리 22 (C++)  (0) 2023.08.01
[ 백준 ] 19940번 - 피자 오븐 (C++)  (0) 2023.07.31
[ 백준 ] 14852번 - 타일 채우기 3 (C++)  (0) 2023.07.30
반응형

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

 

11962번: Counting Haybales

Farmer John is trying to hire contractors to help rearrange his farm, but so far all of them have quit when they saw the complicated sequence of instructions FJ wanted them to follow. Left to complete the project by himself, he realizes that indeed, he has

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

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

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

rudalsd.tistory.com

 

1. 느리게 갱신되는 세그먼트 트리를 이용하여 세그먼트 트리를 업데이트 해줍니다.

 

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
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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include<iostream>
#define ll long long
 
using namespace std;
 
struct node {
    ll sum;
    ll min;
};
 
int N, Q;
int arr[200001];
node segTree[524300];
ll lazy[524300];
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node]) {
        segTree[node].sum += lazy[node] * (1LL * e - s + 1);
        segTree[node].min += lazy[node];
 
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
 
    return;
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node].sum = 1LL * arr[s];
        segTree[node].min = 1LL * arr[s];
 
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node].sum = segTree[node * 2].sum + segTree[node * 2 + 1].sum;
    segTree[node].min = min(segTree[node * 2].min, segTree[node * 2 + 1].min);
 
    return;
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int C)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node].sum += (1LL * e - s + 1) * (1LL * C);
        segTree[node].min += C;
 
        if (s != e) {
            lazy[node * 2] += C;
            lazy[node * 2 + 1] += C;
        }
 
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, C);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, C);
 
    segTree[node].sum = segTree[node * 2].sum + segTree[node * 2 + 1].sum;
    segTree[node].min = min(segTree[node * 2].min, segTree[node * 2 + 1].min);
 
    return;
}
 
ll getSum(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node].sum;
 
    int m = (s + e) / 2;
    
    return getSum(node * 2, s, m, sidx, eidx) + getSum(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
ll getMin(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return 11111111111;
    if (sidx <= s && e <= eidx) return segTree[node].min;
 
    int m = (s + e) / 2;
 
    return min(getMin(node * 2, s, m, sidx, eidx), getMin(node * 2 + 1, m + 1, e, sidx, eidx));
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < Q; i++) {
        char cmd;
        int A, B;
        cin >> cmd >> A >> B;
 
        if (cmd == 'M') {
            cout << getMin(1, 1, N, A, B) << '\n';
        }
        else if (cmd == 'P') {
            int C;
            cin >> C;
 
 
            updateTree(1, 1, N, A, B, C);
        }
        else {
            cout << getSum(1, 1, N, A, B) << '\n';
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5817번 - 고통받는 난쟁이들 (C++)  (0) 2023.06.10
[ 백준 ] 14449번 - Balanced Photo (C++)  (0) 2023.06.09
[ 백준 ] 15816번 - 퀘스트 중인 모험가 (C++)  (0) 2023.06.07
[ 백준 ] 17398번 - 통신망 분할 (C++)  (0) 2023.06.06
[ 백준 ] 16168번 - 퍼레이드 (C++)  (0) 2023.06.05
반응형

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

 

2934번: LRH 식물

상근이는 유전자 조작을 통해 줄기 두 개로 이루어진 식물을 만들었다. 이 식물은 줄기의 x좌표 L, R과 높이 H로 나타낼 수 있다. 아래 그림은 L=2, R=5, H=4인 식물이다. 상근이는 매일 매일 화단에

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

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

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

rudalsd.tistory.com

 

1. 느리게 갱신되는 세그먼트 트리를 이용하여 L + 1 부터 R - 1 까지 1을 더해주고, L노드와 R노드의 값에 이전에 핀 꽃의 개수인 cnt[ L ] + cnt[ R ]의 값을 빼고, 그 값을 출력합니다.

 

2. cnt[ L ]의 값과 cnt[ R ]의 값을 갱신해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int segTree[262222];
int lazy[262222];
int cnt[100001];
 
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)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node]++;
 
        if (s != e) {
            lazy[node * 2]++;
            lazy[node * 2 + 1]++;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx);
}
 
int getTree(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (s > idx || e < idx) return 0;
    if (s == e) return segTree[node];
 
    int m = (s + e) / 2;
    int left = getTree(node * 2, s, m, idx);
    int right = getTree(node * 2 + 1, m + 1, e, idx);
 
    return  left + right;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int L, R;
        scanf("%d %d", &L, &R);
 
        if (L + 1 <= R - 1) {
            updateTree(1, 1, 100000, L + 1, R - 1);
        }
 
        int tempL = getTree(1, 1, 100000, L);
        int tempR = getTree(1, 1, 100000, R);
 
        printf("%d\n", tempL + tempR - cnt[L] - cnt[R]);
 
        cnt[L] = tempL;
        cnt[R] = tempR;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11376번 - 열혈강호 2 (C++)  (0) 2023.05.26
[ 백준 ] 11375번 - 열혈강호 (C++)  (0) 2023.05.25
[ 백준 ] 14245번 - XOR (C++)  (0) 2023.05.22
[ 백준 ] 3006번 - 터보소트 (C++)  (0) 2023.05.21
[ 백준 ] 1280번 - 나무 심기 (C++)  (0) 2023.05.20
반응형

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/2820

 

2820번: 자동차 공장

상근이는 자동차를 매우 좋아한다. 자동차 공장에 취직한 상근이는 계속된 승진 끝에 드디어 사장이 되었다. 공장에는 총 N명의 직원이 있다. 상근이를 제외한 모든 직원은 한 명의 상사가 있다.

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배열에 저장하고, 그래프를 list에 저장합니다.

 

2. dfs를 통해 각 노드가 몇 번에서 시작해서 몇 번에서 끝나는지 오일러 경로 테크닉을 이용하여 st[ n ], en[ n ]에 저장하고, arr2[ st[ n ] ] = arr[ n ] 을 통해 초기화해 줍니다.

 

3. 초기 segmentTree를 만들 때 arr2를 기준으로 만듭니다.

 

4. 월급이 오르거나 내리면 느리게 갱신되는 세그먼트 트리를 이용하여 st[ i ] + 1부터 en[ i ]까지 월급을 더해줍니다.

 

5. segTree에서 해당 노드를 출력해 줍니다.

 

[ 소스코드 ]

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
unsigned int segTree[1050000];
unsigned int lazy[1050000];
vector<int> list[500001];
int st[500001];
int en[500001];
int arr[500001];
int arr2[500001];
int cnt;
 
void dfs(int num)
{
    st[num] = ++cnt;
    arr2[cnt] = arr[num];
 
    for (int& next : list[num]) {
        dfs(next);
    }
 
    en[num] = cnt;
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = arr2[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, unsigned int diff)
{
    updateLazy(node, s, e);
 
    if (e < sidx || s > eidx) return;
    if (sidx <= s && e <= eidx) {
        if (s == e) {
            segTree[node] += diff;
        }
        else {
            lazy[node * 2] += diff;
            lazy[node * 2 + 1] += diff;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, diff);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, diff);
}
 
void getTree(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (idx < s || idx > e) return;
    if (s == e) {
        cout << segTree[node] << '\n';
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, idx);
    getTree(node * 2 + 1, m + 1, e, idx);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        if (i != 1) {
            int p;
            cin >> p;
            list[p].push_back(i);
        }
    }
 
    dfs(1);
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < M; i++) {
        char com;
        int a;
        cin >> com >> a;
 
        if (com == 'p') {
            unsigned int x;
            cin >> x;
 
            updateTree(1, 1, N, st[a] + 1, en[a], x);
        }
        else {
            getTree(1, 1, N, st[a]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2310번 - 어드벤처 게임 (C++)  (0) 2023.05.15
[ 백준 ] 1800번 - 인터넷 설치 (C++)  (0) 2023.05.14
[ 백준 ] 16404번 - 주식회사 승범이네 (C++)  (0) 2023.05.12
[ 백준 ] 14288번 - 회사 문화 4 (C++)  (0) 2023.05.11
[ 백준 ] 14287번 - 회사 문화 3 (C++)  (0) 2023.05.10
반응형

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

 

16404번: 주식회사 승범이네

첫 번째 줄에 승범이를 포함한 판매원들의 수 N(1 ≤ N ≤ 100,000), 명령의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 판매원들은 1번부터 N번까지 번호가 매겨지며, 승범이는 항상 1번이다. 두 번째 줄에 판

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

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

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

rudalsd.tistory.com

 

1. dfs를 통해 각 노드가 몇 번에서 시작해서 몇 번에서 끝나는지 오일러 경로 테크닉을 이용하여 st[ n ], en[ n ]에 저장합니다.

 

2. 돈을 벌거나 잃으면 느리게 갱신되는 세그먼트 트리를 이용하여 st[ i ]부터 en[ i ]까지 더해줍니다.

 

3. segTree에서 해당 노드를 출력해줍니다.

 

[ 소스코드 ]

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
100
101
102
103
104
#include<iostream>
#include<vector>
 
using namespace std;
 
int N, M;
int st[100001];
int en[100001];
int segTree[262222];
int lazy[262222];
vector<int> list[100001];
int cnt;
 
void dfs(int num)
{
    st[num] = ++cnt;
 
    for (int& next : list[num]) {
        dfs(next);
    }
 
    en[num] = cnt;
}
 
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 diff)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        if (s == e) {
            segTree[node] += diff;
        }
        else {
            lazy[node * 2] += diff;
            lazy[node * 2 + 1] += diff;
        }
        return;
    }
 
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, diff);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, diff);
}
 
void getTree(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (e < idx || s > 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 %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        int p;
        scanf("%d", &p);
 
        if (p != -1) {
            list[p].push_back(i);
        }
    }
 
    dfs(1);
 
    for (int j = 0; j < M; j++) {
        int com, i;
        scanf("%d %d", &com, &i);
 
        if (com == 1) {
            int w;
            scanf("%d", &w);
 
            updateTree(1, 1, N, st[i], en[i], w);
        }
        else {
            getTree(1, 1, N, st[i]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1800번 - 인터넷 설치 (C++)  (0) 2023.05.14
[ 백준 ] 2820번 - 자동차 공장 (C++)  (0) 2023.05.13
[ 백준 ] 14288번 - 회사 문화 4 (C++)  (0) 2023.05.11
[ 백준 ] 14287번 - 회사 문화 3 (C++)  (0) 2023.05.10
[ 백준 ] 14268번 - 회사 문화 2 (C++)  (0) 2023.05.09
반응형

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

 

14288번: 회사 문화 4

영선회사에는 매우 좋은 문화가 있는데, 바로 상사가 직속 부하를 칭찬하면 그 부하가 부하의 직속 부하를 연쇄적으로 칭찬하는 내리 칭찬이 있다. 즉, 상사가 한 직속 부하를 칭찬하면 그 부하

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/256

 

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

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

rudalsd.tistory.com

 

1. dfs를 통해 각 노드가 몇 번에서 시작해서 몇 번에서 끝나는지 오일러 경로 테크닉을 이용하여 s[ n ], e[ n ]에 저장합니다.

 

2. 칭찬의 방향이 부하쪽이라면 느리게 갱신되는 세그먼트 트리를 이용하여 s[ i ]부터 e[ i ]까지 칭찬값을 더해줍니다.

 

3. 칭찬의 방향이 상사쪽이라면 비재귀 세그먼트 트리를 하나 더 만들어 n + s[ i ] 노드부터 1번 노드까지 칭찬값을 더해줍니다.

 

4. 느리게 갱신되는 세그먼트 트리에서 해당 인덱스의 값과 비재귀 세그먼트 트리에서 n + s[ i ]부터 n + e[ i ]까지의 구간 합을 더해 출력합니다.

 

[ 소스코드 ]

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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include<iostream>
#include<vector>
 
using namespace std;
 
int n, m;
int s[100001];
int e[100001];
int cnt;
int segTree[262222];
int lazy[262222];
int segTree2[200000];
vector<int> list[100001];
int cur = -1;
int ans;
 
void dfs(int num)
{
    s[num] = ++cnt;
 
    for (int& next : list[num]) {
        dfs(next);
    }
 
    e[num] = cnt;
}
 
void updateLazy(int node, int l, int r)
{
    if (lazy[node] != 0) {
        segTree[node] += lazy[node];
 
        if (l != r) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void updateTree(int node, int l, int r, int lidx, int ridx, int diff)
{
    updateLazy(node, l, r);
 
    if (r < lidx || ridx < l) return;
    if (lidx <= l && r <= ridx) {
        if (l == r) {
            segTree[node] += diff;
        }
        else {
            lazy[node * 2] += diff;
            lazy[node * 2 + 1] += diff;
        }
 
        return;
    }
 
    int m = (l + r) / 2;
    updateTree(node * 2, l, m, lidx, ridx, diff);
    updateTree(node * 2 + 1, m + 1, r, lidx, ridx, diff);
}
 
void updateTree2(int node, int diff)
{
    while (node != 0) {
        segTree2[node] += diff;
        node >>= 1;
    }
}
 
void getTree(int node, int l, int r, int idx)
{
    updateLazy(node, l, r);
 
    if (idx < l || r < idx) return;
 
    if (l == r) {
        ans += segTree[node];
        return;
    }
 
    int m = (l + r) / 2;
    getTree(node * 2, l, m, idx);
    getTree(node * 2 + 1, m + 1, r, idx);
}
 
void getTree2(int l, int r)
{
    while (l <= r) {
        if (l & 1) {
            ans += segTree2[l];
            l++;
        }
        if (~r & 1) {
            ans += segTree2[r];
            r--;
        }
 
        l >>= 1;
        r >>= 1;
    }
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        int p;
        scanf("%d", &p);
 
        if (p != -1) {
            list[p].push_back(i);
        }
    }
 
    dfs(1);
 
    for (int j = 0; j < m; j++) {
        int com;
        scanf("%d", &com);
        if (com == 1) {
            int i, w;
            scanf("%d %d", &i, &w);
 
            if (cur == -1) {
                updateTree(1, 1, n, s[i], e[i], w);
            }
            else {
                updateTree2(n + s[i] - 1, w);
            }
        }
        else if (com == 2) {
            int i;
            scanf("%d", &i);
 
            ans = 0;
 
            getTree(1, 1, n, s[i]);
            getTree2(n + s[i] - 1, n + e[i] - 1);
 
            printf("%d\n", ans);
        }
        else {
            cur *= -1;
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2820번 - 자동차 공장 (C++)  (0) 2023.05.13
[ 백준 ] 16404번 - 주식회사 승범이네 (C++)  (0) 2023.05.12
[ 백준 ] 14287번 - 회사 문화 3 (C++)  (0) 2023.05.10
[ 백준 ] 14268번 - 회사 문화 2 (C++)  (0) 2023.05.09
[ 백준 ] 14267번 - 회사 문화 1 (C++)  (0) 2023.05.08
반응형

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
반응형

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

 

1395번: 스위치

첫 줄에는 스위치의 개수 N(2 ≤ N ≤ 100,000)과 처리할 일의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M개의 줄에 대해 각 줄에 처리할 일에 대한 정보가 담겨진 세 개의 정수 O, Si, Ti가 입력된다. O

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. 해당 노드에서 스위치를 두 번 작동시키면 원상복구 되므로, lazy 배열을 -1 또는 1로 갱신합니다.

 

3. 해당 노드에서 스위치가 작동되면 전구의 수가 총 개수 - 현재 켜져있는 전구의 수로 바뀌므로 e - s + 1 - segTree[node]를 이용하여 갱신해줍니다.

 

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

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int segTree[262222];
int lazy[262222];
int N, M;
 
void modifyLazy(int node, int s, int e)
{
    if (lazy[node] == 1) {
        segTree[node] = e - s + 1 - segTree[node];
        if (s != e) {
            lazy[node * 2] *= -1;
            lazy[node * 2 + 1] *= -1;
        }
        lazy[node] *= -1;
    }
}
 
void modifyTree(int node, int s, int e, int sidx, int eidx)
{
    modifyLazy(node, s, e);
 
    if (eidx < s || e < sidx) return;
 
    if (sidx <= s && e <= eidx) {
        segTree[node] = e - s + 1 - segTree[node];
        if (s != e) {
            lazy[node * 2] *= -1;
            lazy[node * 2 + 1] *= -1;
        }
        return;
    }
 
    int m = (s + e) / 2;
    modifyTree(node * 2, s, m, sidx, eidx);
    modifyTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
int getTree(int node, int s, int e, int sidx, int eidx)
{
    modifyLazy(node, s, e);
 
    if (eidx < s || e < sidx) 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()
{
    fill(lazy, lazy + 262222, -1);
 
    scanf("%d %d", &N, &M);
 
    for (int i = 0; i < M; i++) {
        int O, S, T;
 
        scanf("%d %d %d", &O, &S, &T);
 
        if (S > T) swap(S, T);
 
        if (O == 0) {
            modifyTree(1, 1, N, S, T);
        }
        else {
            printf("%d\n", getTree(1, 1, N, S, T));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
[ 백준 ] 11003번 - 최솟값 찾기 (C++)  (0) 2023.05.05
[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02
[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
[ 백준 ] 4195번 - 친구 네트워크 (C++)  (0) 2023.04.30
반응형

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

 

16975번: 수열과 쿼리 21

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i j k: Ai, Ai+1, ..., Aj에 k를 더한다. 2 x: Ax 를 출력한다.

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. 느리게 갱신되는 세그먼트 트리를 활용하여 Update를 하고 원하는 인덱스의 값을 출력합니다.

 

[ 소스코드 ]

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
100
101
102
103
104
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, M;
ll arr[100001];
ll segTree[263000];
ll lazy[263000];
 
void makeTree(int node, int start, int end)
{
    if (start == end) {
        segTree[node] = arr[start];
        return;
    }
 
    int mid = (start + end) / 2;
    makeTree(node * 2, start, mid);
    makeTree(node * 2 + 1, mid + 1, end);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
void modifyLazy(int node, int start, int end)
{
    if (lazy[node] != 0) {
        segTree[node] += (ll)(end - start + 1) * lazy[node];
 
        if (start != end) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void modifyTree(int node, int start, int end, int i, int j, ll k)
{
    modifyLazy(node, start, end);
 
    if (start > j || end < i) return;
 
    if (i <= start && end <= j) {
        lazy[node] += k;
        modifyLazy(node, start, end);
 
        return;
    }
 
    int mid = (start + end) / 2;
    modifyTree(node * 2, start, mid, i, j, k);
    modifyTree(node * 2 + 1, mid + 1, end, i, j, k);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
void getTree(int node, int start, int end, int x)
{
    modifyLazy(node, start, end);
 
    if (start > x || x > end) return;
    if (start == end) {
        arr[start] = segTree[node];
        return;
    }
 
    int mid = (start + end) / 2;
    getTree(node * 2, start, mid, x);
    getTree(node * 2 + 1, mid + 1, end, x);
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    scanf("%d", &M);
 
    for (int m = 0; m < M; m++) {
        int cmd;
        scanf("%d", &cmd);
 
        if (cmd == 1) {
            int i, j;
            ll k;
            scanf("%d %d %lld", &i, &j, &k);
            modifyTree(1, 1, N, i, j, k);
        }
        else {
            int x;
            scanf("%d", &x);
            getTree(1, 1, N, x);
 
            printf("%lld\n", arr[x]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1777번 - 순열복원 (C++)  (0) 2023.01.20
[ 백준 ] 1849번 - 순열 (C++)  (0) 2023.01.19
[ 백준 ] 10999번 - 구간 합 구하기 2 (C++)  (0) 2023.01.17
[ 백준 ] 5676번 - 음주 코딩 (C++)  (0) 2023.01.15
[ 백준 ] 18436번 - 수열과 쿼리 37 (C++)  (0) 2023.01.14

+ Recent posts

티스토리툴바