BZOJ 4184 shallot

题目大意

给你一个集合，每次插入一个数或删除一个数，需要你输出每个时间这个集合的数所能异或出的最大的数。

首先看到异或出的最大的数立刻想到使用线性基来进行维护，时间复杂度是$O(n log n)$。但是这样存在一个问题——线性基虽然支持动态维护的插入操作，但是却不支持动态维护的删除操作，所以并没有办法良好的维护整个状态。

考虑将每个数出现的时间下放到线段树上。每个区间在线段树上对应$\log n$个节点。对于每个线段树上的节点维护一个线性基，这样的话从根节点一直pushdown到叶子节点，得到所有叶子节点对应的线性基的时间复杂度为线性基合并的时间复杂度*叶子节点个数，为$O(n \log^2 n)$.

#include <map>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lson pos<<1
#define rson pos<<1|1
struct basis
{
	int v[31];
	void clear(){memset(v,0,sizeof v);}
	void insert(int tg)
	{
		int i,j;
		for(i=30;~i;--i)
			if(tg&(1<<i))
			{
				if(v[i]&(1<<i)) tg^=v[i];
				else
				{
					v[i]=tg;
					for(j=i-1;~j;--j)
						if((v[i]&(1<<j))&&(v[j]&(1<<j)))
							v[i]^=v[j];
					for(j=30;~j;--j)
						if(j!=i&&(v[i]&(1<<i))&&(v[j]&(1<<i)))
							v[j]^=v[i];
					break;
				}
			}
	}
	int getans()
	{
		int i,ret=0;
		for(i=30;~i;--i) if(ret^v[i]>ret) ret^=v[i];
		return ret;
	}
}bs[1000];
int n,ans[500010],stk[1001],top,ref[2000010];
vector<int>vct[2000010];
map<int,int>mp;
void update(int pos,int l,int r,int x,int y,int z)
{
	if(x<=l&&r<=y) {vct[pos].push_back(z);return;}
	int mid=(l+r)>>1;
	if(x<=mid) update(lson,l,mid,x,y,z);
	if(y>mid) update(rson,mid+1,r,x,y,z);
}
void query(int pos,int l,int r)
{
	for(vector<int>::iterator it=vct[pos].begin();it!=vct[pos].end();++it) bs[ref[pos]].insert(*it);
	if(l==r){ans[l]=bs[ref[pos]].getans();stk[++top]=ref[pos];return;}
	int i,mid=(l+r)>>1;
	ref[lson]=stk[top--],ref[rson]=stk[top--];
	bs[ref[lson]].clear(),bs[ref[rson]].clear();
	for(i=30;~i;--i) bs[ref[lson]].v[i]=bs[ref[pos]].v[i];
	for(i=30;~i;--i) bs[ref[rson]].v[i]=bs[ref[pos]].v[i];
	query(lson,l,mid),query(rson,mid+1,r);
	stk[++top]=ref[pos];
}
int main()
{
	int i,t;
	scanf("%d",&n);
	for(i=0;i<1000;++i) stk[++top]=i;
	for(i=1;i<=n;++i)
	{
		scanf("%d",&t);
		if(t>0) mp[t]=i;
		else update(1,1,n,mp[-t],i-1,-t),mp.erase(mp.find(-t));
	}
	for(map<int,int>::iterator it=mp.begin();it!=mp.end();++it) update(1,1,n,it->second,n,it->first);
	ref[1]=stk[top--],query(1,1,n);
	for(i=1;i<=n;++i) printf("%d\n",ans[i]);
	return 0;
}