1100F-Ivan and Burgers

发表于 | 分类于

F. Ivan and Burgers

题意

​ 给出n个整数,有q次查询,每次查询给出l,r,问l,r内区间的最大异或和.

思路

 线性基,在线或者离线

代码

离线线性基的代码

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int a[maxn],ans[maxn];
struct P{
	int l,r,id;
	bool operator < (P b){
		return r<b.r;
	}
} p[maxn];
int pos[21],line[21];
void add(int x,int id){
	for(int i=20;i>=0;i--){
		if(x&(1<<i)){
			if(!line[i]) {
				line[i]=x,pos[i]=id;
				break;
			}
			if(pos[i]<id) swap(line[i],x),swap(pos[i],id);
			x^=line[i];
		}
	}
}
int query(int id){
	int res=0;
	for(int i=20;i>=0;i--){
		if(pos[i]>=id&&(res^line[i])>res) res^=line[i];
	}
	return res;
}
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int q;
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>p[i].l>>p[i].r;
		p[i].id=i;
	}
	sort(p+1,p+q+1);
	int l=1;
	for(int i=1;i<=q;i++){
		while(l<=p[i].r&&l<=n) add(a[l],l),l++;
		ans[p[i].id]=query(p[i].l);
	}
	for(int i=1;i<=q;i++) printf("%d\n",ans[i]);
	//system("pause");
	return 0;
}

在线线性基的代码:

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
#include<bits/stdc++.h>
using namespace std;
const int maxn=5e5+10;
int a[maxn],pos[maxn][21],line[maxn][21];
struct P{
	int l,r,id;
}p[maxn];
int n;
void init(){
	for(int i=1;i<=n;i++){
		for(int j=0;j<=20;j++) 
			line[i][j]=line[i-1][j],pos[i][j]=pos[i-1][j];
		int id=i;
		for(int j=20;j>=0;j--){
			if(a[i]&(1<<j)){
				if(!line[i][j]) {
					line[i][j]=a[i];
					pos[i][j]=id;
					break;
				}
				if(pos[i][j]<id) swap(line[i][j],a[i]),swap(pos[i][j],id);
				a[i]^=line[i][j];
			}
		}
	}
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	init();
	int q;
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		int l,r;
		scanf("%d%d",&l,&r);
		int res=0;
		for(int j=20;j>=0;j--)
			if(pos[r][j]>=l&&(res^line[r][j])>res) res^=line[r][j];
		printf("%d\n",res);
	}
	//system("pause");
}