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


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*N
const 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 1
treap 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 <= x
int 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;
}