Luogu

BZOJ

分析

异或满足可减性，所以可以维护前缀和，然后

$\mathrm{a[p]\ xor\ a[p+1]\ xor\ ...\ xor\ a[n]\ xor\ x=s[p-1]\ xor\ s[n]\ xor\ x}$

然后就只要维护$s[]$。添加很好维护，重点是如何查询。

此时查询转变为：已知$val=\mathrm{s[n]\ xor\ x}$，求一个$p\in[l-1,r-1]$，使得$\mathrm{s[p]\ xor\ val}$最大。

可以构建一颗可持久化$\mathrm{Trie}$，第$i$个版本为插入了$s[i]$后的$\mathrm{Trie}$树。

每次查询，从根节点开始，贪心地选与这一位相反的值。

此外，还有一个$l-1\leq p\leq r-1$的限制。

先考虑$p\leq r-1$，查询第$r-1$个版本的$\mathrm{Trie}$即可，因为此时不可能访问到$r-1$之后的$s$。
再考虑$l-1\leq p$，对每个节点维护一个$latest$值，表示子树中所有$s$值的下标的最大值。这样，在查询时只访问$latest\geq l-1$的节点就行了。

代码

//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

namespace io {
    const int SIZE=(1<<21)+1;
    char ibuf[SIZE],*iS,*iT,obuf[SIZE],*oS=obuf,*oT=oS+SIZE-1,c,qu[55]; int f,qr;
    inline char gc() { return (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),(iS==iT?EOF:*iS++)):*iS++); }
    inline void flush() {
        fwrite(obuf,1,oS-obuf,stdout);
        oS=obuf;
    }
    inline void putc(char x) {
        *oS++=x;
        if (oS==oT) flush();
    }
    template <class I>
    inline void read(I &x) {
        for (f=1,c=gc();c<'0'||c>'9';c=gc()) if (c=='-') f=-1;
        for (x=0;c<='9'&&c>='0';c=gc()) x=x*10+(c&15); x*=f;
    }
    template <class I>
    inline void print(I x) {
        if (!x) putc('0'); if (x<0) putc('-'),x=-x;
        while (x) qu[++qr]=x%10+'0',x/=10;
        while (qr) putc(qu[qr--]);
    }
}
using io::gc;
using io::read;
using io::print;
using io::putc;

const int MAXN=600010+10;

int trie[MAXN*24][2],latest[MAXN*24];
int s[MAXN],root[MAXN];
int n,m,tot;

inline void insert(int i,int k,int p,int q) {
    if (k<0) { latest[q]=i; return; }
    int c=s[i]>>k&1;
    if (p) trie[q][c^1]=trie[p][c^1];
    trie[q][c]=++tot;
    insert(i,k-1,trie[p][c],trie[q][c]);
    latest[q]=max(latest[trie[q][0]],latest[trie[q][1]]);
}

inline int query(int now,int val,int k,int L) {
    if (k<0) return s[latest[now]]^val;
    int c=val>>k&1;
    if (latest[trie[now][c^1]]>=L) return query(trie[now][c^1],val,k-1,L);
    else return query(trie[now][c],val,k-1,L);
}

int main() {
    read(n),read(m),latest[0]=-1,root[0]=++tot;
    insert(0,23,0,root[0]);
    for (re int i=1,x;i<=n;++i) {
        read(x),s[i]=s[i-1]^x,root[i]=++tot;
        insert(i,23,root[i-1],root[i]);
    }
    for (re int i=1,x,l,r;i<=m;++i) {
        char op=gc(); while (!isalpha(op)) op=gc();
        if (op=='A') {
            read(x),root[++n]=++tot,s[n]=s[n-1]^x;
            insert(n,23,root[n-1],root[n]);
        } else {
            read(l),read(r),read(x);
            print(query(root[r-1],s[n]^x,23,l-1)),putc('\n');
        }
    }
    io::flush();
    return 0;
}