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
|
using namespace std;
const int maxn=5e5+10;
int a[maxn],ans[maxn];
struct {
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("%dn",ans[i]);
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
|
using namespace std;
const int maxn=5e5+10;
int a[maxn],pos[maxn][21],line[maxn][21];
struct {
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("%dn",res);
}
}
|
近期评论