[文章目录]
Description
插入删除可重集合内元素，查询集合子集最大亦或和。操作数<=5*10^5 ai<=2^31-1
按照时间的线段树维护线性基。
对于一个权值出现的操作区间[l,r]，我们将标记永久化，用线段树维护线性基。最后搜索这个线段树，将大区间的线性基加到子区间中【下传标记】。
注意不能对于每个大区间的线性基都真的加到子区间中，会MLE。对应办法只能是在dfs的时候记录一个vector，存储路径上的线性基，回溯的时候释放空间。
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define pb push_back
#define R register
inline char nc()
{
static char buf[100000],*p1,*p2;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
x=0; char f=0,ch=nc();
while(!isdigit(ch)) {if(ch=='-') f=1; ch=nc();}
while(isdigit(ch)) x=x*10+ch-'0',ch=nc();
if(f) x=-x;
}
inline int Abs(int x){return x>0 ? x : -x;}
int n,a[500100],b[500100],c[500100],num[500100],tot;
vector<int>ve[2000100];
void fix(int pos,int l,int r,int x,int y,int z)
{
if(x<=l&&y>=r) {ve[pos].pb(z); return ;}
int mid=(l+r)>>1;
if(y<=mid) fix(pos<<1,l,mid,x,y,z);
else if(x>mid) fix(pos<<1|1,mid+1,r,x,y,z);
else fix(pos<<1,l,mid,x,y,z),fix(pos<<1|1,mid+1,r,x,y,z);
}
int lin[33];
void dfs(vector<int> v,int pos,int l,int r)
{
memset(lin,0,sizeof lin); R int i,j,x;
for(i=0;i<(int)ve[pos].size();++i)
{
x=ve[pos][i];
for(j=30;~j;--j) if((x>>j)&1)
{
if(!lin[j]){lin[j]=x; break;}
x^=lin[j];
}
}
for(i=0;i<(int)v.size();++i)
{
x=v[i];
for(j=30;~j;--j) if((x>>j)&1)
{
if(!lin[j]){lin[j]=x; break;}
x^=lin[j];
}
}
if(l==r)
{
x=0;
for(i=30;~i;--i)
if((x^lin[i])>x) x^=lin[i];
printf("%d\n",x);
return ;
}
v.clear();
for(i=30;~i;--i) if(lin[i]) v.pb(lin[i]);
int mid=(l+r)>>1;
dfs(v,pos<<1,l,mid);
dfs(v,pos<<1|1,mid+1,r);
}
int main()
{
read(n); int i,id;
for(i=1;i<=n;++i) read(a[i]),b[i]=Abs(a[i]);
sort(b+1,b+n+1); c[++tot]=b[1];
for(i=2;i<=n;++i) if(b[i]!=b[i-1]) c[++tot]=b[i];
memset(b,0,sizeof b);
for(i=1;i<=n;++i)
{
id=lower_bound(c+1,c+tot+1,Abs(a[i]))-c;
if(a[i]>0) {if(!num[id]) b[id]=i; num[id]++;}
else {num[id]--; if(!num[id]) fix(1,1,n,b[id],i-1,c[id]);}
}
for(i=1;i<=tot;++i) if(num[i]) fix(1,1,n,b[i],n,c[i]);
vector<int>v;
dfs(v,1,1,n);
return 0;
}