Luogu4735 最大异或和

题目蓝链

Description

给你一个序列，你需要支持以下两个操作：

1. A x: 在序列尾部添加一个整数(x)，序列的长度增加(1)
2. Q l r x: 询问操作，你需要找到一个位置(p in [l,r])，使得：(x bigoplus a_p bigoplus a_{p + 1} bigoplus ldots bigoplus a_n)最大，输出最大值是多少

Solution

首先我们需要打一个可持久化的(trie)树来维护(a_i)的前缀和，这样我们就可以快速在一段区间对应的(trie)树上查询，查询的时候我们只需要贪心的找就可以了

另外，我们需要把询问的式子转化一下
[ x bigoplus a_p bigoplus a_{p + 1} bigoplus ldots bigoplus a_n = (x bigoplus all) bigoplus a_1 bigoplus a_2 bigoplus ldots bigoplus a_{p - 1} ]
由于对于当前的询问，(x bigoplus all)为定值，所以我们只需要在(trie)树上找到一个(a_1 bigoplus a_2 bigoplus ldots bigoplus a_{p - 1})，使其与(x bigoplus all?)的异或和最大即可

Code

#include <bits/stdc++.h>

using namespace std;

#define fst first
#define snd second
#define mp make_pair
#define squ(x) ((LL)(x) * (x))
#define debug(...) fprintf(stderr,__VA_ARGS__)

typedef long long LL;
typedef pair<int,int> pii;

template<typename T> inline bool chkmax(T &a,const T &b) { return a < b ? a = b,1 : 0; }
template<typename T> inline bool chkmin(T &a,const T &b) { return a > b ? a = b,1 : 0; }

inline int read() {
    int sum = 0,fg = 1; char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == ‘-‘) fg = -1;
    for (; isdigit(c); c = getchar()) sum = (sum << 3) + (sum << 1) + (c ^ 0x30);
    return fg * sum;
}

const int maxn = 3e5 + 10;
const int inf = (1 << 24) - 1;

int n,m,a[maxn << 1],rt[maxn << 1];

namespace ST {
    struct node {
        int ls,rs,v;
    }A[maxn << 6];
#define ls(x) A[x].ls
#define rs(x) A[x].rs
    int cnt;
    void change(int &nrt,int rt,int l,int r,int x) {
        A[nrt = ++cnt] = A[rt],++A[cnt].v;
        if (l == r) return;
        int mid = (l + r) >> 1;
        if (x <= mid) change(ls(nrt),ls(rt),l,mid,x);
        else change(rs(nrt),rs(rt),mid + 1,r,x);
    }
    int query(int x,int y,int v) {
        if (l == r) return l;
        int mid = (l + r) >> 1,len = r - mid;
        if (v <= mid) {
            if (A[ls(y)].v - A[ls(x)].v) return query(ls(x),ls(y),v);
            return query(rs(x),rs(y),v + len);
        } else {
            if (A[rs(y)].v - A[rs(x)].v) return query(rs(x),v);
            return query(ls(x),v - len);
        }
        return 0;
    }
}

int main() {
#ifdef xunzhen
    freopen("xor.in","r",stdin);
    freopen("xor.out","w",stdout);
#endif

    n = read(),m = read();
    for (int i = 1; i <= n; i++) {
        a[i] = a[i - 1] ^ read();
        ST::change(rt[i],rt[i - 1],inf,a[i - 1]);
    }
    for (int i = 1; i <= m; i++) {
        static char s[10];
        scanf("%s",s);
        if (s[0] == ‘A‘) {
            ++n,a[n] = a[n - 1] ^ read();
            ST::change(rt[n],rt[n - 1],a[n - 1]);
        } else {
            int l = read(),r = read(),x = read() ^ a[n];
            printf("%dn",ST::query(rt[l - 1],rt[r],inf ^ x) ^ x);
        }
    }

    return 0;
}