반응형

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

 

1777번: 순열복원

순열의 크기 N(1 ≤ N ≤ 100,000)이 주어진다. 두 번째 줄에는 순열 1, 2, …, N에 해당하는 Inversion sequence가 공백으로 구분되어 들어온다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 모든 리프 노드를 1로 초기화시킵니다.

 

2. 각 숫자의 값은 큰 숫자부터 뒤의 빈칸의 수를 의미합니다. 따라서, 세그먼트 트리의 노드의 값이 빈칸의 수를 의미하고, 이 수가 현재 숫자의 값보다 크다면 해당 노드로, 작다면 노드의 값을 뺀 값을 가지고 다음 노드로 재귀합니다.

 

3. 리프노드에 도달하면 해당 위치에 현재 숫자가 있는 것이므로 ans [해당 위치] = 현재 숫자가 됩니다.

 

4. for문을 통해 1부터 N번 째 위치까지의 수를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int arr[100001];
int ans[100001];
int segTree[263000];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = 1;
        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 x, int i)
{
    segTree[node] -= 1;
 
    if (s == e) {
        ans[s] = i;
        return;
    }
 
    int m = (s + e) / 2;
    if (segTree[node * 2 + 1] < x) {
        updateTree(node * 2, s, m, x - segTree[node * 2 + 1], i);
    }
    else {
        updateTree(node * 2 + 1, m + 1, e, x, i);
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = N; i > 0 ; i--) {
        updateTree(1, 1, N, arr[i] + 1, i);
    }
 
    for (int i = 1; i <= N; i++) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10090번 - Counting Inversions (C++)  (0) 2023.01.22
[ 백준 ] 1615번 - 교차개수세기 (C++)  (0) 2023.01.21
[ 백준 ] 1849번 - 순열 (C++)  (0) 2023.01.19
[ 백준 ] 16975번 - 수열과 쿼리 21 (C++)  (0) 2023.01.18
[ 백준 ] 10999번 - 구간 합 구하기 2 (C++)  (0) 2023.01.17
반응형

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

 

1849번: 순열

1부터 N까지의 수들이 한 번씩 쓰인 수열이 있다. 그 수열에서 i 앞에 있는 수 들 중, i보다 큰 수들의 개수를 A[i]라고 정의하자. A[i]가 주어져 있을 때, 원래 수열을 구하는 프로그램을 작성하여라

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 모든 리프 노드를 1로 초기화시킵니다.

 

2. 각 숫자의 값은 작은 숫자부터 앞의 빈칸의 수를 의미합니다. 따라서, 세그먼트 트리의 노드의 값이 빈칸의 수를 의미하고, 이 수가 현재 숫자의 값보다 크다면 해당 노드로, 작다면 노드의 값을 뺀 값을 가지고 다음 노드로 재귀합니다.

 

3. 리프노드에 도달하면 해당 위치에 현재 숫자가 있는 것이므로 ans [해당 위치] = 현재 숫자가 됩니다.

 

4. for문을 통해 1부터 N번 째 위치까지의 수를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
int arr[100001];
int segTree[263000];
int ans[100001];
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = 1;
        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 getTree(int node, int s, int e, int x, int i)
{
    if (s == e) {
        segTree[node] = 0;
        ans[s] = i;
        return;
    }
 
    segTree[node] -= 1;
 
    int m = (s + e) / 2;
    if (segTree[node * 2] < x) {
        getTree(node * 2 + 1, m + 1, e, x - segTree[node * 2], i);
    }
    else {
        getTree(node * 2, s, m, x, i);
    }
}
 
int main()
{
    scanf("%d", &N);
    
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = 1; i <= N; i++) {
        getTree(1, 1, N, arr[i] + 1, i);
    }
 
    for (int i = 1; i <= N; i++) {
        printf("%d\n", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1615번 - 교차개수세기 (C++)  (0) 2023.01.21
[ 백준 ] 1777번 - 순열복원 (C++)  (0) 2023.01.20
[ 백준 ] 16975번 - 수열과 쿼리 21 (C++)  (0) 2023.01.18
[ 백준 ] 10999번 - 구간 합 구하기 2 (C++)  (0) 2023.01.17
[ 백준 ] 5676번 - 음주 코딩 (C++)  (0) 2023.01.15
반응형

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

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

 

10999번: 구간 합 구하기 2

첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 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. 세그먼트 트리와 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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, M, K;
ll arr[1000001];
ll segTree[2100000];
ll lazy[2100000];    //방문할 필요가 없는 노드의 경우 다음 방문 때 더할 값을 저장
 
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)    //현재 노드에 lazy 값이 있다면 더해주기
{
    if (lazy[node] != 0) {
        segTree[node] += (ll)(end - start + 1) * lazy[node];
        if (start != end) {    //리프 노드가 아니라면 아래 노드에 lazy값 물려주기
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
 
        lazy[node] = 0;
    }
}
 
void modifyTree(int node, int start, int end, int sidx, int eidx, ll d)
{
    modifyLazy(node, start, end);    //현재 노드에 lazy값 체크
 
    if (sidx > end || start > eidx) return;
 
    if (sidx <= start && end <= eidx) {    //완전히 포함된다면
        segTree[node] += (ll)(end - start + 1) * d;
        if (start != end) {    //리프 노드가 아닐 경우 아래 노드에 lazy값 물려주기
            lazy[node * 2] += d;
            lazy[node * 2 + 1] += d;
        }
        return;
    }
 
    int mid = (start + end) / 2;
    modifyTree(node * 2, start, mid, sidx, eidx, d);
    modifyTree(node * 2 + 1, mid+1, end, sidx, eidx, d);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
ll sumTree(int node, int start, int end, int sidx, int eidx)
{
    modifyLazy(node, start, end);    //현재 노드에 lazy값 체크
 
    if (start > eidx || end < sidx) return 0;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    ll left = sumTree(node * 2, start, mid, sidx, eidx);
    ll right = sumTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    scanf("%d %d %d", &N, &M, &K);
 
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < M + K; i++) {
        int a;
        scanf("%d", &a);
 
        if (a == 1) {
            int b, c;
            ll d;
            scanf("%d %d %lld", &b, &c, &d);
 
            modifyTree(1, 1, N, b, c, d);
        }
        else {
            int b, c;
            scanf("%d %d", &b, &c);
 
            printf("%lld\n", sumTree(1, 1, N, b, c));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1849번 - 순열 (C++)  (0) 2023.01.19
[ 백준 ] 16975번 - 수열과 쿼리 21 (C++)  (0) 2023.01.18
[ 백준 ] 5676번 - 음주 코딩 (C++)  (0) 2023.01.15
[ 백준 ] 18436번 - 수열과 쿼리 37 (C++)  (0) 2023.01.14
[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
반응형

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

 

5676번: 음주 코딩

각 테스트 케이스마다 곱셈 명령의 결과를 한 줄에 모두 출력하면 된다. 출력하는 i번째 문자는 i번째 곱셈 명령의 결과이다. 양수인 경우에는 +, 음수인 경우에는 -, 영인 경우에는 0을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합 대신 구간 곱을 return 합니다.

 

2. 구간 곱의 부호만 판단하면 되므로 입력받은 값이 양수이면 1, 음수이면 -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
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>
#include<cstring>
#include<vector>
 
using namespace std;
 
int N, K;
int arr[100001];
int segTree[263000];
vector<char>ans;
 
int invert(int num)
{
    if (num > 0) return 1;
    else if (num < 0) return -1;
    return 0;
}
 
int makeTree(int node, int start, int end)
{
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);
    int right = makeTree(node * 2 + 1, mid + 1, end);
 
    return segTree[node] = left * right;
}
 
int changeTree(int node, int start, int end, int idx, int V)
{
    if (idx < start || end < idx) return segTree[node];
    if (start == end) return segTree[node] = V;
 
    int mid = (start + end) / 2;
    int left = changeTree(node * 2, start, mid, idx, V);
    int right = changeTree(node * 2 + 1, mid + 1, end, idx, V);
 
    return segTree[node] = left * right;
}
 
int getTree(int node, int start, int end, int sidx, int eidx)
{
    if (start > eidx || end < sidx) return 1;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    int left = getTree(node * 2, start, mid, sidx, eidx);
    int right = getTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left * right;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    while (cin >> N >> K) {
        memset(segTree, 0, sizeof(segTree));
        ans.clear();
 
        for (int i = 1; i <= N; i++) {
            cin >> arr[i];
            arr[i] = invert(arr[i]);
        }
 
        makeTree(1, 1, N);
 
        for (int k = 0; k < K; k++) {
            char ch;
            cin >> ch;
 
            if (ch == 'C') {
                int i, V;
                cin >> i >> V;
 
                V = invert(V);
                changeTree(1, 1, N, i, V);
                arr[i] = V;
            }
            else {
                int i, j;
                cin >> i >> j;
 
                int temp = getTree(1, 1, N, i, j);
 
                if (temp < 0) ans.push_back('-');
                else if (temp > 0) ans.push_back('+');
                else ans.push_back('0');
            }
        }
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i];
        }
        cout << endl;
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 16975번 - 수열과 쿼리 21 (C++)  (0) 2023.01.18
[ 백준 ] 10999번 - 구간 합 구하기 2 (C++)  (0) 2023.01.17
[ 백준 ] 18436번 - 수열과 쿼리 37 (C++)  (0) 2023.01.14
[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
[ 백준 ] 2493번 - 탑 (C++)  (0) 2023.01.12
반응형

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

 

18436번: 수열과 쿼리 37

길이가 N인 수열 A1, A2, ..., AN이 있다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i x: Ai를 x로 바꾼다. 2 l r: l ≤ i ≤ r에 속하는 모든 Ai중에서 짝수의 개수를 출력한다. 3 l r: l ≤ i ≤

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합 대신 짝수와 홀수의 개수를 구해야 하므로 각 노드별로 짝수의 개수와 홀수의 개수를 저장해 return 합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
pair<int, int> segTree[263000];
int arr[100001];
 
pair<int, int> makeTree(int node, int start, int end)
{
    if (start == end) {
        if (arr[start] % 2 == 0) {
            return segTree[node] = { 0,1 };
        }
        else {
            return segTree[node] = { 1,0 };
        }
    }
 
    int mid = (start + end) / 2;
    pair<int, int> left = makeTree(node * 2, start, mid);
    pair<int, int> right = makeTree(node * 2 + 1, mid + 1, end);
 
    return segTree[node] = { left.first + right.first, left.second + right.second };
}
 
void modifyTree(int node, int start, int end, int idx, int odd, int even)
{
    if (idx < start || end < idx) return;
 
    segTree[node].first += odd;
    segTree[node].second += even;
 
    if (start != end) {
        int mid = (start + end) / 2;
        modifyTree(node * 2, start, mid, idx, odd, even);
        modifyTree(node * 2 + 1, mid + 1, end, idx, odd, even);
    }
}
 
int oddTree(int node, int start, int end, int sidx, int eidx)
{
    if (eidx < start || sidx > end) return 0;
    if (sidx <= start && end <= eidx) return segTree[node].first;
 
    int mid = (start + end) / 2;
    int left = oddTree(node * 2, start, mid, sidx, eidx);
    int right = oddTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left + right;
}
 
int evenTree(int node, int start, int end, int sidx, int eidx)
{
    if (eidx < start || sidx > end) return 0;
    if (sidx <= start && end <= eidx) return segTree[node].second;
 
    int mid = (start + end) / 2;
    int left = evenTree(node * 2, start, mid, sidx, eidx);
    int right = evenTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    scanf("%d", &M);
 
    for (int i = 0; i < M; i++) {
        int n, l, r;
        scanf("%d %d %d", &n, &l, &r);
 
        if (n == 1) {
            if (arr[l] % 2 == 0 && r % 2 != 0) {
                modifyTree(1, 1, N, l, 1, -1);
            }
            else if (arr[l] % 2 != 0 && r % 2 == 0) {
                modifyTree(1, 1, N, l, -1, 1);
            }
 
            arr[l] = r;
        }
        else if (n == 2) {
            printf("%d\n", evenTree(1, 1, N, l, r));
        }
        else {
            printf("%d\n", oddTree(1, 1, N, l, r));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10999번 - 구간 합 구하기 2 (C++)  (0) 2023.01.17
[ 백준 ] 5676번 - 음주 코딩 (C++)  (0) 2023.01.15
[ 백준 ] 14427번 - 수열과 쿼리 15 (C++)  (0) 2023.01.13
[ 백준 ] 2493번 - 탑 (C++)  (0) 2023.01.12
[ 백준 ] 13975번 - 파일 합치기 3 (C++)  (0) 2023.01.11
반응형

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

 

14427번: 수열과 쿼리 15

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 : 수열에서 크기가 가장 작은 값의 인덱스를 

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합 대신 최솟값의 index를 구해야 하므로 왼쪽 노드와 오른쪽 노드 중 더 작은 값의 index return 해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
int arr[100001];
pair<int, int> segTree[263000];
 
pair<int, int> makeTree(int node, int start, int end)
{
    if (start == end)return segTree[node] = { arr[start], start };
 
    int mid = (start + end) / 2;
    pair<int, int> left = makeTree(node * 2, start, mid);
    pair<int, int> right = makeTree(node * 2 + 1, mid + 1, end);
 
    if (left <= right) {
        return segTree[node] = left;
    }
    else {
        return segTree[node] = right;
    }
}
 
pair<int, int> modifyTree(int node, int start, int end, int i, int v)
{
    if (i < start || end < i) return segTree[node];
    if (start == end) return segTree[node] = { arr[start], start };
 
    int mid = (start + end) / 2;
    pair<int, int> left = modifyTree(node * 2, start, mid, i, v);
    pair<int, int> right = modifyTree(node * 2 + 1, mid + 1, end, i, v);
 
    if (left <= right) {
        return segTree[node] = left;
    }
    else {
        return segTree[node] = right;
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    scanf("%d", &M);
 
    for (int m = 0; m < M; m++) {
        int n;
        scanf("%d", &n);
 
        if (n == 1) {
            int i, v;
            scanf("%d %d", &i, &v);
            arr[i] = v;
 
            modifyTree(1, 1, N, i, v);
        }
        else {
            printf("%d\n", segTree[1].second);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5676번 - 음주 코딩 (C++)  (0) 2023.01.15
[ 백준 ] 18436번 - 수열과 쿼리 37 (C++)  (0) 2023.01.14
[ 백준 ] 2493번 - 탑 (C++)  (0) 2023.01.12
[ 백준 ] 13975번 - 파일 합치기 3 (C++)  (0) 2023.01.11
[ 백준 ] 16118번 - 달빛 여우 (C++)  (0) 2023.01.10
반응형

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

 

1275번: 커피숍2

첫째 줄에 수의 개수 N과 턴의 개수 Q가 주어진다.(1 ≤ N, Q ≤ 100,000) 둘째 줄에는 처음 배열에 들어가 있는 정수 N개가 주어진다. 세 번째 줄에서 Q+2번째 줄까지는 x y a b의 형식으로 x~y까지의 합

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합의 크기가 int 범위를 벗어나므로 long long 자료형을 사용해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
int N, Q;
ll arr[100001];
ll segTree[263000];
 
ll makeTree(ll node, ll start, ll end)
{
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    ll left = makeTree(node * 2, start, mid);
    ll right = makeTree(node * 2 + 1, mid + 1, end);
 
    return segTree[node] = right + left;
}
 
void modifyTree(ll node, ll start, ll end, ll a, ll diff)
{
    if (a < start || a > end) return;
    segTree[node] += diff;
 
    if (start != end) {
        int mid = (start + end) / 2;
        modifyTree(node * 2, start, mid, a, diff);
        modifyTree(node * 2 + 1, mid + 1, end, a, diff);
    }
}
 
ll sumTree(ll node, ll start, ll end, ll x, ll y)
{
    if (y < start || x > end) return 0;
    if (x <= start && end <= y) return segTree[node];
 
    int mid = (start + end) / 2;
    ll left = sumTree(node * 2, start, mid, x, y);
    ll right = sumTree(node * 2 + 1, mid + 1, end, x, y);
 
    return left + right;
}
 
int main()
{
    scanf("%d %d", &N, &Q);
 
    for (int i = 1; i <= N; i++) {
        scanf("%lld", &arr[i]);
    }
 
    makeTree(1,1,N);
 
    for (int i = 0; i < Q; i++) {
        ll x, y, a, b;
        scanf("%lld %lld %lld %lld", &x, &y, &a, &b);
        if (y < x) {
            ll temp = x;
            x = y;
            y = temp;
        }
        ll diff = b - arr[a];
        arr[a] = b;
        printf("%lld\n", sumTree(1, 1, N, x, y));
        modifyTree(1, 1, N, a, diff);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2470번 - 두 용액 (C++)  (0) 2023.01.07
[ 백준 ] 17141번 - 연구소 2 (C++)  (0) 2023.01.06
[ 백준 ] 10868번 - 최솟값 (C++)  (0) 2023.01.04
[ 백준 ] 3745번 - 오름 (C++)  (0) 2023.01.03
[ 백준 ] 14438번 - 수열과 쿼리 17 (C++)  (0) 2023.01.02
반응형

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

 

10868번: 최솟값

N(1 ≤ N ≤ 100,000)개의 정수들이 있을 때, a번째 정수부터 b번째 정수까지 중에서 제일 작은 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 a, b의 쌍이 M(1 ≤ M ≤ 100,000)개 주어졌을 때는

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합 대신 최솟값을 구해야 하므로 왼쪽 노드와 오른쪽 노드 중 더 작은 값을 return 해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N, M;
int arr[100001];
int segTree[263000];
 
int makeTree(int node, int start, int end)
{
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);
    int right = makeTree(node * 2 + 1, mid + 1, end);
 
    if (left < right) {
        return segTree[node] = left;
    }
    else {
        return segTree[node] = right;
    }
}
 
int getTree(int node, int start, int end, int sidx, int eidx)
{
    if (end < sidx || start > eidx) return 1987654321;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    int left = getTree(node * 2, start, mid, sidx, eidx);
    int right = getTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    if (left < right) {
        return left;
    }
    else {
        return right;
    }
}
 
int main()
{
    scanf("%d %d", &N, &M);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        printf("%d\n", getTree(1, 1, N, a, b));
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17141번 - 연구소 2 (C++)  (0) 2023.01.06
[ 백준 ] 1275번 - 커피숍2 (C++)  (0) 2023.01.05
[ 백준 ] 3745번 - 오름 (C++)  (0) 2023.01.03
[ 백준 ] 14438번 - 수열과 쿼리 17 (C++)  (0) 2023.01.02
[ 백준 ] 12837번 - 가계부 (Hard) (C++)  (0) 2023.01.01
반응형

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

 

14438번: 수열과 쿼리 17

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v : Ai를 v로 바꾼다. (1 ≤ i ≤ N, 1 ≤ v ≤ 109) 2 i j : Ai, Ai+1, ..., Aj에서 크기가 가장 작은 값을

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/51

 

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

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

rudalsd.tistory.com

 

1. 구간 합 대신 최솟값을 구해야 하므로 왼쪽 노드와 오른쪽 노드 중 더 작은 값을 return 해줍니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int segTree[263000];
int arr[100001];
int N, M;
 
int makeTree(int node, int start, int end)
{
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    int left = makeTree(node * 2, start, mid);
    int right = makeTree(node * 2 + 1, mid + 1, end);
 
    if (right < left) {
        segTree[node] = right;
        return right;
    }
    else {
        segTree[node] = left;
        return left;
    }
}
 
int getTree(int node, int start, int end, int sidx, int eidx)
{
    if (start > eidx || end < sidx) return 1987654321;
    if (sidx <= start && end <= eidx) return segTree[node];
 
    int mid = (start + end) / 2;
    int left = getTree(node * 2, start, mid, sidx, eidx);
    int right = getTree(node * 2 + 1, mid + 1, end, sidx, eidx);
 
    if (left < right) {
        return left;
    }
    else {
        return right;
    }
}
 
int modifyTree(int node, int start, int end, int idx, int v)
{
    if (idx > end || idx < start) return segTree[node];
    if (start == end) return segTree[node] = arr[start];
 
    int mid = (start + end) / 2;
    int left = modifyTree(node * 2, start, mid, idx, v);
    int right = modifyTree(node * 2 + 1, mid + 1, end, idx, v);
 
    if (left < right) {
        segTree[node] = left;
        return left;
    }
    else {
        segTree[node] = right;
        return right;
    }
}
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
    }
 
    makeTree(1, 1, N);
 
    scanf("%d", &M);
 
    for (int m = 0; m < M; m++) {
        int n;
        scanf("%d", &n);
 
        if (n == 1) {
            int i, v;
            scanf("%d %d", &i, &v);
            arr[i] = v;
            modifyTree(1, 1, N, i, v);
        }
        else {
            int i, j;
            scanf("%d %d", &i, &j);
            printf("%d\n", getTree(1, 1, N, i, j));
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 10868번 - 최솟값 (C++)  (0) 2023.01.04
[ 백준 ] 3745번 - 오름 (C++)  (0) 2023.01.03
[ 백준 ] 12837번 - 가계부 (Hard) (C++)  (0) 2023.01.01
[ 백준 ] 17244번 - 아맞다우산 (C++)  (0) 2022.12.31
[ 백준 ] 17497번 - 계산 (C++)  (0) 2022.12.30

+ Recent posts

티스토리툴바