思路

可持久化入门题.
首先,如果不是区间,而是整体询问的话,我们可以直接建,从高位到低位枚举,答案的这一位能是1就为1,不然只能为0.
区间询问的话其实相差不大.使用可持久化树,这样就知道每个前缀序列构成的树.还需要记录每个节点总共经过了几次.然后在两棵树上跑,这里判断是否有节点作差即可(类似于前缀和的思想).
算法时空复杂度为.

代码

#include<bits/stdc++.h>
using namespace std;
#define MAXN 300005
#define len 25

int N, M;
int T[MAXN<<1];
int tr[MAXN * 52][2], cnt[MAXN * 52], tot;

void ins( int pre, int c, int x, int cur ){
    cnt[c] = cnt[pre] + 1; if ( cur < 0 ) return;
    int t(( x >> cur ) & 1);
    tr[c][!t] = tr[pre][!t], ins( tr[pre][t], tr[c][t] = ++tot, x, cur - 1 );
}

int GetMax( int pre, int c, int x, int cur ){
    if ( cur < 0 ) return 0;
    int t(( x >> cur ) & 1);
    if ( cnt[tr[c][!t]] - cnt[tr[pre][!t]] > 0 ) return GetMax( tr[pre][!t], tr[c][!t], x, cur - 1 ) | ( 1 << cur );
    return GetMax( tr[pre][t], tr[c][t], x, cur - 1 );
}

int main(){
    scanf( "%d%d", &N, &M );
    int t, l, r, c(0); char opt; ins( 0, T[1] = ++tot, 0, len );
    for ( int i = 1; i <= N; ++i ) scanf( "%d", &t ), c ^= t, ins( T[i], T[i + 1] = ++tot, c, len );
    while( M-- ){
        while( ( opt = getchar() ) != 'A' && opt != 'Q' );
        if ( opt == 'A' ){
            scanf( "%d", &t );
            c ^= t, N++;
            ins( T[N], T[N + 1] = ++tot, c, len );
        } else
            scanf( "%d%d%d", &l, &r, &t ), t ^= c, printf( "%d\n", GetMax( T[l - 1], T[r], t, len ) );
    }
    return 0;
}