2017-07-04

【bzoj4184】shallot

线性基重学系列第一题

AC通道

考虑一个元素存在的时间[l,r]，在线段树对应区间的vector中加入这个元素

然后用类似于标记永久化的方法dfs一遍即可

#include<bits/stdc++.h>
#define FILE "read"
#define MAXN 500100
#define cmin(a,b) a=min(a,b)
#define cmax(a,b) a=max(a,b)
using namespace std;
typedef long long ll;
ll n,Mat[35],a[MAXN];
map<ll,int>cnt,last;
vector<ll>data[MAXN<<2];
inline ll read(){
	ll x=0,f=1;  char ch=getchar();
	while(ch>'9'||ch<'0')  {if(ch=='-')  f=-1;  ch=getchar();}
	while(ch>='0'&&ch<='9')  {x=x*10+ch-'0';  ch=getchar();}
	return x*f;
}
void updata(int p,int l,int r,int x,int y,ll v){
	if(x<=l&&y>=r){
		data[p].push_back(v);
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) updata(p<<1,l,mid,x,y,v);
	if(y>mid)  updata(p<<1|1,mid+1,r,x,y,v);
}
void dfs(int p,int l,int r,ll *Mat){
	ll temp[35],Lmat[35],Rmat[35];
	memcpy(temp,Mat,sizeof(temp));
	for(int i=0;i<data[p].size();++i)for(int j=32;j>=0;--j)if(data[p][i]>>j&1){
		if(temp[j]) data[p][i]^=temp[j];
		else{
			temp[j]=data[p][i];
			for(int k=j-1;k>=0;--k) if(temp[k]&&(temp[j]>>k&1))temp[j]^=temp[k];
			for(int k=j+1;k<=32;++k)if(temp[k]&&(temp[j]>>k&1))temp[k]^=temp[j];
			break;
		}
	}
	memcpy(Lmat,temp,sizeof(Lmat));
	memcpy(Rmat,temp,sizeof(Rmat));
	if(l==r){
		ll ans=0;
		for(int i=32;i>=0;--i)cmax(ans,ans^temp[i]);
		printf("%lld\n",ans);
		return;
	}
	int mid=(l+r)>>1;
	dfs(p<<1,l,mid,Lmat);  dfs(p<<1|1,mid+1,r,Rmat);
}
int main(){
	freopen(FILE".in","r",stdin);
	freopen(FILE".out","w",stdout);
	n=read();  
	for(int i=1;i<=n;++i){
		a[i]=read();
		if(a[i]>0){if(++cnt[a[i]]==1) last[a[i]]=i;}
		else{if(--cnt[-a[i]]==0) updata(1,1,n,last[-a[i]],i-1,-a[i]);}
	}
	for(int i=1;i<=n;++i)if(cnt[abs(a[i])])updata(1,1,n,last[abs(a[i])],n,abs(a[i]));
	dfs(1,1,n,Mat);
	return 0;
}

本文标题:【bzoj4184】shallot

文章作者:chty

发布时间:2017年07月04日 - 21时10分

最后更新:2017年07月05日 - 19时23分

许可协议:本文为博主原创，未经许可不得转载。