考虑一个无脑做法:线段树维护区间线性基。时间复杂度是 \(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;
}
- Beginner AtCoder Contest Query 223beginner atcoder contest 223 beginner atcoder contest query contest programming beginner atcoder beginner atcoder contest 296 beginner atcoder contest 295 beginner atcoder contest abcde beginner atcoder contest 335 beginner atcoder contest 332 beginner atcoder contest 328 beginner atcoder contest 334