# Bzoj4184 shallot

## 用 线段树 维护带有删除操作的线性基

Posted by yjjr's blog on March 15, 2018

# 题目

## Sample Input

6
1 2 3 4 -2 -3


## Sample Output

1
3
3
7
7
5


# 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;
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()
{
rep(i,1,n){
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;
}