[BZOJ4184]shallot 线段树+线性基

链接

题意：给你每个数字出现的时间和消失的时间，求每个时刻最大异或和

题解

按照时间建立线段树，线段树每个节点开个vector存一下这个时间区间有哪些数，然后递归进入的时候加入线性基，开一个栈记录一下加了哪些基底，回溯的时候把之前加的删掉即可

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
using namespace std;
typedef long long ll;
inline int read(){char c,p=0;int w;
	while(!isdigit(c=getchar()))if(c=='-')p=1;w=c&15;
	while(isdigit(c=getchar()))w=w*10+(c&15);return p?-w:w;
}
inline char smax(int&x,const int&y){return x<y?x=y,1:0;}
inline char smin(int&x,const int&y){return x>y?x=y,1:0;}
const int N=5e5+5,n=read();
vector<int>g[N<<2];
#define ls o<<1
#define rs o<<1|1
inline void ins(int o,int l,int r,int x,int y,int z){
	if(x<=l&&r<=y){g[o].push_back(z);return;}
	int mid=l+r>>1;
	if(x<=mid)ins(ls,l,mid,x,y,z);
	if(y>mid)ins(rs,mid+1,r,x,y,z);
}
int p[33],s[33],top;
inline void ins(int x){for(int i=31;~i;--i)if(x>>i&1)if(!p[i]){p[i]=x,s[++top]=i;break;}else x^=p[i];}
inline void erase(int pre){while(top!=pre)p[s[top--]]=0;}

inline void ask(int o,int l,int r){
	int pre=top;
	for(int i=0;i<g[o].size();++i)ins(g[o][i]);
	if(l==r){
		int ans=0;
		for(int i=31;~i;--i)smax(ans,ans^p[i]);
		return printf("%d
",ans),erase(pre);
	}
	int mid=l+r>>1;ask(ls,l,mid),ask(rs,mid+1,r);erase(pre);
}
map<int,int>pos;
map<int,int>::iterator it;
int main(){
	REP(i,1,n){
		int x=read();
		if(x>0)pos[x]=i;
		else{
			it=pos.find(-x);
			ins(1,1,n,it->second,i-1,-x);
			pos.erase(it);
		}
	}
	for(it=pos.begin();it!=pos.end();++it)
	ins(1,1,n,it->second,n,it->first);
	ask(1,1,n);
	return 0;
}