人生第一道Ynoi，开心

https://www.luogu.com.cn/problem/P5607

拿到这个题，看了一下，发现询问要求最大异或和，怎么办？

没办法，我只学过线性基，就顺着这个思路硬上吧。

我们开一颗线段树，里面的节点存线性基，那么空间复杂度是\(O(n \log v)\)的

先不管修改操作，那么我们容易分析得到单次查询的复杂度是\(O(\log n \log^2 v)\)

这个复杂度一看就是正解，接着想修改

区间\(\text{xor}\)还得维护线性基？？？什么鬼？？？

我们想，区间\(\text{xor}\)在线段树上难以办到，但是单点\(\text{xor}\)很简单

怎么办？

差分啊！！！

但我们怎么差分才能保证正确性呢？

熟知，对于一个数列\(a_n\)

如果我们把它差分，使得\(b_1 = a_1, b_i = a_i \text{xor} a_{i-1} (i>1)\)

那么由线性代数基础知识，数列\(b_n\)的线性基和原数列的线性基是一样的

这启发我们线段树维护差分的线性基，然后再单独维护\(a\)，询问时将\(a\)插入线段树查询得到的线性基、

这个\(a\)就很好维护了，直接上线段树或者树状数组维护差分即可

这样，单次修改复杂度为\(O(\log n \log v)\)

#include <cstdio>
#include <iostream>
using namespace std;
const int N = 50010;
int n, m, a[N], b[N], opt, l, r, v;
inline int read() {
    int res = 0, flag = 0; char ch = getchar();
    for(; !isdigit(ch); ch = getchar()) if(ch == '-') flag = 1;
    for(; isdigit(ch); ch = getchar()) res = (res << 1) + (res << 3) + (ch ^ 48);
    if(flag) res = ~res + 1;
    return res;
}
struct LineBase{
    int a[31];
    inline void clear() {for(int i = 0; i < 31; ++i) a[i] = 0;}
    inline void insert(int x) {
        for(int i = 30; i + 1; --i)
            if(x & (1 << i))
                if(!a[i]) {a[i] = x; break;}
                else x ^= a[i];
    }
}O;
inline LineBase merge(LineBase x, LineBase y) {
    for(int i = 30; i + 1; --i) if(y.a[i]) x.insert(y.a[i]);
    return x;
}
struct SegmentTree{
    #define lc (k << 1)
    #define rc (lc | 1)
    #define mid (l + r >> 1)
    LineBase tr[N << 2];
    inline void update(int k) {tr[k] = merge(tr[lc], tr[rc]);}
    inline void build(int k, int l, int r) {
        if(l == r) {tr[k].insert(b[l]); return;}
        build(lc, l, mid), build(rc, mid + 1, r), update(k);
    }
    inline void modify(int k, int l, int r, int loc) {
        if(l > loc || r < loc) return ;
        if(l == r) {tr[k].clear(), tr[k].insert(b[l]); return;}
        modify(lc, l, mid, loc), modify(rc, mid + 1, r, loc), update(k);
    }
    inline LineBase query(int k, int l, int r, int L, int R) {
        if(l > R || r < L) return O;
        if(L <= l && r <= R) return tr[k];
        return merge(query(lc, l, mid, L, R), query(rc, mid + 1, r, L, R));
    }
}s;
struct BIT{
    #define lowbit(x) (x & -x)
    int tr[N];
    inline void insert(int x, int v) {for(; x <= n; x += lowbit(x)) tr[x] ^= v;}
    inline int query(int x) {int res = 0; for(; x; x -= lowbit(x)) res = res ^ tr[x]; return res;}
}bit;
inline void out(int x) {
    int flag = 0;
    for(int i = 30; i + 1; --i)
        if(flag) printf("%d",((x & (1 << i)) > 0));
        else if(x & (1 << i)) printf("1"), flag = 1;
    if(!flag) printf("0");
}
int main() {
    n = read(), m = read();
    for(int i = 1; i <= n; ++i) a[i] = read(), b[i] = a[i] ^ a[i - 1], bit.insert(i, b[i]); b[n + 1] = a[n];
    s.build(1, 1, n + 1);
    for(int i = 1; i <= m; ++i) {
        opt = read(), l = read(), r = read(), v = read();
        if(opt == 1) {
            b[l] ^= v, b[r + 1] ^= v;
            bit.insert(l, v), bit.insert(r + 1, v);
            s.modify(1, 1, n + 1, l), s.modify(1, 1, n + 1, r + 1);
        }
        else {
            LineBase ans = s.query(1, 1, n + 1, l + 1, r);
            ans.insert(bit.query(l));
            for(int j = 30; j + 1; --j) if((ans.a[j] ^ v) > v) v ^= ans.a[j];
            printf("%d\n",v);
        }
    }
    return 0;
}