Luogu P8773 [蓝桥杯 2022 省 A] 选数异或

https://www.luogu.com.cn/problem/P8773

因为 \(a\texttt{ xor } b=c\) 则 \(a\texttt{ xor } c=b\)，对于 \(a_i\) 找到 \(a_i\texttt{ xor } x\) 离其最近的位置，放在 ST 表里查询区间最大值即可。

# include <bits/stdc++.h>
using namespace std;
const int N = 100000, M = 18;
int Max [M] [N + 10];
int l2 [N + 10];
const int X = 1 << 20;
int lst [X + 10];
int main () {
	ios :: sync_with_stdio (false);
	cin .tie (0);
	cout .tie (0);
	int n, m, x;
	cin >> n >> m >> x;
	for (int i = 3; i <= n; ++ i) {
		l2 [i] = l2 [i + 1 >> 1] + 1;
	}
	for (int i = 1; i <= n; ++ i) {
		int a;
		cin >> a;
		Max [0] [i] = lst [a ^ x];
		lst [a] = i;
	}
	for (int i = 1; (1 << i) <= n; ++ i) {
		for (int s = 1, t = 1 << i; t <= n; ++ s, ++ t) {
			Max [i] [t] = max (Max [i - 1] [s + (1 << (i - 1)) - 1], Max [i - 1] [t]);
		}
	}
	while (m --) {
		int l, r;
		cin >> l >> r;
		int g = l2 [r - l + 1];
		cout << (max (Max [g] [l + (1 << (g)) - 1], Max [g] [r]) >= l ? "yes" : "no") << '\n';
	}
	return 0;
}