반응형

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(11, N);
 
    for (int i = 0; i < M; i++) {
        char com;
        int a;
        cin >> com >> a;
 
        if (com == 'p') {
            unsigned int x;
            cin >> x;
 
            updateTree(11, N, st[a] + 1, en[a], x);
        }
        else {
            getTree(11, N, st[a]);
        }
    }
}
cs
반응형
반응형

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(11, N, st[i], en[i], w);
        }
        else {
            getTree(11, N, st[i]);
        }
    }
}
cs
반응형
반응형

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(11, 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(11, n, s[i]);
            getTree2(n + s[i] - 1, n + e[i] - 1);
 
            printf("%d\n", ans);
        }
        else {
            cur *= -1;
        }
    }
}
cs
반응형
반응형

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

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(11, n, s[i], e[i], w);
        }
        else {
            query(11, n, s[i]);
        }
    }
}
cs
반응형

+ Recent posts