标签：线性基，线段树，CDQ分治
题目
题目传送门
Description
小苗去市场上买了一捆小葱苗，她突然一时兴起，于是她在每颗小葱苗上写上一个数字，然后把小葱叫过来玩游戏。 每个时刻她会给小葱一颗小葱苗或者是从小葱手里拿走一颗小葱苗，并且 让小葱从自己手中的小葱苗里选出一些小葱苗使得选出的小葱苗上的数字的异或和最大。 这种小问题对于小葱来说当然不在话下，但是他的身边没有电脑，于是他打电话给同为Oi选手的你，你能帮帮他吗？ 你只需要输出最大的异或和即可，若小葱手中没有小葱苗则输出0。
第一行一个正整数n表示总时间；第二行n个整数a1,a2…an，若ai大于0代表给了小葱一颗数字为ai的小葱苗，否则代表从小葱手中拿走一颗数字为-ai的小葱苗。
Output
输出共n行，每行一个整数代表第i个时刻的最大异或和。
6
1 2 3 4 -2 -3
Sample Output
1
3
3
7
7
5
HINT
N<=500000,Ai<=231−1
N
<=
500000
,
A
i
<=
2
31
−
1
分析
考试的时候现学了线性基，刺激qwq
因为线性基不支持删除操作，所以我们考虑离线
确定每个数都存在于一段连续的区间，所以我们可以用map来记录区间的起始位置和结束位置，然后用线段树来实现区间操作
这样就可以化解删除操作了
具体方法是给线段树上的每一个节点都开一个vector，vector里维护的就是线性基
每次更新到一整块区间就在线性基中加入这个数，并维护线性基
查询的时候将每个点到根的路径上的所有线性基扔进一个新开的vector，维护的同时贪心就好了
官方题解给出的是CDQ分治，时间复杂度为
O(31nlogn)
O
(
31
n
log
n
)
code
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define dep(i,a,b) for(int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
inline ll read(){
ll f=
1,x=
0;
char ch=getchar();
while(ch<
'0'||ch>
'9'){
if(ch==
'-')f=-
1;ch=getchar();}
while(ch>=
'0'&&ch<=
'9'){x=x*
10+ch-
'0';ch=getchar();}
return x*f;
}
#define lson (x<<1)
#define rson (x<<1|1)
#define mid ((l+r)>>1)
#define mp make_pair
#define pb push_back
const int maxn=
5e5+
6;
int n,last[maxn],x[maxn],y;
map<int,int> Map;
struct line{
vector<int>v;
inline int insert(
int x){
for(
int i=
0;i<v.size();i++)
if((x^v[i])<x)x^=v[i];
if(x){
v.pb(x);
for(
int i=v.size()-
1;i;i--)
if(v[i]>v[i-
1])swap(v[i],v[i-
1]);
}
return x;
}
inline int querymax(){
int re=
0;
for(
int i=
0;i<v.size();i++)
if((re^v[i])>re)re^=v[i];
return re;
}
}s[maxn<<
2],F;
void modify(
int x,
int l,
int r,
int ql,
int qr,
int v){
if(ql<=l&&r<=qr){s[x].insert(v);
return;}
if(ql<=mid)modify(lson,l,mid,ql,qr,v);
if(qr>mid)modify(rson,mid+
1,r,ql,qr,v);
}
void query(
int l,
int r,
int x,line q){
for(
int i=
0;i<s[x].v.size();i++)q.insert(s[x].v[i]);
if(l==r){
printf(
"%d\n",q.querymax());
return;
}
query(l,mid,lson,q),query(mid+
1,r,rson,q);
}
int main()
{
n=read();
rep(i,
1,n){
x[i]=read();
if(x[i]<
0)y=Map[-x[i]],last[y]=i-
1;
else Map[x[i]]=i;
}
rep(i,
1,n){
if(x[i]<
0)
continue;
if(!last[i])last[i]=n;
modify(
1,
1,n,i,last[i],x[i]);
}
query(
1,n,
1,F);
return 0;
}
