반응형

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

 

13537번: 수열과 쿼리 1

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

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

https://rudalsd.tistory.com/462

 

[ 자료구조 ] 머지 소트 트리(Merge Sort Tree)

1. 머지 소트 트리(Merge Sort Tree) 머지 소트 트리(Merge Sort Tree)는 분할 정복을 활용하는 합병 정렬(Merge Sort)을 저장하는 자료구조 입니다. 2. 머지 소트 트리(Merge Sort Tree) 동작 원리 머지 소트 트리(Me

rudalsd.tistory.com

 

1. 수열을 입력받고, 머지 소트 트리를 구현합니다.

 

2. 해당 구간에 대해 upper_bound를 활용하여, 해당 구간의 값 중 k보다 큰 값을 ans에 저장합니다.

 

3. 쿼리마다 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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
vector<int> mergeSortTree[262222];
int arr[100001];
int ans;
 
void merge(int node, int s, int e) {
    int s_size = mergeSortTree[node * 2].size();
    int e_size = mergeSortTree[node * 2 + 1].size();
    int i = 0;
    int j = 0;
    while (1) {
        if (mergeSortTree[node * 2][i] < mergeSortTree[node * 2 + 1][j]) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i++]);
        }
        else {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j++]);
        }
 
        if (i == s_size || j == e_size) {
            break;
        }
    }
 
    if (i == s_size) {
        for (j; j < e_size; j++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j]);
        }
    }
    else {
        for (i; i < s_size; i++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i]);
        }
    }
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        mergeSortTree[node].push_back(arr[s]);
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    merge(node, s, e);
}
 
void getTree(int node, int s, int e, int i, int j, int k)
{
    if (e < i || j < s) return;
    if (i <= s && e <= j) {
        ans += mergeSortTree[node].end() - upper_bound(mergeSortTree[node].begin(), mergeSortTree[node].end(), k);
        return;
    }
 
    int m = (s + e) / 2;
    getTree(node * 2, s, m, i, j, k);
    getTree(node * 2 + 1, m + 1, e, i, j, k);
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    cin >> M;
 
    for (int a = 0; a < M; a++) {
        int i, j, k;
        cin >> i >> j >> k;
        ans = 0;
 
        getTree(1, 1, N, i, j, k);
 
        cout << ans << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 3079번 - 입국심사 (C++)  (0) 2023.08.10
[ 백준 ] 18114번 - 블랙 프라이데이 (C++)  (0) 2023.08.09
[ 백준 ] 2465번 - 줄 세우기 (C++)  (0) 2023.08.06
[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
반응형

1. 머지 소트 트리(Merge Sort Tree)

 

머지 소트 트리(Merge Sort Tree)는 분할 정복을 활용하는 합병 정렬(Merge Sort)을 저장하는 자료구조 입니다.

 

2. 머지 소트 트리(Merge Sort Tree) 동작 원리

머지 소트 트리(Merge Sort Tree)는 각 노드에서 해당 노드에 포함된 모든 원소들을 정렬한 상태로 저장하는 트리입니다.

머지 소트 트리(Merge Sort Tree)는 아래와 같이 구성되어 있습니다.

 

1 2 3 4 5 6 7 8
1 2 5 6  3 4 7 8 
1 5 2 6 3 7 4 8
1 5 2 6 3 7 4 8

 

3. 머지 소트 트리(Merge Sort Tree) 구현

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
void merge(int node, int s, int e) {
    int s_size = mergeSortTree[node * 2].size();
    int e_size = mergeSortTree[node * 2 + 1].size();
    int i = 0;
    int j = 0;
    while (1) {
        if (mergeSortTree[node * 2][i] < mergeSortTree[node * 2 + 1][j]) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i++]);
        }
        else {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j++]);
        }
 
        if (i == s_size || j == e_size) {
            break;
        }
    }
 
    if (i == s_size) {
        for (j; j < e_size; j++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j]);
        }
    }
    else {
        for (i; i < s_size; i++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i]);
        }
    }
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        mergeSortTree[node].push_back(arr[s]);
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    merge(node, s, e);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 자료구조 ] 트라이(Trie)  (0) 2023.06.24
[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)  (0) 2023.05.04
[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)  (0) 2023.01.16
[ 자료구조 ] 희소 배열(Sparse Table)  (0) 2022.08.07
[ 자료구조 ] 세그먼트 트리 (Segment Tree)  (0) 2022.07.02

+ Recent posts

티스토리툴바