F. Ivan and Burgers 前缀线性基

F. Ivan and Burgers 前缀线性基

传送门

题意：首先输入n，代表当前有n个数，然后再输入m，代表m次询问，每一次询问是询问区间[l,r]，这段区间内的数的最大异或值。

思路：处理出来一个前缀线性基，记录线性基上该位置是在原序列的哪个位置，求值的时候在第r个线性基上找，如果位置>=l则是合法的。如果有两个相同的数在同一位，遇到这种情况则用贪心的想法，如果在同一位上明显原序列越大的数越优，因为如果把原序列小的留下，则区间长度较小时明显没有原序列大的数更优，所以贪心的留下原序列大的。和这题很像

    #include<iostream>#include<algorithm>#include<cmath>#include<cstdio>#include<cstring>#define ll long longusing 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("%dn",ans);//cout<<ans<<endl;}return 0;}