백준 13544 - 수열과 쿼리 3

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

 

특정 구간에서 어떤 원소를 상대로 질의를 처리하는 것은 머지 소트 트리를 이용하여 할 수 있다.

 

머지 소트 트리를 구현한 후 문제에서 요구하는 대로 질의를 처리한 결과를 출력하면 AC를 받을 수 있다.

 

마지막으로 출력한 결과와 XOR 연산을 해줘야 하는 것을 잊지 말자.

 

# XOR를 해주는 이유는 오프라인 쿼리를 사용할 수 없게 하기 위함이라고 한다.

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

vector<int> tree[400000];
int ar[100001];

int mid(int s, int e) { return s + (e - s) / 2; }

void init(int node, int start, int end)
{
    vector<int> &cur = tree[node];

    if (start == end)
    {
        cur.push_back(ar[start]);
        return;
    }
    
    int m = mid(start, end);

    init(node * 2, start, m);
    init(node * 2 + 1, m + 1, end);

    vector<int> &l = tree[node * 2], &r = tree[node * 2 + 1];
    cur.resize(l.size() + r.size());
    merge(l.begin(), l.end(), r.begin(), r.end(), cur.begin());
}

int query(int node, int start, int end, int l, int r, int val)
{
    if (end < l || start > r) return 0;
    vector<int> &cur = tree[node];
    if (l <= start && end <= r)
        return cur.end() - upper_bound(cur.begin(), cur.end(), val);
    
    int m = mid(start, end);

    return query(node * 2, start, m, l, r, val) + query(node * 2 + 1, m + 1, end, l, r, val);
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> ar[i];
    init(1, 1, n);
    
    int q;
    cin >> q;

    int last_ans = 0;

    while (q--)
    {
        int go, to, val;
        cin >> go >> to >> val;

        go ^= last_ans, to ^= last_ans, val ^= last_ans;
        last_ans = query(1, 1, n, go, to, val);

        cout << last_ans << '\n';
    }
}