2019 Multi-University Training Contest 1 1002 Operation 线性基

## 题目大意

0操作：询问l-----r区间内所有数中部分数通过异或运算所组成的所有数中的最大值。

1操作：在序列尾部插入值x。

## 代码

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<3) + (num<<1) + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn =  5e5+5;
int n,m;
int T;
int opt,l,r,x;
int f[maxn<<1][31],id[maxn<<1][31];
int last;
int k = pos;
for(int j = 30;j >= 0;--j)
f[pos][j] = f[pos-1][j],id[pos][j] = id[pos-1][j];
for(int j = 30;j >= 0;--j){
if(x & (1<<j)){
if(!f[pos][j]){
f[pos][j] = x;
id[pos][j] = k;
break;
}
else{
if(k > id[pos][j]){
swap(k,id[pos][j]);
swap(x,f[pos][j]);
}
x ^= f[pos][j];
}
}
}
return;
}
int main(){
T = get_num();
while(T--){
n = get_num();
m = get_num();
last = 0;
for(int i = 1;i <= n+m;++i)
for(int j = 0;j <= 30;++j)f[i][j] = 0;
for(int i = 1;i <= n;++i){
x = get_num();
}
while(m--){
opt = get_num();
if(opt == 1){
x = get_num();
x ^= last;
}
else if(opt == 0){
l = get_num();
r = get_num();
l = (l ^ last) % n + 1;
r = (r ^ last) % n + 1;
last = 0;
if(l > r)swap(l,r);
for(int j = 30;j >= 0;--j){
if(id[r][j] >= l && (last ^ f[r][j]) > last)
last ^= f[r][j];
}
printf("%d\n",last);
}
}
}
return 0;
}```

0 条评论