[백준 13544] 수열과 쿼리 3

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

 

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.

• i j k: Ai, Ai+1, ..., Aj로 이루어진 부분 수열 중에서 k보다 큰 원소의 개수를 출력한다.

 

문제 조건에 "넷째 줄부터 M개의 줄에는 a, b, c가 주어진다. a, b, c를 이용해 쿼리를 만들어야 한다." 라는 조건 때문에 이전 값의 결과가 다음 값에 영향을 끼치니 오프라인 쿼리로는 처리할 수 없다.

 

수열과 쿼리 1(https://www.acmicpc.net/problem/13537)문제와 푸는 알고리즘은 동일하다

 

k보다 큰 원소의 수 = 정렬 후 upper_bound를 이용한다

 

세그먼트 트리를 구성 할 때 각 구간의 원소를 vector로 가지는 세그먼트 트리를 만들었는데 찾다 보니 그게 머지 소트 트리라는 자료구조였다.

 

#include "iostream"
#include "algorithm"
#include "vector"
#include "map"
#pragma GCC optimize ("O3")
#pragma GCC optimize ("Ofast")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

using namespace std;
int arr[100001];
vector<int> segTree[262144];

int N, M;
void makeSegTree(int start, int end, int idx);
int find(int start, int end, int idx, int left, int right, int target);
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> N;
    for(int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
    makeSegTree(1, N, 1);
    cin >> M;
    int res = 0;
    for(int q = 0; q < M; q++) {
        int a, b, c; cin >> a >> b >> c;
        res = find(1, N, 1, a ^ res, b ^ res, c ^ res);
        cout << res << '\n';
    }
}
void makeSegTree(int start, int end, int idx) {
    if(start == end) {
        segTree[idx].push_back(arr[start]);
        return;
    }
    int mid = (end + start) / 2;
    makeSegTree(start, mid, idx << 1);
    makeSegTree(mid + 1, end, idx << 1 | 1);
    segTree[idx].insert(segTree[idx].end(), segTree[idx << 1].begin(), segTree[idx << 1].end());
    segTree[idx].insert(segTree[idx].end(), segTree[idx << 1 | 1].begin(), segTree[idx << 1 | 1].end());
    sort(segTree[idx].begin(), segTree[idx].end());
}
int find(int start, int end, int idx, int left, int right, int target) {
    if(right < start || end < left) {
        return 0;
    }
    if(left <= start && end <= right) {
        int t = upper_bound(segTree[idx].begin(), segTree[idx].end(), target) - segTree[idx].begin();
        return segTree[idx].size() - t;
    }

    int mid = (start + end) / 2;
    return find(start, mid, idx << 1, left, right, target) + find(mid + 1, end, idx << 1 | 1, left, right, target);
}