Wannafly挑战赛14 - E 并查集维护线性基区间

线性基删除不知道怎么维护,不妨逆向添加

然后区间连通性的维护自然要应用到并查集,每次操作mark一下当前位置,如果在操作时左边的区间已经mark过就搞它,右边同理

注意find时谁的基被插入

#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<string>

#include<vector>

#include<stack>

#include<queue>

#include<set>

#include<map>

#include<bitset>

#define rep(i,j,k) for(register int i=j;i<=k;i++)

#define rrep(i,j,k) for(register int i=j;i>=k;i--)

#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])

#define iin(a) scanf("%d",&a)

#define lin(a) scanf("%lld",&a)

#define din(a) scanf("%lf",&a)

#define s0(a) scanf("%s",a)

#define s1(a) scanf("%s",a+1)

#define print(a) printf("%lld",(ll)a)

#define enter putchar('\n')

#define blank putchar(' ')

#define println(a) printf("%lld\n",(ll)a)

#define IOS ios::sync_with_stdio(0)

using namespace std;

const int MAXN = 1e5+11;

const double EPS = 1e-7;

typedef long long ll;

typedef unsigned long long ull;

const ll MOD = 10086;

unsigned int SEED = 17;

const ll INF = 1ll<<60;

ll read(){

    ll x=0,f=1;register char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

struct LB{

    ll b[66];

    void clear(){

        rep(i,0,62) b[i]=0;

    }

    void insert(ll x){

        rrep(i,62,0) if(x>>i&1){

            if(b[i]) x^=b[i];

            else{

                b[i]=x;

                rrep(j,i-1,0) if(b[j]&&(b[i]>>j&1)) b[i]^=b[j];

                rep(j,i+1,62) if(b[j]>>i&1) b[j]^=b[i];

                break;

            }

        }

    }

    ll rk1(){

        ll res=0;

        rrep(i,62,0) res^=b[i];

        return res;

    }

    void merge(LB rhs){

        rep(i,0,62) if(rhs.b[i]) insert(rhs.b[i]);

    }

}B[MAXN];

struct UF{

    int p[MAXN];

    void init(int n){

        rep(i,1,n) p[i]=i;

    }

    int find(int x){

        if(x==p[x]) return x;

        // int o=p[x];

        int t=find(p[x]);

        B[t].merge(B[x]);

        return p[x]=t;

    }

    ll link(int a,int b){

        a=find(a);b=find(b);

        if(a==b) return B[a].rk1();

        p[a]=b;B[b].merge(B[a]);

        return B[b].rk1();

    }

}uf;

ll a[MAXN],n,x[MAXN],ans[MAXN];

bool vis[MAXN];

int main(){

    while(cin>>n){

        uf.init(n);

        memset(vis,0,sizeof vis);

        rep(i,1,n) a[i]=read();

        rep(i,1,n) x[i]=read();

        rep(i,1,n) B[i].clear();

        rep(i,1,n) B[i].insert(a[i]);

        ll mx=0;

        rrep(i,n,1){

            if(i==n) mx=ans[i]=a[x[n]],vis[x[n]]=1;

            else{

                ans[i]=-1;

                vis[x[i]]=1;

                if(vis[x[i]-1]&&x[i]-1>0){

                    int a=uf.find(x[i]-1);

                    mx=ans[i]=max(mx,uf.link(x[i],a));

                }

                if(vis[x[i]+1]&&x[i]+1<=n){

                    int a=uf.find(x[i]+1);

                    mx=ans[i]=max(mx,uf.link(x[i],a));

                }

                if(ans[i]==-1){

                    mx=ans[i]=max(mx,a[x[i]]);

                }

            }

            //rep(j,1,n) cout<<j<<" "<<uf.p[j]<<endl;

        }

        rep(i,1,n) println(ans[i]);

    }

    return 0;

}