HDU-6579 Operation(多校1B)(线性基)
终于又做了一道线性基！
前缀线性基求区间最大异或值
Operation
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 262144/262144 K (Java/Others)
Total Submission(s): 1073 Accepted Submission(s): 337
Problem Description
There is an integer sequence a of length n and there are two kinds of operations:
0 l r: select some numbers from al…ar so that their xor sum is maximum, and print the maximum value.
1 x: append x to the end of the sequence and let n=n+1.
Input
There are multiple test cases. The first line of input contains an integer T(T≤10), indicating the number of test cases.
For each test case:
The first line contains two integers n,m(1≤n≤5×105,1≤m≤5×105), the number of integers initially in the sequence and the number of operations.
The second line contains n integers a1,a2,…,an(0≤ai<230), denoting the initial sequence.
Each of the next m lines contains one of the operations given above.
It’s guaranteed that ∑n≤106,∑m≤106,0≤x<230.
And operations will be encrypted. You need to decode the operations as follows, where lastans denotes the answer to the last type 0 operation and is initially zero:
For every type 0 operation, let l=(l xor lastans)mod n + 1, r=(r xor lastans)mod n + 1, and then swap(l, r) if l>r.
For every type 1 operation, let x=x xor lastans.
Output
For each type 0 operation, please output the maximum xor sum in a single line.
Sample Input
1
3 3
0 1 2
0 1 1
1 3
0 3 4
Sample Output
1
3
题意：给定一个数组，有两个操作
- 1,x 在数组末尾插入一个x(但x需要解码)
- 0,l,r 在数组[l,r]之间任取数字进行异或，求出最大可能的异或值(l,r也需要解码)
//#pragma comment(linker, "/STACK:102400000,102400000")
#include "bits/stdc++.h"
#define pb push_back
#define ls l,m,now<<1
#define rs m+1,r,now<<1|1
#define hhh printf("hhh\n")
#define see(x) (cerr<<(#x)<<'='<<(x)<<endl)
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
inline int read() {int x=0;char c=getchar();while(c<'0'||c>'9')c=getchar();while(c>='0'&&c<='9')x=x*10+c-'0',c=getchar();return x;}
const int maxn = 5e5+10;
const int mod = 1e9+7;
const double eps = 1e-9;
int f[maxn][32], pos[maxn][32]; //f用来保存f[r]出的前缀线性基,pos[i][j]用来记录f[i][j]在原数组中的位置
inline void add(int i, int x) {
int k=i;
for(int j=0; j<=30; ++j) f[i][j]=f[i-1][j], pos[i][j]=pos[i-1][j];
for(int j=30; j>=0; --j) if(x>>j) {
if(!f[i][j]) {
f[i][j]=x, pos[i][j]=k;
break;
}
else {
if(k>pos[i][j]) swap(k,pos[i][j]), swap(x,f[i][j]); //贪心的将高位相同但位置更靠后的放在高位
x^=f[i][j];
}
}
}
int main() {
//ios::sync_with_stdio(false);
int T=read();
while(T--) {
int n=read(), m=read();
for(int i=1; i<=n; ++i) add(i,read());
int ans=0;
while(m--) {
if(read()) add(++n,read()^ans);
else {
int l=(read()^ans)%n+1, r=(read()^ans)%n+1; //由于l,r,x是编码过的，所以读入后要记得解码
if(l>r) swap(l,r);
ans=0;
for(int i=30; i>=0; --i)
if((ans^f[r][i])>ans&&pos[r][i]>=l) ans^=f[r][i]; //还是正常的求最大值，但是这个基底必须是由[l,r]区间内的数得到的。
printf("%d\n", ans);
}
}
for(int i=1; i<=n; ++i)
for(int j=0; j<=30; ++j) f[i][j]=pos[i][j]=0;
}
}
