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

13537번 수열과 쿼리 1과 문제가 비슷해서 함께 풀이됩니다.

<코드>

#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);
    
    int ans=0;
    for(int i=0; i<M; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        
        a ^= ans;
        b ^= ans;
        c ^= ans;
        
        k = c;
        
        cout << (ans = query(1, N, 1, a, b)) << '\n';
    }
    
    return 0;
}

 

 

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