[bzoj4184]-shallot

题目（BZOJ）
 
...总之就是对时间进行分治的姿势而已。
...进一步来讲，我们只考虑线段树的叶子节点，因为那才是我们要的信息，其他节点只是辅助作用而已。
每个叶子节点存当前时间有哪些数加进来，哪些数被删掉。我们在树上先左走后右走，就可以处理每个时间的答案了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;bool ck=0;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	if(ck)e=-e;
}
const int N=500001;
int n,ji[31];
map <int,int> mp;
struct node{
	int a[31];
	node(){memset(a,0,sizeof a);}
	inline int &operator [] (const int i){return a[i];}
}e;
inline void addji(node &x,int v){
	for(int i=30;i>=0;--i){
		if(!(v>>i))continue;
		if(!x[i]){x[i]=v;break;}
		v^=x[i];
	}
}
#define ls id<<1
#define rs id<<1|1
struct seg{
	int l,r;
	vector <int> vec;
}t[N<<2];
void build(int l,int r,int id){
	t[id].l=l,t[id].r=r;t[id].vec.clear();
	if(l==r)return;
	int mid=(l+r)>>1;
	build(l,mid,ls);build(mid+1,r,rs);
}
void insert(int L,int R,int val,int id){
	int l=t[id].l,r=t[id].r;
	if(L<=l&&R>=r){
		t[id].vec.push_back(val);
		return;
	}
	int mid=(l+r)>>1;
	if(R<=mid)insert(L,R,val,ls);
	else if(L>mid)insert(L,R,val,rs);
	else{
		insert(L,mid,val,ls);
		insert(mid+1,R,val,rs);
	}
}
void work(node x,int id){
	int l=t[id].l,r=t[id].r;
	for(int i=0;i<t[id].vec.size();++i)addji(x,t[id].vec[i]);
	if(l==r){
		int ans=0;
		for(int i=30;i>=0;--i)ans=max(ans,(ans^x[i]));
		printf(
		return;
	}
	work(x,ls);work(x,rs);
}
int main(){
	read(n);int mx=INT_MAX;
	for(int i=1;i<=n;++i){
		int x;read(x);
		mp[x]=i;if(x>0)mx=min(mx,x);
	}
	build(1,n,1);
	for(map<int,int>::iterator i=mp.find(mx);i!=mp.end();++i){
	//get到的新操作，详情见https://www.cnblogs.com/DaD3zZ-Beyonder/p/6612729.html
		int x=i->first,l=i->second,r=mp[-x]?(mp[-x]-1):n;
		insert(l,r,x,1);
	}
	work(e,1);
	return 0;
}