HackerEarth XOR queries problem solution YASH PAL, 31 July 2024 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 i x: Change the value of Ai to x 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("%dn", ans); } } cerr << "time taken = " << clock()/(double)CLOCKS_PER_SEC << endl;} coding problems