C++(g++ 7.5.0) 解法, 执行用时: 114ms, 内存消耗: 14368K, 提交时间: 2022-08-18 20:52:40

#include<cstdio>
#include<algorithm>
struct linear_base
{
	int a[32];
	void insert(int x)
	{
		for(int i=31;i>=0;i--)if(x>>i)
		{
			if(!a[i]){a[i]=x;break;}
			x^=a[i];
		}
	}
	int query()
	{
		int xsum=0;
		for(int i=31;i>=0;i--)if((xsum^a[i])>xsum)xsum^=a[i];
		return xsum;
	}
	void merge(linear_base&o)
	{
		for(int i=31;i>=0;i--)if(o.a[i])
			insert(o.a[i]);
	}
}lb[100003];
int x[100003],d[100003],a[100003];
struct DSU
{
	int f[100003];
	void init(int n){for(int i=1;i<=n;i++)f[i]=i,lb[i].insert(x[i]);}
	int find(int p){return p==f[p]?p:p=find(f[p]);}
	void merge(int x,int y)
	{
		x=find(x),y=find(y);
		if(x==y)return;
		f[y]=x,lb[x].merge(lb[y]);
	}
}dsu;
bool vis[100003];
int main()
{
	int n,ans=0;scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%d",x+i);
	for(int i=n;i>=1;i--)scanf("%d",d+i);
	dsu.init(n);
	for(int i=1;i<=n;i++)
	{
//		for(int j=1;j<=n;j++)printf("%d ",lb[j].query());putchar(10);
		int&p=d[i];
		vis[p]=1;
		if(vis[p-1])dsu.merge(p,p-1);
		if(vis[p+1])dsu.merge(p,p+1);
		ans=std::max(ans,lb[dsu.find(p)].query());
		a[i]=ans;
	}
	for(int i=n;i>=1;i--)printf("%d\n",a[i]);
}

C++14(g++5.4) 解法, 执行用时: 109ms, 内存消耗: 15332K, 提交时间: 2019-07-24 21:59:32

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int N=1e5+7;

int n,res;
int a[N],x[N],p[N][30],fa[N],ans[N];

void ins(int *p, int x)
{
    for(int i=29; ~i; i--)
        if((x>>i)&1)
        {
            if(!p[i]) {p[i]=x; return ;}
            x^=p[i];
        }
}

int get(int x)
{
    return x==fa[x]? x:fa[x]=get(fa[x]);
}

void merge(int u, int v)
{
    u=get(u),v=get(v);
    for(int i=29; ~i; i--)
        if(p[v][i]) ins(p[u],p[v][i]);
    fa[v]=u;
}

int ask(int *p)
{
    int res=0;
    for(int i=29; ~i; i--) res=max(res,res^p[i]);
    return res;
}

int main()
{
#ifdef local
    freopen("in.txt", "r", stdin);
#endif
    scanf("%d",&n);
    for(int i=1; i<=n; i++) scanf("%d",&a[i]);
    for(int i=1; i<=n; i++) scanf("%d",&x[i]);
    for(int i=n,t; i; i--)
    {
        t=x[i];
        fa[t]=t,ins(p[t],a[t]);
        if(fa[t-1]) merge(t,t-1);
        if(fa[t+1]) merge(t,t+1);
        ans[i]=res=max(res,ask(p[get(t)]));
    }
    for(int i=1; i<=n; i++) printf("%d\n",ans[i]);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 137ms, 内存消耗: 17516K, 提交时间: 2018-04-20 19:38:30

#include<bits/stdc++.h>
using namespace std;
int n,a[100100],A[100100];
int b[40],anses[100100],ans,val[100100][40],f[100100];
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
void ins(int b[],int x){
	for(int j=30;j>=0;--j)if((x>>j&1)){
		if(!b[j]){
			b[j]=x;
			break;
		} else x^=b[j];
	}
}
int cal(int b[]){
	int ans=0;
	for(int j=30;j>=0;--j)if((ans^b[j])>ans)ans^=b[j];
	return ans;
}
void merge(int x,int y){
	x=find(x),y=find(y);
	for(int i=0;i<=30;++i)if(val[x][i])ins(val[y],val[x][i]);
	f[x]=y;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)f[i]=0;
	for(int i=1;i<=n;++i)scanf("%d",&a[i]);
	for(int i=1;i<=n;++i)scanf("%d",&A[i]);
	for(int i=n;i>=1;--i){
		int x=A[i];
		f[x]=x,ins(val[x],a[x]);
		if(f[x-1])merge(x-1,x);
		if(f[x+1])merge(x+1,x);
		ans=max(ans,cal(val[find(x)]));
		anses[i]=ans;
	}
	for(int i=1;i<=n;++i)printf("%d\n",anses[i]);
}