题目链接
题意
每次询问是否一个区间里的集合是否都能表示某一个元素。
思路
每一个点都是一个线性基。
题目的询问其实就是询问，是否这个区间的线性空间交能表示这个数字。
线性空间求交模板题。
注意查询的时候不需要真的全都交起来，可以直接在线段树上看可不可行，代替把整个区间内的交求出来多一个log。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
using namespace std;
typedef long long ll;
void err(){cout << "\033[39;0m" << endl;}
template<template<typename...> class T, typename t, typename... A>
void err(T<t> a, A... x){for (auto v: a) cout << v << ' '; err(x...);}
template<typename T, typename... A>
void err(T a, A... x){cout << a << ' '; err(x...);}
typedef unsigned int ui;
const int N = 5e4 + 5;
ui base[N << 4][33];
bool insert(int c, ui x)
{
for (int i = 31; i >= 0; i--)
if ((x >> i) & 1)
{
//dbg(i, base[c][i], x);
if (base[c][i])
{
x ^= base[c][i];
if (x == 0)
return 1;
}
else
{
base[c][i] = x;
return 0;
}
}
return x == 0;
}
int tot[33], tmp[33];
void merge(int a, int b, int c)
{
//puts("Merge!!!!!!");
//dbg(a, b, c);
for(int i = 0; i < 32; i++)
{
//dbg(base[a][i]);
tot[i] = base[a][i];
tmp[i] = base[a][i];
base[c][i] = 0;
}
for(int i = 0; i < 32; i++)
if (base[b][i])
{
ui cur = base[b][i], add = 0;
for (int j = i; j >= 0; j--)
if ((cur >> j) & 1)
{
//dbg(j, tot[j], cur, add, tmp[j]);
if (tot[j])
{
cur ^= tot[j];
add ^= tmp[j];
//dbg(cur, add);
if (!cur)
{
base[c][i] = add;
//dbg(base[c][i]);
break;
}
}
else
{
tot[j] = cur;
tmp[j] = add;
break;
}
}
}
}
int siz;
void push_up(int rt)
{
merge(lson, rson, rt);
}
template<class T>
void read(T& ret)
{
ret = 0;
char c;
while ((c = getchar()) < '0' || c > '9');
while (c >= '0' && c <= '9')
{
ret = ret * 10 + c - '0';
c = getchar();
}
}
void build(int L, int R, int rt)
{
//dbg(L, R);
if (L == R)
{
for (int i = 31; i >= 0; i--)
base[rt][i] = 0;
read(siz);
for (int i = 1; i <= siz; i++)
{
ui x;
read(x);
insert(rt, x);
}
/*
for (int i = 31; i >= 0; i--)
{
if (base[rt][i])
dbg(rt, i, base[rt][i]);
}
*/
return;
}
for (int i = 31; i >= 0; i--)
base[rt][i] = 1 << i;
int mid = (L + R) >> 1;
build(Lson);
build(Rson);
push_up(rt);
}
bool check(int a, ui x)
{
for (int i = 0; i < 32; i++)
{
base[0][i] = base[a][i];
}
return insert(0, x);
}
bool query(int l, int r, ui x, int L, int R, int rt)
{
if (l <= L && r >= R)
{
return check(rt, x);
}
int mid = (L + R) >> 1;
bool ans = 1;
if (l <= mid)
ans = ans && query(l, r, x, Lson);
if (r > mid)
ans = ans && query(l, r, x, Rson);
return ans;
}
int main()
{
int n, m;
scanf("%d%d", &n, &m);
build(1, n, 1);
for (int q = 1; q <= m; q++)
{
int l, r;
ui x;
read(l);
read(r);
read(x);
if (query(l, r, x, 1, n, 1))
puts("YES");
else
puts("NO");
}
return 0;
}