Header Ad

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


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;
}


Post a Comment

0 Comments