考虑一个无脑做法：线段树维护区间线性基。时间复杂度是 \(O(m \log n \log^2 V)\)，过于优秀以至于无法接受。
事实上我们并不需要维护区间线性基，因为不带修。考虑“可持久化线性基”，开 \(n\) 个线性基，第 \(i\) 个维护前缀 \([1, i]\) 的数。并且插入线性基时优先选择出现位置靠后的数，这样使得查询时左端点的限制更容易被满足。查询的时候，直接查第 \(r\) 个线性基能不能凑出 \(x\) 并且不使用出现位置 \(< l\) 的数。
但是这样空间复杂度是 \(O(n \log V)\) 的，不够优秀。考虑我们其实可以离线，按右端点从小到大插入并且回答询问，就不用开 \(n\) 个线性基了，空间复杂度降为 \(O(n + \log V)\)，时间复杂度是 \(O((n + m) \log V)\)。
code
// Problem: H - Xor Query
// Contest: AtCoder - AtCoder Beginner Contest 223
// URL: https://atcoder.jp/contests/abc223/tasks/abc223_h
// Memory Limit: 1024 MB
// Time Limit: 3000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include <bits/stdc++.h>
#define pb emplace_back
#define fst first
#define scd second
#define mems(a, x) memset((a), (x), sizeof(a))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef long double ldb;
typedef pair<ll, ll> pii;
const int maxn = 400100;
ll n, m, a[maxn], p[66], d[65], b[maxn];
struct node {
ll p, x, id;
node(ll a = 0, ll b = 0, ll c = 0) : p(a), x(b), id(c) {}
};
vector<node> vc[maxn];
inline void insert(ll x, ll t) {
for (int i = 59; ~i; --i) {
if (x & (1LL << i)) {
if (!p[i]) {
p[i] = x;
d[i] = t;
break;
}
if (d[i] < t) {
swap(x, p[i]);
swap(t, d[i]);
}
x ^= p[i];
}
}
}
inline bool check(ll x, ll t) {
for (int i = 59; ~i; --i) {
if (x & (1LL << i)) {
if (!p[i] || d[i] < t) {
return 0;
}
x ^= p[i];
}
}
return 1;
}
void solve() {
scanf("%lld%lld", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%lld", &a[i]);
}
for (int i = 1; i <= m; ++i) {
ll l, r, x;
scanf("%lld%lld%lld", &l, &r, &x);
vc[r].pb(l, x, i);
}
for (int i = 1; i <= n; ++i) {
insert(a[i], i);
for (node u : vc[i]) {
b[u.id] = check(u.x, u.p);
}
}
for (int i = 1; i <= m; ++i) {
puts(b[i] ? "Yes" : "No");
}
}
int main() {
int T = 1;
// scanf("%d", &T);
while (T--) {
solve();
}
return 0;
}