终于又做了一道线性基！

前缀线性基求区间最大异或值

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. 1,x 在数组末尾插入一个x(但x需要解码)
  2. 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;
    }
}