13544번: 수열과 쿼리 3

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


$O(n{\lg n}^2)$

세그먼트 트리를 이용한다.(bit를 이용해도 된다.)
구간 [l,r]에 해당하는 서브트리의 루트 노드를 h라 하면
h는 [l,(l+r)/2], [(l+r)/2+1,r] 구간에 해당하는 서브트리의 루트 노드를 자식으로 가지며 수열 a[l...r]을 오름차순 정렬하여 가지게 만든다.
(i,j,k) 쿼리가 들어 오면
해당 구간의 노드마다 upper_bound를 이용하여 k보다 큰 원소의 개수를 합해준다.

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int n, m;
vector<int> t[400000];
void insert(int h, int l, int r, int g, int x) {
    if (r < g || g < l) return;
    t[h].push_back(x);
    if (l^r) insert(h * 2 + 1, l, (l + r) / 2, g, x), insert(h * 2 + 2, (l + r) / 2 + 1, r, g, x);
}
int count(int h, int l, int r, int gl, int gr, int x) {
    if (r < gl || gr < l) return 0;
    if (gl <= l && r <= gr) return t[h].end() - upper_bound(t[h].begin(), t[h].end(), x);
    return count(h * 2 + 1, l, (l + r) / 2, gl, gr, x) + count(h * 2 + 2, (l + r) / 2 + 1, r, gl, gr, x);
}
int main() {
    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++) scanf("%d", &x), insert(0, 1, n, i, x);
    for (int i = 0; i < n * 4; i++) sort(t[i].begin(), t[i].end());
    scanf("%d", &m);
    for (int i = 0, x, y, z, r = 0; i < m; i++) {
        scanf("%d%d%d", &x, &y, &z);
        r = count(0, 1, n, x^r, y^r, z^r);
        printf("%d\n", r);
    }
    return 0;
}