1771F - Hossam and Range Minimum Query - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f;
const int N = 2e5 + 10;

struct Node
{
	int l, r;
	ULL val;
}tr[N * 40];
int rt[N], cnt;

mt19937_64 sj(random_device{}());
map<int, ULL> mp;

int insert(int p, int l, int r, int x, ULL v)
{
	int q = ++ cnt;
	tr[q] = tr[p];
	tr[q].val ^= v;
	if(l == r) return q;
	int mid = l + r >> 1;
	if(x <= mid) tr[q].l = insert(tr[p].l, l, mid, x, v);
	else tr[q].r = insert(tr[p].r, mid + 1, r, x, v);
	return q;
}

int query(int q, int p, int l, int r)
{
	if(l == r) return l;
	int mid = l + r >> 1;
	if((tr[tr[q].l].val ^ tr[tr[p].l].val) != 0)
		return query(tr[q].l, tr[p].l, l, mid);
	else return query(tr[q].r, tr[p].r, mid + 1, r);
}

void solve()
{
	int n;
	cin >> n;
	const int rli = 1e9;
	for(int i = 1, x; i <= n; i ++)
	{
		cin >> x;
		while(mp[x] == 0) mp[x] = sj();
		rt[i] = insert(rt[i - 1], 0, rli, x, mp[x]);
	}
	int q;
	cin >> q;
	int ans = 0;
	while(q --)
	{
		int l, r;
		cin >> l >> r;
		l ^= ans, r ^= ans;
		if(((tr[rt[r]].val) ^ (tr[rt[l - 1]].val)) == 0) ans = 0;
		else ans = query(rt[r], rt[l - 1], 0, rli);
		cout << ans << "\n";
	}
}

signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("data.in", "r", stdin);
	int T = 1;
    while(T --) solve();
	return 0;
}