CF1100F. Ivan and Burgers

CF1100F. Ivan and Burgers

原题传送门:>Here<

我们发现一个询问$l,r$相当于把$[l,r]$里的所有数丢进线性基里,然后查询最大异或和。

用线段树维护线性基复杂度是$O(nlog^3n)$。我们考虑优秀一点的做法。

考虑分治。假设当前分治到$(l,r)$,中点为$mid$。

我们分别预处理出从$mid$往左右连续的线性基。

也就是对于$num_i$,当$i<mid$时,$num_i$为$[i,mid]$的线性基;否则就是$[mid,i]$的线性基。

这样对于一个跨越$mid$的询问,我们可以$O(log^2n)$合并线性基并$O(logn)$计算。对于一个只在左边/只在右边的询问,我们继续递归下去。

总复杂度$O(nlog^2n)$。

代码:

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
#include <cstdio>
#include <cstring>
#include <vector>

struct basis{
int Base[21];
basis(){memset(Base,0,sizeof Base);}
void add(int x){
for(int i=20;~i;--i)
if(x&(1<<i)){
if(!Base[i]){
Base[i]=x;
return;
}
x^=Base[i];
}
}
int getmx(){
int ans=0;
for(int i=20;~i;--i)
if(ans<(ans^Base[i]))ans^=Base[i];
return ans;
}
void print(){
for(int i=20;~i;--i)printf("%d ",Base[i]);putchar('\n');
}
}num[500001];
basis merge(basis a,basis b){
for(int i=20;~i;--i)
if(b.Base[i])a.add(b.Base[i]);
return a;
}
int a[500001],ans[500001],n,q;
struct query{int l,r,orig;}queries[500001],tem[500001];
void solve(int l,int r,int el,int er){
if(el>er)return;
if(l==r){
for(int i=el;i<=er;i++)ans[queries[i].orig]=a[l];
return;
}
int mid=(l+r)>>1;
num[mid]=basis();
num[mid].add(a[mid]);
for(int i=mid+1;i<=r;i++){
num[i]=num[i-1];
num[i].add(a[i]);
}
for(int i=mid-1;i>=l;i--){
num[i]=num[i+1];
num[i].add(a[i]);
}
int x=el,y=er;
for(int i=el;i<=er;i++){
if(queries[i].r<=mid)tem[x++]=queries[i];
else if(queries[i].l>mid)tem[y--]=queries[i];
else ans[queries[i].orig]=merge(num[queries[i].r],num[queries[i].l]).getmx();
}
for(int i=el;i<x;i++)queries[i]=tem[i];
for(int i=er;i>y;i--)queries[i]=tem[i];
solve(l,mid,el,x-1);
solve(mid+1,r,y+1,er);
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",a+i);
scanf("%d",&q);
for(int i=1;i<=q;i++)scanf("%d%d",&queries[i].l,&queries[i].r),queries[i].orig=i;
solve(1,n,1,q);
for(int i=1;i<=q;i++)printf("%d\n",ans[i]);
}

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×