반응형

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

 

14287번: 회사 문화 3

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

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

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

 

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
#include<iostream>
#include<vector>
 
using namespace std;
 
int n, m;
int segTree[200000];
int s[100001];
int e[100001];
int cnt = -1;
vector<int> list[100001];
 
void dfs(int num)
{
    s[num] = ++cnt;
 
    for (int& next : list[num]) {
        dfs(next);
    }
 
    e[num] = cnt;
}
 
void updateTree(int node, int w)
{
    while (node != 0) {
        segTree[node] += w;
        node >>= 1;
    }
}
 
int getTree(int left, int right)
{
    int ret = 0;
 
    while (left <= right) {
        if (left % 2 == 1) {
            ret += segTree[left];
            left += 1;
        }
        if (right % 2 == 0) {
            ret += segTree[right];
            right -= 1;
        }
 
        left >>= 1;
        right >>= 1;
    }
 
    return ret;
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        int parent;
        scanf("%d", &parent);
 
        if (parent != -1) {
            list[parent].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(s[i] + n, w);
        }
        else {
            printf("%d\n", getTree(n + s[i], n + e[i]));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16404번 - 주식회사 승범이네 (C++)  (0) 2023.05.12
[ 백준 ] 14288번 - 회사 문화 4 (C++)  (0) 2023.05.11
[ 백준 ] 14268번 - 회사 문화 2 (C++)  (0) 2023.05.09
[ 백준 ] 14267번 - 회사 문화 1 (C++)  (0) 2023.05.08
[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
반응형

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

 

14268번: 회사 문화 2

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

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. 특정 인원에게 칭찬을 하면 update 함수를 통해 s[ i ]에서 e [ i ]까지 값을 업데이트해줍니다.

 

3. 해당 인원의 칭찬 값을 구하기 위해서 segment tree에서 s[ 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
#include<iostream>
#include<vector>
 
using namespace std;
 
int n, m;
vector<int> list[100001];
int cnt;
int s[100001];
int e[100001];
int segTree[262222];
int lazy[262222];
 
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;
    }
 
    return;
}
 
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] += diff;
        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);
}
 
void query(int node, int s, int e, int idx)
{
    updateLazy(node, s, e);
 
    if (idx < s || idx > e) return;
 
    if (s == e) {
        printf("%d\n", segTree[node]);
        return;
    }
 
    int m = (s + e) / 2;
    query(node * 2, s, m, idx);
    query(node * 2 + 1, m + 1, e, idx);
}
 
void dfs(int num)
{
    s[num] = ++cnt;
 
    for (int next : list[num]) {
        dfs(next);
    }
 
    e[num] = cnt;
}
 
