传送门
题意：给你n个数字，n个消除位置的顺序，问每次消除前不包含无效位置的区间的异或和的最大值。
题解：我们反向加入数字，那么每次会和pos-1与pos+1的区间合并，我们通过线性基记录每个位置的情况，通过并查集合并，查询合并完的线性基的最大异或和，就可以了。
#include<iostream> #include<cstring> #include<cmath> #include<cstdio> #include<algorithm> #define ll long long using namespace std; const int maxn=1e5+10; int per[maxn]; int p[maxn]; int ans[maxn]; int mark[maxn]; struct L_B{ int d[35]; L_B() { memset(d,0,sizeof(d)); } bool insert(int val) { for(int i=30;i>=0;i--) { if(val&(1<<i)) { if(!d[i]) { d[i]=val; break; } val^=d[i]; } } return val>0; } int query_max() { int ret=0; for(int i=30;i>=0;i--) { if((ret^d[i])>ret) { ret^=d[i]; } } return ret; } }a[maxn]; L_B merge(const L_B &n1,const L_B &n2)// a[nx]=merge(a[nx],a[ny]); { L_B ret=n1; for(int i=30;i>=0;i--) { if(n2.d[i]) ret.insert(n2.d[i]); } return ret; } int find(int x) { if(x==per[x]) { return x; } return per[x]=find(per[x]); } int link(int x,int y) { int nx=find(x),ny=find(y); if(nx!=ny) { per[ny]=nx; // ny的父节点是nx } a[nx]=merge(a[nx],a[ny]);// 维护左边的线性基础 return a[nx].query_max(); } int main() { L_B(); memset(mark,0,sizeof(mark)); int n; cin>>n; for(int i=1;i<=n;i++) { int w; cin>>w; a[i].insert(w); per[i]=i; } for(int i=1;i<=n;i++) { cin>>p[i]; } int sum=0; for(int i=n;i>=1;i--) { int k=p[i]; mark[k]=1; sum=max(a[k].query_max(),sum); if(mark[k-1]) { sum=max(sum,link(k-1,k)); } if(mark[k+1]) { sum=max(sum,link(k,k+1)); } ans[i]=sum; } for(int i=1;i<=n;i++) { cout<<ans[i]<<endl; } return 0; }
