반응형

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

 

13544번: 수열과 쿼리 3

길이가 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. a, b, c를 입력받고 pre에 xor 한 후 그 값을 이용하여 해당 구간에 대해 upper_bound를 활용하여, 해당 구간의 값 중 k보다 큰 값을 ans에 저장합니다.

 

3. ans를 출력하고, pre에 ans를 저장한 후 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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N, M;
vector<int> mergeSortTree[262222];
int arr[100001];
int ans;
int pre;
 
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, 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 (i; i < s_size; i++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2][i]);
        }
    }
    else {
        for (j; j < e_size; j++) {
            mergeSortTree[node].push_back(mergeSortTree[node * 2 + 1][j]);
        }
    }
}
 
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 (s > j || e < i) 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;
 
    while (M--) {
        int a, b, c;
        cin >> a >> b >> c;
 
        ans = 0;
 
        a ^= pre;
        b ^= pre;
        c ^= pre;
 
        getTree(1, 1, N, a, b, c);
 
        cout << ans << '\n';
 
        pre = ans;
    }
}
cs
반응형
저작자표시 비영리 변경금지

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

[ 백준 ] 19591번 - 독특한 계산기 (C++)  (0) 2023.10.18
[ 백준 ] 14699번 - 관악산 등산 (C++)  (1) 2023.10.17
[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
[ 백준 ] 1737번 - Pibonacci (C++)  (0) 2023.10.14
[ 백준 ] 25498번 - 핸들 뭘로 하지 (C++)  (0) 2023.10.13

+ Recent posts

티스토리툴바