HackerEarth XOR queries problem solution

In this HackerEarth XOR queries problem solution You are given a 1indexed array A, of length n, and q queries to be performed on it. The queries are of two types
1. i x: Change the value of Ai to x
2. L R I J: Find l, r, i, and j according to the code below. Consider the subarray B = [Al, Al+1 ... Ar]. Sort B, and find the Bitwise xor of Bi, Bi+1...Bj in the sorted array B.

HackerEarth XOR queries problem solution.

`#include <bits/stdc++.h>using namespace std;#define ll long long#define pii pair<int, int>#define mp make_pair#define F first#define S second#define sd(x) scanf("%d", &(x))#define print(s) cerr<<#s<<" : ";for(auto i:(s))cerr<<i<<" ";cerr<<"\n";#include <ext/pb_ds/assoc_container.hpp>#include <ext/pb_ds/tree_policy.hpp>using namespace __gnu_pbds;#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>// N is max insert operations. Memory: 4*Nconst int N = 3e6+10;//key acc to heap, value acc to BT, 0 represents NULLPO int lft[N], rgt[N], value[N], XOR[N], cnt = 0;unsigned key[N];static unsigned generate_key() {    static unsigned x = 123456789, y = 362436069, z = 521288629, w = 88675123;    unsigned t = x ^ x<<11;    x = y; y = z; z = w;    return w = w ^ w>>19 ^ t ^ t>>8;}inline void fix(int x){XOR[x] = value[x] ^ XOR[lft[x]] ^ XOR[rgt[x]];}struct treap{    int root;    treap(){root = 0;}    int merge(int L, int R){        if(L == 0){ fix(R); return R;}        if(R == 0){ return L;}        if(key[L] > key[R]){ rgt[L] = merge(rgt[L], R), fix(L); }        else{ lft[R] = merge(L, lft[R]); fix(R);}        return (key[L] > key[R]) ? L : R;    }    pii split(int T, int X){        if(T == 0) return mp(0,0);        if(value[T] <= X){            pii P = split(rgt[T], X);            rgt[T] = P.F; fix(T);            return mp(T, P.S);        }        pii P = split(lft[T], X);        lft[T] = P.S; fix(T);        return mp(P.F, T);    }    int find(int rt, int X){        if(rt == 0 || value[rt] == X) return rt;        if(value[rt] < X) return find(rgt[rt], X);        return find(lft[rt], X);    }    int find(int X){ return find(root, X);}    void insert(int X){        if(find(X)) return;        key[++cnt] = generate_key(); value[cnt] = XOR[cnt] = X;        pii P = split(root, X);        int L = merge(P.F, cnt);        root = merge(L, P.S);    }    void erase(int rt, int up, int x){        if(rt == 0) return;        XOR[rt] ^= x;        if(value[rt] == x){            if(up == 0) root = merge(lft[rt], rgt[rt]);            else if(lft[up] == rt) lft[up] = merge(lft[rt], rgt[rt]);            else rgt[up] = merge(lft[rt], rgt[rt]);            return;         }        if(value[rt] > x) erase(lft[rt], rt, x);        else erase(rgt[rt], rt, x);    }    void erase(int x){ if(!find(x)) return; erase(root, 0, x);}    int xorval(int rt, int x){        if(rt == 0) return 0;        if(value[rt] <= x) return XOR[lft[rt]] ^ value[rt] ^ xorval(rgt[rt], x);        return xorval(lft[rt], x);    }    int xorval(int x){return xorval(root, x);}};const int M = 100005, _M = 50005;int a[3 * M], inva[3 * M];ordered_set tree1[3 * M];// root at 1treap T[3 * M];int maxind = 0;void make(int s = 1, int e = M, int ind = 1){    if(s == e){        if(inva[s]) tree1[ind].insert(inva[s]);        return;    }    int mid = (s + e) >> 1;    make(s, mid, ind << 1); make(mid + 1, e, (ind << 1) + 1);    tree1[ind] = tree1[(ind << 1) + 1];    for(int v : tree1[ind << 1]) tree1[ind].insert(v);}void adddel(int b, int x, int i, int s = 1, int e = M, int ind = 1){    if(s > x || e < x) return;    if(b) tree1[ind].insert(i);    else tree1[ind].erase(i);    if(s == e) return;    int mid = (s + e) >> 1;    adddel(b, x, i, s, mid, ind << 1);    adddel(b, x, i, mid + 1, e, (ind << 1) + 1);}int kth_in_range(int k, int l, int r, int ind = 1, int s = 1, int e = M){    if(s == e) return s;    maxind = max(maxind, ind << 1);    int left = tree1[ind << 1].order_of_key(r + 1) - tree1[ind << 1].order_of_key(l);    int mid = (s + e) >> 1;    if(left < k) return kth_in_range(k - left, l, r, (ind << 1) + 1, mid + 1, e);    return kth_in_range(k, l, r, ind << 1, s, mid);}void adddel2(int b, int i, int x, int s = 1, int e = _M, int ind = 1){    if(s > i || e < i) return;    if(b) T[ind].insert(x);    else T[ind].erase(x);    if(s == e) return;    int mid = (s + e) >> 1;    adddel2(b, i, x, s, mid, ind << 1);    adddel2(b, i, x, mid + 1, e, (ind << 1) + 1);}// get xor of all elements in [l,r] with value <= xint getXOR(int l, int r, int x, int s = 1, int e = _M, int ind = 1){    if(l > e || s > r) return 0;    if(l <= s && e <= r) return T[ind].xorval(x);    int mid = (s + e) >> 1;    return getXOR(l, r, x, s, mid, ind << 1) ^ getXOR(l, r, x, mid + 1, e, (ind << 1) + 1);}void update(int i, int x){    int y = a[i];    adddel(0, y, i); adddel(1, x, i);    adddel2(0, i, y); adddel2(1, i, x);    a[i] = x; inva[a[i]] = i;}int query(int l, int r, int i, int j){    int x = kth_in_range(i, l, r), y = kth_in_range(j, l, r);    return getXOR(l, r, x - 1) ^ getXOR(l, r, y);}int main(){    int n = 50000, q = 50000, type, l, r, L, R, I, J, x, i, j;    sd(n); sd(q);     assert(n <= 50000); assert(q <= 50000);    for(i = 1; i <= n; i++){        // a[i] = get_new();         sd(a[i]);    }    for(i = 1; i <= n; i++) inva[a[i]] = i, adddel2(1, i, a[i]);    make();     int ans = 0;    while(q--){        sd(type);        if(type == 1){            sd(l), sd(x);            update(l, x);        }        else{            scanf("%d %d %d %d", &L, &R, &I, &J);            l = 1 + ((ans ^ L) % n);            r = 1 + ((ans ^ R) % n);            if(l > r) swap(l, r);            i = 1 + ((I ^ ans) % (r - l + 1));            j = 1 + ((J ^ ans) % (r - l + 1));            if(i > j) swap(i, j);             assert(1 <= l && l <= r && r <= n);            assert(1 <= i && i <= j && j <= r - l + 1);            // cerr << l << " " << r << " " << i << " " << j << endl;            ans = query(l, r, i, j);            printf("%d\n", ans);        }    }    cerr << "time taken = " << clock()/(double)CLOCKS_PER_SEC << endl;}`