int main()
{
    scanf("%d %d", &n, &m);
 
    for (int i = 1; i <= n; i++) {
        int parent;
        scanf("%d", &parent);
 
        if (parent != -1) {
            list[parent].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, s[i], e[i], w);
        }
        else {
            query(1, 1, n, s[i]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14288번 - 회사 문화 4 (C++)  (0) 2023.05.11
[ 백준 ] 14287번 - 회사 문화 3 (C++)  (0) 2023.05.10
[ 백준 ] 14267번 - 회사 문화 1 (C++)  (0) 2023.05.08
[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
반응형

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

 

11003번: 최솟값 찾기

N개의 수 A1, A2, ..., AN과 L이 주어진다. Di = Ai-L+1 ~ Ai 중의 최솟값이라고 할 때, D에 저장된 수를 출력하는 프로그램을 작성하시오. 이때, i ≤ 0 인 Ai는 무시하고 D를 구해야 한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. 비재귀 세그먼트 트리를 이용하여 각 구간의 최솟값을 구해주고, 출력해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int arr[10000001];
int N, L;
 
int getTree(int left, int right)
{
    left += N;
    right += N;
    int ret = 1000000000;
 
    while (left <= right) {
        if (left & 1) {
            ret = min(arr[left], ret);
            left += 1;
        }
        if (~right & 1) {
            ret = min(arr[right], ret);
            right -= 1;
        }
        left >>= 1;
        right >>= 1;
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin >> N >> L;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[N + i];
    }
 
    for (int i = N - 1; i >= 1; i--) {
        arr[i] = min(arr[i << 1], arr[i << 1 | 1]);
    }
 
    for (int i = 0; i < N; i++) {
        cout << getTree(max(0, i - L + 1), i) << ' ';
    }
}
cs

 

반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14419번 - Foehn Phenomena (C++)  (0) 2023.05.07
[ 백준 ] 12844번 - XOR (C++)  (0) 2023.05.06
[ 백준 ] 1395번 - 스위치 (C++)  (0) 2023.05.03
[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02
[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
반응형

1. 비재귀 세그먼트 트리 (Segment Tree)

 

재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다.

 

2. 비재귀 세그먼트 트리 구현

 

항의 개수가 N개라면 리프노드는 N번 노드부터 2N - 1번 노드까지 입니다. 이후 N번 노드부터 1번 노드까지 for문을 통해 돌면서 해당 노드의 왼쪽 노드는 i << 1, 오른쪽 노드는 i << 1 | 1로 표현됩니다.

 

따라서, 합을 구하려면 segTree[node] = segTree[ node << 1 ] + segTree[ node << 1 | 1 ] 로 표현해줍니다.

 

3. 비재귀 세그먼트 트리 구간합 구하기

구간에서 왼쪽 경계의 노드 번호가 짝수라면 부모 노드가 반드시 구간에 포함되고, 홀수라면 부모 노드가 구간에 절대 포함되지 않습니다. 부모 노드가 구간에 절대 포함되지 않을 때 왼쪽 경계의 값에 1을 더해줍니다.

 

구간에서 오른쪽 경계의 노드 번호가 짝수라면 부모 노드가 구간에 절대 포함되지 않고, 홀수라면 부모 노드가 반드시 구간에 포함됩니다. 부모 노드가 구간에 절대 포함되지 않을 때 오른쪽 경계의 값에 1을 빼줍니다.

 

이를 왼쪽 경계의 값과 오른쪽 경계의 값이 교차될 때까지 수행하고, 교차된다면 반복문을 탈출해줍니다.

반응형
저작자표시 비영리 변경금지 (새창열림)

'자료구조' 카테고리의 다른 글

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)  (0) 2023.08.07
[ 자료구조 ] 트라이(Trie)  (0) 2023.06.24
[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)  (0) 2023.01.16
[ 자료구조 ] 희소 배열(Sparse Table)  (0) 2022.08.07
[ 자료구조 ] 세그먼트 트리 (Segment Tree)  (0) 2022.07.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/9426

 

9426번: 중앙값 측정

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 250,000, 1 ≤ K ≤ 5,000, K ≤ N) 둘째 줄부터 N개 줄에 측정한 온도가 순서대로 주어진다. 온도는 0보다 크거나 같고, 65535보다 작거나 같은 정수이다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 초기에 Segment Tree를 초기화해주는 대신 트리를 업데이트해주는 함수만을 통해 K 시간 동안 값들을 업데이트하고, 그중 중앙값을 ans에 더해줍니다.

 

2. K 시간 이후에는 i 초의 값을 세그먼트 트리에 넣어주고, i - K초의 값을 세그먼트 트리에서 빼줍니다.

 

3. 이후 중앙값을 ans에 더해주고, 마지막에 ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, K;
int segTree[262222];
int arr[250000];
ll ans;
 
void plusTree(int node, int s, int e, int num)
{
    if (s > num || e < num) return;
    segTree[node]++;
    
    if (s != e) {
        int m = (s + e) / 2;
 
        plusTree(node * 2, s, m, num);
        plusTree(node * 2 + 1, m + 1, e, num);
    }
}
 
void minusTree(int node, int s, int e, int num)
{
    if (s > num || e < num) return;
    segTree[node]--;
 
    if (s != e) {
        int m = (s + e) / 2;
 
        minusTree(node * 2, s, m, num);
        minusTree(node * 2 + 1, m + 1, e, num);
    }
}
 
void getTree(int node, int s, int e, int cnt)
{
    if (s == e) {
        ans += s;
        return;
    }
 
    int m = (s + e) / 2;
 
    if (segTree[node * 2] >= cnt) {
        getTree(node * 2, s, m, cnt);
    }
    else {
        getTree(node * 2 + 1, m + 1, e, cnt - segTree[node * 2]);
    }
}
 
int main()
{
    scanf("%d %d", &N, &K);
    int Max = 0;
    int Min = 66666;
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        Max = max(Max, arr[i]);
        Min = min(Min, arr[i]);
    }
 
    for (int i = 0; i < K; i++) {
        plusTree(1, Min, Max, arr[i]);
    }
 
    getTree(1, Min, Max, (K + 1) / 2);
 
    for (int i = K; i < N; i++) {
        plusTree(1, Min, Max, arr[i]);
        minusTree(1, Min, Max, arr[i-K]);
        getTree(1, Min, Max, (K + 1) / 2);
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 11003번 - 최솟값 찾기 (C++)  (0) 2023.05.05
[ 백준 ] 1395번 - 스위치 (C++)  (0) 2023.05.03
[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
[ 백준 ] 4195번 - 친구 네트워크 (C++)  (0) 2023.04.30
[ 백준 ] 25545번 - MMST (C++)  (0) 2023.04.29
반응형

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

 

1572번: 중앙값

중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

[ 자료구조 ] 세그먼트 트리 (Segment Tree)

1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다. 예를 들어 size가 5인 배열이 있다고 생각해봅시다. int arr [5] = {1

rudalsd.tistory.com

 

1. 초기에 Segment Tree를 초기화해주는 대신 트리를 업데이트해주는 함수만을 통해 K 시간 동안 값들을 업데이트하고, 그중 중앙값을 ans에 더해줍니다.

 

2. K 시간 이후에는 i 초의 값을 세그먼트 트리에 넣어주고, i - K초의 값을 세그먼트 트리에서 빼줍니다.

 

3. 이후 중앙값을 ans에 더해주고, 마지막에 ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, K;
int segTree[262222];
int arr[250000];
ll ans;
 
void plusTree(int node, int s, int e, int num)
{
    if (s > num || e < num) return;
    segTree[node]++;
    
    if (s != e) {
        int m = (s + e) / 2;
 
        plusTree(node * 2, s, m, num);
        plusTree(node * 2 + 1, m + 1, e, num);
    }
}
 
void minusTree(int node, int s, int e, int num)
{
    if (s > num || e < num) return;
    segTree[node]--;
 
    if (s != e) {
        int m = (s + e) / 2;
 
        minusTree(node * 2, s, m, num);
        minusTree(node * 2 + 1, m + 1, e, num);
    }
}
 
void getTree(int node, int s, int e, int cnt)
{
    if (s == e) {
        ans += s;
        return;
    }
 
    int m = (s + e) / 2;
 
    if (segTree[node * 2] >= cnt) {
        getTree(node * 2, s, m, cnt);
    }
    else {
        getTree(node * 2 + 1, m + 1, e, cnt - segTree[node * 2]);
    }
}
 
int main()
{
    scanf("%d %d", &N, &K);
    int Max = 0;
    int Min = 66666;
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        Max = max(Max, arr[i]);
        Min = min(Min, arr[i]);
    }
 
    for (int i = 0; i < K; i++) {
        plusTree(1, Min, Max, arr[i]);
    }
 
    getTree(1, Min, Max, (K + 1) / 2);
 
    for (int i = K; i < N; i++) {
        plusTree(1, Min, Max, arr[i]);
        minusTree(1, Min, Max, arr[i-K]);
        getTree(1, Min, Max, (K + 1) / 2);
    }
 
    printf("%lld", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1395번 - 스위치 (C++)  (0) 2023.05.03
[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02
[ 백준 ] 4195번 - 친구 네트워크 (C++)  (0) 2023.04.30
[ 백준 ] 25545번 - MMST (C++)  (0) 2023.04.29
[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
반응형

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

 

4195번: 친구 네트워크

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 관계된 친구들의 수를 저장할 rel 배열과 부모 노드를 저장할 vect 배열을 선언합니다.

 

2. unordered_map 자료 구조를 활용하여 해당 친구의 인덱스를 저장합니다.

 

3. Union-Find를 활용하여 친구들의 관계를 이어주고, 부모 노드의 rel 배열의 값을 더해주고, 이를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<unordered_map>
#include<string>
 
using namespace std;
 
int vect[200001];
int rel[200001];
unordered_map<string, int> m;
 
int Find(int num)
{
    if (vect[num] == num) return num;
    return vect[num] = Find(vect[num]);
}
 
void Union(int a, int b)
{
    int pa = Find(a);
    int pb = Find(b);
 
    vect[pb] = pa;
    rel[pa] += rel[pb];
}
 
int main()
{
    int T;
    scanf("%d", &T);
 
    for (int t = 0; t < T; t++) {
        int F;
        int cnt = 1;
        m.clear();
        scanf("%d", &F);
 
        for (int i = 1; i <= F * 2; i++) {
            vect[i] = i;
            rel[i] = 1;
        }
 
        for (int i = 0; i < F; i++) {
            char A[21];
            char B[21];
            scanf("%s %s", A, B);
 
            if (m.count(A) == 0) {
                m[A] = cnt++;
            }
            if (m.count(B) == 0) {
                m[B] = cnt++;
            }
 
            int a = m[A];
            int b = m[B];
 
            if (Find(a) != Find(b)) {
                Union(a, b);
            }
 
            printf("%d\n", rel[Find(a)]);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 9426번 - 중앙값 측정 (C++)  (0) 2023.05.02
[ 백준 ] 1572번 - 중앙값 (C++)  (0) 2023.05.01
[ 백준 ] 25545번 - MMST (C++)  (0) 2023.04.29
[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
[ 백준 ] 2513번 - 통학버스 (C++)  (0) 2023.04.27

+ Recent posts

티스토리툴바