传送门
题意：首先输入n，代表当前有n个数，然后再输入m，代表m次询问，每一次询问是询问区间[l,r]，这段区间内的数的最大异或值。
思路：处理出来一个前缀线性基，记录线性基上该位置是在原序列的哪个位置，求值的时候在第r个线性基上找，如果位置>=l则是合法的。如果有两个相同的数在同一位，遇到这种情况则用贪心的想法，如果在同一位上明显原序列越大的数越优，因为如果把原序列小的留下，则区间长度较小时明显没有原序列大的数更优，所以贪心的留下原序列大的。和这题很像
#include<iostream> #include<algorithm> #include<cmath> #include<cstdio> #include<cstring> #define ll long long using namespace std; const int maxn=5e5+10; int per[maxn][30]; int pos[maxn][30]; int insert(int k,int w) { for(int i=0;i<=25;i++) { per[k][i]=per[k-1][i]; pos[k][i]=pos[k-1][i]; } int ans=k; for(int i=25;i>=0;i--) { if(w&(1<<i)) { if(!per[k][i]) { per[k][i]=w; pos[k][i]=ans; break; } else{ if(ans>pos[k][i]) { swap(ans,pos[k][i]); swap(w,per[k][i]); } w^=per[k][i]; } } } return w>0;// 等于0表示能表示 } int main() { int n; scanf("%d",&n); for(int i=1;i<=n;i++) { int w; scanf("%d",&w); insert(i,w); } int m; scanf("%d",&m); while(m--) { int l,r; scanf("%d%d",&l,&r); int ans=0; for(int i=25;i>=0;i--) { if(per[r][i]>0&&pos[r][i]>=l)// { ans=max(ans,ans^per[r][i]); } } printf("%d\n",ans); //cout<<ans<<endl; } return 0; }
