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
|
using namespace std;
# define ls (pos<<1)
# define rs ((pos<<1)|1)
const int maxn=5e4+10;
unsigned tree[maxn<<2][32];
void (unsigned x,int pos){
for(int i=31;i>=0;i--)
if(x>>i){
if(!tree[pos][i]){
tree[pos][i]=x;
break;
}
x^=tree[pos][i];
}
}
void push_up(int pos){
int l=ls,r=rs;
unsigned t1[32],t2[32];
for(int i=0;i<=31;i++) t1[i]=t2[i]=tree[l][i];
for(int i=0;i<=31;i++)
if(tree[r][i]){
unsigned x=tree[r][i],tmp=0;
for(int j=31;j>=0;j--)
if(x>>j){
if(!t1[j]){
t1[j]=x;
t2[j]=tmp;
break;
}
x^=t1[j];
tmp^=t2[j];
}
if(!x) insert(tmp,pos);
}
}
void build(int l,int r,int pos){
if(l==r){
int c;
scanf("%d",&c);
for(int i=1;i<=c;i++){
unsigned x;
scanf("%u",&x);
insert(x,pos);
}
return ;
}
int mid=(l+r)>>1;
build(l,mid,ls);
build(mid+1,r,rs);
push_up(pos);
}
int query(int x,int y,unsigned int val,int l, int r,int pos){
if(l>=x&&y>=r){
for(int i=31;i>=0;i--)
if(val>>i)
val^=tree[pos][i];
return val==0;
}
int mid=l+r>>1;
int res=1;
if(x<=mid) res&=query(x,y,val,l,mid,ls);
if(y>mid) res&=query(x,y,val,mid+1,r,rs);
return res;
}
int main(){
int n,m;
scanf("%d%d",&n,&m);
build(1,n,1);
for(int i=1;i<=m;i++){
int x,y;
unsigned val;
scanf("%d%d%u",&x,&y,&val);
printf("%sn",query(x,y,val,1,n,1)?"YES":"NO");
}
}
|
近期评论