BZOJ4184: shallot

题解:

考虑每个数都有一个存在的时间区间.

将这个数的存在看做一次区间修改,利用线段树维护打标记即可.

(其实和分治的本质是相同的)

为了计算插入这个数造成的影响,只需要维护一个线性基即可.

详情见代码.

代码:

#include<cstdio>
#include<cctype>
#include<cstring>
#include<climits>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#include<map>
#include<stack>
#include<vector>
using namespace std;

#define N 500010
inline int getc(){
	static const int L=1<<15;
	static char buf[L],*S=buf,*T=buf;
	if(S==T){
		T=(S=buf)+fread(buf,1,L,stdin);
		if(S==T)
			return EOF;
	}
	return*S++;
}
inline int getint(){
	int c;
	while(!isdigit(c=getc())&&c!='-');
	bool s=c=='-';
	int x=s?0:c-'0';
	while(isdigit(c=getc()))
		x=(x<<1)+(x<<3)+c-'0';
	return s?-x:x;
}

#define N 500010
int a[N];

struct Linear_Base{
	int a[32];
	Linear_Base(){
		memset(a,0,sizeof a);
	}
	inline void insert(int x){
		for(int i=31;i>=0;--i){
			if((x>>i)&1){
				if(a[i]==0){
					a[i]=x;
					break;
				}
				else
					x^=a[i];
			}
		}
	}
	inline int getans(){
		int ans=0;
		for(int i=31;i>=0;--i)
			if(((ans>>i)&1)==0)
				ans^=a[i];
		return ans;
	}
};


struct info{
	int l,r,x;
	info(int _l,int _r,int _x):l(_l),r(_r),x(_x){}
};

inline void divide_conquer(int l,int r,vector<info>num,Linear_Base s){
	for(int i=0;i<num.size();++i)
		if(num[i].l==l&&num[i].r==r)
			s.insert(num[i].x);
	if(l==r){
		printf("%d\n",s.getans());
		return;
	}
	int mid=(l+r)>>1;
	vector<info>nl,nr;
	for(int i=0;i<num.size();++i)
		if(num[i].l!=l||num[i].r!=r){
			if(num[i].r<=mid)
				nl.push_back(info(num[i].l,num[i].r,num[i].x));
			else if(num[i].l>mid)
				nr.push_back(info(num[i].l,num[i].r,num[i].x));
			else{
				nl.push_back(info(num[i].l,mid,num[i].x));
				nr.push_back(info(mid+1,num[i].r,num[i].x));
			}
		}
	divide_conquer(l,mid,nl,s);
	divide_conquer(mid+1,r,nr,s);
}

map<int,int>cnt,last_pos;

int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	int n=getint();
	int i,j,x;
	vector<info>begin;
	for(i=1;i<=n;++i){
		x=getint();
		if(x>0){
			if(++cnt[x]==1)
				last_pos[x]=i;
		}
		else{
			if(--cnt[-x]==0)
				begin.push_back(info(last_pos[-x],i-1,-x));
		}
	}
	for(map<int,int>::iterator it=cnt.begin();it!=cnt.end();++it)
		if(it->second>0)
			begin.push_back(info(last_pos[it->first],n,it->first));

	Linear_Base lb;
	divide_conquer(1,n,begin,lb);
	
	return 0;
}