526互联

Codeforces Round 837 (Div. 2) F. Hossam and Range Minimum Query

发布时间 2023-05-25 18:14:01作者: qdhys

传送门

大致题意：

   给一个n，然后给一个数组a， 有m个询问，询问区间[l, r]出现次数为奇数的最小值，若没有输出0， 每次输入的l，r需要异或上上一个答案，在第一个询问的时候认为上一个答案为0

解题思路：

  1. 

#include <bits/stdc++.h>
#include <chrono>
#include <random>
#include <ctime>
const int N = 2e5 + 10;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
using ll = long long;
using ull = unsigned long long;
using namespace std;
mt19937_64 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l, ll r) {    
	ll f = r - l + 1;    
	return rng() % f + l;
}

mt19937_64 sj(random_device{}());

int n, m, timedelta;
int a[N];
std::map<int, ull> mp;
std::map<ull, int> id;

int root[N];

int L[N << 6], R[N << 6], idx;
ull xr[N << 6]; 

inline void insert(int &p, int q, int l, int r, int x, ull v) {
	p = ++ idx;
	
	L[p] = L[q], R[p] = R[q]; xr[p] = xr[q];
	xr[p] ^= v;
	if (l == r) return ;
	
	int mid = l + r >> 1;
	
	if (x <= mid)	insert(L[p], L[q], l, mid, x, v);
	else insert(R[p], R[q], mid + 1, r, x, v);
	
}

inline int query(int p, int q, int l, int r) {
	int mid = l + r >> 1;
	if (l == r) return l;
	if ((xr[L[p]] ^ xr[L[q]]) != 0) return query(L[p], L[q], l, mid);
	return query(R[p], R[q], mid + 1, r);
}

inline void solve() {
	std::cin >> n;
	
	for (int i = 1; i <= n; i ++) {
		std::cin >> a[i];
		while (mp[a[i]] == 0) mp[a[i]] = sj();
		insert(root[i], root[i - 1], 0, 1e9, a[i], mp[a[i]]);
	}

	
	std::cin >> m;
	
	int last = 0;
	while (m --) {
		int l, r;
		std::cin >> l >> r;
		l ^= last, r ^= last;
		
		if ((xr[root[l - 1]] ^ xr[root[r]]) == 0) {
			last = 0;
			std::cout << last << '\n';
			continue;
		}
		last = query(root[l - 1], root[r], 0, 1e9);
		std::cout << last << '\n';
	
	}
}


int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
    
    int _ = 1;
    //std::cin >> _;
    while (_ --) solve();
    
    return 0;
}