传送门

题意是说会依次给m次操作，要么在序列后面加一个数，要么问你区间[L, R]里的最大异或和。

做法很有技巧。维护前缀的线性基。f[x][i]代表前x个数第i位的代表的基是哪个数。

但是不是一般的方法直接维护，而是只留下最靠后加入的。所以还需要一个pos[x][i]代表f[x][i]是第几个数。

这样在查询f[r][i]的时候如果第i位的pos是小于l的(pos[r][i] < l)，这一位就不合法舍去。

因为在插入的时候是在此位存在的情况下维护尽量靠后的。所以答案一定是最大的。

#include<bits/stdc++.h>
using namespace std;
const int maxn = 5e5 + 233;
int f[maxn][33], pos[maxn][33];
inline int Read() 
{
    int x=0,f=1; char ch=getchar(); 
    while (ch<'0'||ch>'9') {if (ch=='-') f=-f; ch=getchar();}
    while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*f;
}
char s[30];
inline void writeln(int x)
{
    if (x<0) putchar('-'),x=-x; 
    if (!x) putchar('0'); else 
    {
        int len=0;  
        while (x) s[++len]=x%10+'0',x/=10;
          while (len) putchar(s[len--]);
    } 
    putchar('\n');
}
void add(int x, int v)
{
    for(int i = 30; i >= 0; --i) f[x][i] = f[x - 1][i], pos[x][i] = pos[x - 1][i];
    int t = x;
    for(int i = 30; i >= 0; --i)
    {
        if(v >> i)
        {
            if(!f[x][i]) 
            {
                f[x][i] = v, pos[x][i] = t;
                break;
            }
            else  
            {
                if(pos[x][i] < t)
                    swap(pos[x][i], t), swap(f[x][i], v);
                v ^= f[x][i];
            }
        }
    }
}
int main()
{
    int T; 
    scanf("%d", &T);
    while(T--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        int k;
        for(int i = 1; i <= n; ++i) k = Read(), add(i, k);
        int ans = 0;
        int l, r; 
        for(int j = 1; j <= m; ++j)
        {
            int op; //scanf("%d", &op);
            op = Read();
            if(op == 0)
            {
                //scanf("%d%d", &l, &r);
                l = Read(), r = Read();
                l ^= ans, r ^= ans;
                l = l % n + 1, r = r % n + 1;
                if(l > r) swap(l, r);
                ans = 0;
                for(int i = 30; i >= 0; --i)
                {
                    if(pos[r][i] >= l && ((ans ^ f[r][i]) > ans)) ans ^= f[r][i];
                }
                printf("%d\n", ans);
            }
            else 
            {
                //scanf("%d", &k); 
                k = Read();
                add(++n, k ^ ans);
            }
        }
        // puts("");
    }
}