「bzoj4184」shallot葱苗 - 线段树分治+线性基 | Bill Yang's Blog

「bzoj4184」shallot葱苗 - 线段树分治+线性基

题目大意

    每次加入一个数,删除一个数,动态维护最大异或和。


题目分析

这题有点厉害。

在线没法做,考虑离线。
离线维护最大异或和,不妨线段树分治,把数存在的区间提出来放进线段树,考虑分治遍历解决异或和。

分治遍历时维护一个线性基,每次递归时加入线性基,递归到叶子输出线性基异或和即可。
怎么回溯呢?需要在线性基里删除一个元素?
似乎还是没法做啊?

不方,注意到线性基大小只有$31$,我们又可以搞事情。
递归时不引用传递,暴力复制,就不需要回溯了。
只会复制$O(n)$次,故时间复杂度为$O(n\log n+31n)$。


代码

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
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;
inline int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(!isdigit(x)) {if(x=='-')bj=-1;x=getchar();}
while(isdigit(x)) {num=num*10+x-'0';x=getchar();}
return num*bj;
}
const int maxn=500005,MAX_BASE=31;
struct Linear_Bases {
int b[MAX_BASE+1];
Linear_Bases() {fill(b,b+MAX_BASE+1,0);}
void add(int num) {
for(int j=MAX_BASE; j>=0; j--)
if(num>>j&1) {
if(b[j]) {
num^=b[j];
continue;
}
b[j]=num;
for(int k=j-1; k>=0; k--)if(b[j]>>k&1)b[j]^=b[k];
for(int k=j+1; k<=MAX_BASE; k++)if(b[k]>>j&1)b[k]^=b[j];
break;
}
}
int cal() {
int ans=0;
for(int i=0; i<=MAX_BASE; i++)ans^=b[i];
return ans;
}
};
struct Segment_Tree {
struct Tree {
int left,right;
vector<int> p;
Tree(int l=0,int r=0):left(l),right(r) {p=vector<int>();}
} tree[maxn<<2];
#define ls index<<1
#define rs index<<1|1
void build(int index,int Left,int Right) {
tree[index]=Tree(Left,Right);
if(Left==Right)return;
int mid=(Left+Right)>>1;
build(ls,Left,mid);
build(rs,mid+1,Right);
}
void insert(int index,int Left,int Right,int x) {
if(Right<tree[index].left||Left>tree[index].right)return;
if(Left<=tree[index].left&&Right>=tree[index].right) {tree[index].p.push_back(x);return;}
insert(ls,Left,Right,x);
insert(rs,Left,Right,x);
}
void dfs(int index,Linear_Bases lb) {
for(int x:tree[index].p)lb.add(x);
if(tree[index].left==tree[index].right) {printf("%d\n",lb.cal());return;}
dfs(ls,lb);
dfs(rs,lb);
}
} st;
int n,tot=0,a[maxn],b[maxn],H[maxn];
int main() {
n=Get_Int();
st.build(1,1,n);
for(int i=1; i<=n; i++) {
a[i]=Get_Int();
if(a[i]>0)b[++tot]=a[i];
}
sort(b+1,b+tot+1);
tot=unique(b+1,b+tot+1)-b-1;
for(int i=1; i<=n; i++) {
if(a[i]>0)H[lower_bound(b+1,b+tot+1,a[i])-b]=i;
else {
int now=lower_bound(b+1,b+tot+1,-a[i])-b;
st.insert(1,H[now],i-1,-a[i]);
H[now]=0;
}
}
for(int i=1; i<=tot; i++)if(H[i])st.insert(1,H[i],n,b[i]);
Linear_Bases lb;
st.dfs(1,lb);
return 0;
}
0%