Operation
Operation
題意:0 l rはl,rの間で任意にいくつかの数を選択して異或値を最大にする.1 x末尾にx値を挿入します.
考え方:接頭辞の線形ベースを維持すればいい.
題意:0 l rはl,rの間で任意にいくつかの数を選択して異或値を最大にする.1 x末尾にx値を挿入します.
考え方:接頭辞の線形ベースを維持すればいい.
#include
using namespace std;
const int N=1e6+5;
int n,q,c[N];
int pos[N][30],p[N][30];
void insert(int x,int num){
for(int i=0;i<30;i++){
pos[x][i]=pos[x-1][i];
p[x][i]=p[x-1][i];
}
int tmp=num;
int id=x;
for(int i=29;i>=0;i--){
if((tmp>>i)&1){
if(!p[x][i]){
p[x][i]=tmp;
pos[x][i]=id;
return;
}
if(pos[x][i]=0;i--)
if(pos[r][i]>=l&&(res^p[r][i])>res)
res^=p[r][i];
return res;
}
int main(){
int T;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&q);
for(int i=0;i<30;i++)
pos[0][i]=p[0][i]=0;
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
insert(i,x);
}
int last=0;
int op,l,r,x;
while(q--){
scanf("%d",&op);
if(op==0){
scanf("%d%d",&l,&r);
l=(l^last)%n+1;
r=(r^last)%n+1;
if(l>r)
swap(l,r);
printf("%d
",last=ask(l,r));
}
else{
scanf("%d",&x);
x^=last;
insert(++n,x);
}
}
}
return 0;
}