AcWing
4645. 选数异或(第十三届蓝桥杯省赛C++ A组/C组)
线性DP. 定义f[i]：从1到i枚举b，所有在b之前，且能与b配对的最右位置的a的最大值，即：假设b∈[1, i]，g[b]表示b之前能与b配对的最右位置的a∈[1, b-1]，那么f[i] = max{g[b]}, b∈[1, i].
状态转移方程：f[i] = max{f[i-1], g[i]}.
对于任意一次查询[l, r]，如果f[r] >= l，表示在[l, r]存在至少一对配对的点，那么输出yes，否则输出no.
#include <bits/stdc++.h>
using namespace std;
int n, m, x;
const int N = 100010, M = (1 << 20) + 10;
int a;
int f[N], q[M];
int main(){
cin >> n >> m>> x;
for(int i = 1; i <= n; i++){
cin >> a;
f[i] = max(f[i - 1], q[a]); // 注意这行和下面一行的顺序不能颠倒，因为异或为0的话，不能和自己异或
q[a ^ x] = i;
}
while(m--){
int l, r;
cin >> l >> r;
if(f[r] >= l) cout << "yes\n";
else cout << "no\n";
}
return 0;
}