hdu多校第四场

发表于 | 更新于 | 分类于

B xor

题意

有n个基合每个集合都有小于等于32个数,有m个查询,每个查询为l,r,x,代表l~r区间内,是否每个集合都可以独立表示x这个数.

思路

用线段树维护区间内的线性基交,然后查询区间线性基是否可以表示x.

代码

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
#include<bits/stdc++.h>
using namespace std;
# define ls (pos<<1)
# define rs ((pos<<1)|1)
const int maxn=5e4+10;
unsigned tree[maxn<<2][32];
void insert(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("%s\n",query(x,y,val,1,n,1)?"YES":"NO");
	}
	//system("pause");
}