https://vjudge.net/problem/HDU-6579
题意：
给出n个数，接下来有m次操作。
1 k：在数组后面多加一个k。（n=n+1）。
0 l r：询问[l,r]区间内任意取数，异或和的最大值。
特别要注意的是2种操作都加密了，1号操作需要k=k^lasten;2号操作需要l=(l^lasten)%n+1,r=(r^lasten)%n+1.lasten初始值为0，以后lasten为上一次0号操作的答案。
思路：
前缀线性基。建立二维数组pre_p[1000009][maxbit]，表示从1~i前i个数组成的线性基。建立数组pre_pos[1000009][maxbit],表示对于第i个前缀线性基第j位为1的数的最大下标（另一种理解： 对于区间[1,i]内的数，二进制第j位为1的最大下标。可能是由不止一个数异或而成的，此时记录这几个数的最小下标）。
对于每一次1号操作，都要在重新维护pre_p数组和pre_pos数组。
对于0号操作，我们按普通的线性基用法使用pre_p[r],不同的就是对于每一个不为0的pre_p[r][j]都要判断pre_pos[r][j]>=l是否成立。即当右端点固定为r时，pre[r][j]是否可以在l以后出现。
（本人原本maxbit开的是32，然后一直血wa，换成31就过了，血的教训）
#include<bits/stdc++.h>
using namespace std;
const int maxbit=31;
#define met(a,b) memset(a,b,sizeof(a))
int p[maxbit+5],pos[maxbit+5],pre_p[1000009][maxbit],pre_pos[1000009][maxbit];
void solve(int val,int adr )//建立1~adr的前缀线性基
{
int k=adr;
for(int i=maxbit-1; i>=0; i--)
{
if((val>>i)&1)//
{
if(!p[i])
{
// cout<<(val>>i)<<endl;
// cout<<i<<"__________ "<<p[i]<<"....."<<val<<endl;
p[i]=val;
pos[i]=adr;
break;
}
else
{
if(pos[i]<adr)swap(p[i],val),swap(adr,pos[i]);//本题重点代码，更新二进制第i为1的下标
val^=p[i];//新的val是原val与原p[i]异或得到的，所以adr应该是2者较小的下标（即原p[i]的下标），所以上面用swap而不是赋值。
}
}
}
for(int i=0; i<=maxbit-1; ++i)
{
pre_p[k][i]=p[i];
pre_pos[k][i]=pos[i];
}
}
int seek_ans(int l,int r)//在区间[l,r]内搜寻答案
{
if(l>r) swap(l,r);
int k=0;
for(int i=maxbit-1; i>=0; i--)
{
if(pre_p[r][i] &&pre_pos[r][i]>=l)
k=max(k,k^pre_p[r][i]);
}
return k;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
int T;
cin>>T;
while(T--)
{
int n,m,k;
cin>>n>>m;
for(int i=1; i<=n; i++)
{
cin>>k;
solve(k,i);
}
int lastans=0;
for(int t=0; t<m; t++)
{
int f;
cin>>f;
if(f)
{
cin>>k;
k^=lastans;//解密
solve(k,++n);//建立线性基
}
else
{
int l,r;
cin>>l>>r;
lastans=seek_ans((l^lastans)%n+1,(r^lastans)%n+1);//解密找答案
cout<<lastans<<endl;
}
}
for(int j=maxbit-1;j>=0;--j) p[j]=pos[j]=0;//初始化
for(int i=0;i<=n;i++)
{
for(int j=maxbit-1;j>=0;--j)
pre_p[i][j]=pre_pos[i][j]=0;
}
}
return 0;
}