[C++] 13537번 수열과 쿼리 1 - 자료 구조, 정렬, 세그먼트 트리, 머지 소트 트리

13544번과 문제가 비슷하여 함께 풀이됩니다.

1. 문제

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

<입력>

• -1-   수열의 크기 $N(1\le N\le 100,000)$
• -2-   Ai가 주어진다. $(1\le A_i\le {10}^9)$
• -3-   쿼리의 개수 $M(1\le M\le 100,000)$
• -M개-   쿼리 i, j, k $(1\le i\le j\le N,1\le k\le {10}^9)$

<출력>

• 각각의 쿼리마다 한 줄에 하나씩 정답을 출력한다.

2. 재정의

• $A_n(i\le n\le j)$수열 중 k보다 큰 원소 개수 구하기

3. 해결방법

• 세그먼트 트리(머지 소트 트리) 구현
• upper_bound()로 query 수행하기

4. 실수한 점, 개선할 점

• 병합정렬을 수행할 때 merge() 함수를 사용할 시 vector의 크기가 이미 정의되어 있어야 runtime error를 발생하지 않는다.
• upper_bound는 k이상인 iterator를 반환하는 것이 아닌 k보다 큰 수의 iterator를 반환한다.
• init() 함수를 할 때 tr[no*2]와 tr[no*2+1]에 이미 저장되므로 vector<int>형을 반환할 필요 없이 void로 할 수 있고 이 경우 소요 시간이 개선된다.
• 원소 개수를 구할 대 .end() - upper_bound()를 해주면 소요 시간이 개선된다.
• ll형이 필요하지 않고 int형을 사용하면 형 변환 과정이 없어 소요 시간이 개선된다.

 

<코드>

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAX_N = 100001;
const int MAX_TR = 400001;

// 수열의 크기 N과, 수열 A[i]
int N;
int A[MAX_N];
// 쿼리의 개수 M
int M;
// 찾으려는 값 k
int k;

// 머지 소트 트리
vector<int> tr[MAX_TR];

// 머지 소트 트리 구현
void init(int s, int e, int no) {
    if(s==e)
        tr[no].push_back(A[s]);
    else {
        int m = (s+e)/2;
        init(s, m, no*2), init(m+1, e, no*2+1);
        tr[no].resize(e-s+1);
        merge(tr[no*2].begin(), tr[no*2].end(), tr[no*2+1].begin(), tr[no*2+1].end(), tr[no].begin());
    }
}

// 쿼리 계산
int query(int s, int e, int no, int l, int r) {
    if(l>e || r<s) return 0;
    if(l<=s && e<=r)
        return tr[no].end() - upper_bound(tr[no].begin(), tr[no].end(), k);
    int m = (s+e)/2;
    return query(s, m, no*2, l, r) + query(m+1, e, no*2+1, l, r);
}

void input() {
    cin >> N;
    for(int i=1; i<=N; i++)
        cin >> A[i];
    cin >> M;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    // 머지 소트 트리 구현
    init(1, N, 1);
    
    for(int i=0; i<M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        k = c;
        
        cout << query(1, N, 1, a, b) << '\n';
    }
    
    return 0;
}

 

 

<머지 소트 트리(merge sort tree)>

https://seungwuk98.tistory.com/41

[PS를 위한 자료구조 9강] 머지 소트 트리의 개념과 구현

 

<merge() 함수>

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=kks227&logNo=220404011875 

[C++ 강좌] 103 - 알고리즘 헤더 파일 (12) - merge(), set_union(), set_intersection(), set_difference(), set_symmetric_d

 

<upper_bound() 함수>

https://blockdmask.tistory.com/168

[탐색] lower_bound, upper_bound

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.