Merge Sort Tree

/*
    Author : M. A. Rafsan Mazumder
    *** Merge Sort Tree (Segment Tree with vectors) ***
    Time and Space Complexity (Build) : O(nlogn)
    For point update, policy based data structure is needed - Build Complexity : O(n * (logn)^2)
                                                             Update : O((logn)^2)
    Code : Count the numbers of elements greater than a given value(k) in a range(i, j)
    Problem : http://www.spoj.com/problems/KQUERYO/
    Query Complexity : O((logn)^2)
*/

#include <bits/stdc++.h>

using namespace std;

#define MAX 30005
int arr[MAX], n, q;
vector<int> tree[4*MAX];

vector<int> mergeAll(vector<int> V1, vector<int> V2)
{
    vector<int> V( (int)V1.size()+(int)V2.size() ); // Preallocate Memory
    merge(V1.begin(), V1.end(), V2.begin(), V2.end(), V.begin());
    return V;
}

void init(int node, int b, int e)
{
    if(b == e){
        tree[node].push_back(arr[b]);
        return;
    }
    int left = 2*node;
    int right = 2*node+1;
    int mid = (b+e)/2;
    init(left, b, mid);
    init(right, mid+1, e);
    tree[node] = mergeAll(tree[left], tree[right]);
}

int query(int node, int b, int e, int l, int r, int val)
{
    if(l > r) return 0;
    if(l > e || r < b) return 0;
    if(b >= l && e <= r){
        int it = upper_bound(tree[node].begin(), tree[node].end(), val) - tree[node].begin();
        int cnt = tree[node].size() - it;
        return cnt;
    }
    int left = 2*node;
    int right = 2*node+1;
    int mid = (b+e)/2;
    int p1 = query(left, b, mid, l, r, val);
    int p2 = query(right, mid+1, e, l, r, val);
    return p1+p2;
}

int main()
{
    scanf("%d", &n);
    for(int i=1; i<=n; i++) scanf("%d", &arr[i]);
    init(1, 1, n);
    int last = 0;
    scanf("%d", &q);
    while(q--){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        int i = a^last, j = b^last, k = c^last;
        i = max(i, 1);
        j = min(j, n);
        last = query(1, 1, n, i, j, k);
        printf("%d\n", last);
    }
}