Luogu

分析

没想到差分 /ll

根据要求的东西，不难想到线性基。现在既然有一个区间询问，而且线性基还很好合并，那么可以想到在外面套一层线段树。

问题是区间修改时一个线性基如何整体异或一个值。考虑差分，变成单点修改，直接把叶节点线性基清空然后 pushup 上去即可。

可以证明 $a_{l..r}$ 的线性基和 $a_l\cup(a_i-a_{i-1})_{l+1..r}$ 的线性基是相同的，所以询问时求出 $[l+1,r]$ 的线性基然后把 $a_l$ 插入即可。我们还需要一个树状数组来维护 $a_i$ 的值。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
#define debug(...) fprintf(stderr,__VA_ARGS__)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=50000+10;

int n,Q,a[N];

struct LB {
    int b[35];
    LB() { memset(b,0,sizeof(b)); }
    void init() { memset(b,0,sizeof(b)); }
    void insert(int x) {
        for (int i=30;~i;--i) {
            if (!(x>>i)) continue;
            if (!b[i]) { b[i]=x; break; }
            x^=b[i];
        }
    }
    int query(int w) {
        for (int i=30;~i;--i)
            if ((w^b[i])>w) w^=b[i];
        return w;
    }
} H;

LB merge(LB a,LB b) {
    for (int i=30;~i;--i)
        if (b.b[i]) a.insert(b.b[i]);
    return a;
}

#define ls (o<<1)
#define rs (o<<1|1)
LB t[N<<2];
void pushup(int o) { t[o]=merge(t[ls],t[rs]); }
void build(int o,int l,int r) {
    if (l==r) { t[o].insert(a[l]); return; }
    int mid=(l+r)>>1;
    build(ls,l,mid),build(rs,mid+1,r);
    pushup(o);
}
void modify(int o,int l,int r,int p,int w) {
    if (l==r) { t[o].init(),t[o].insert(a[l]^=w); return; }
    int mid=(l+r)>>1;
    if (p<=mid) modify(ls,l,mid,p,w);
    else modify(rs,mid+1,r,p,w);
    pushup(o);
}
LB query(int o,int l,int r,int ql,int qr) {
    if (ql<=l&&r<=qr) return t[o];
    int mid=(l+r)>>1;
    if (qr<=mid) return query(ls,l,mid,ql,qr);
    else if (ql>mid) return query(rs,mid+1,r,ql,qr);
    else return merge(query(ls,l,mid,ql,mid),query(rs,mid+1,r,mid+1,qr));
}
#undef ls
#undef rs

int c[N];
void add(int x,int y) { for (;x<=n;x+=x&-x) c[x]^=y; }
int sum(int x) { int s=0; for (;x;x-=x&-x) s^=c[x]; return s; }

int main() {
    n=read(),Q=read();
    for (int i=1;i<=n;++i) a[i]=read();
    for (int i=n;i;--i) a[i]^=a[i-1];
    for (int i=1;i<=n;++i) add(i,a[i]);
    build(1,1,n);
    while (Q--) {
        int op=read(),l=read(),r=read(),w=read();
        if (op==1) {
            modify(1,1,n,l,w),add(l,w);
            if (r<n) modify(1,1,n,r+1,w),add(r+1,w);
        } else {
            H=l<r?query(1,1,n,l+1,r):LB();
            H.insert(sum(l));
            printf("%d\n",H.query(w));
        }
    }
    return 0;
}