BZOJ-4260___Codechef REBXOR —— 01字典树 + DP

题目链接：点我啊╭(╯^╰)╮

题目大意：

    求两个不相交区间的最大连续异或和

解题思路：

    预处理前后缀异或，区间 $i$ ~ $j$ 的异或为 $pre[j]?pre[i]$ $(i<j)$
    $dp[i]$ 为 $i$ 之前任意一段区间的最大异或值
    $dp[i]=max(dp[i?1],max(pre[i]?pre[1$ ~ $i?1]))$
    可以用 $01$ 字典树查询
    另一段区间倒过来做即可

核心：01字典树模板题

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
using namespace std;
typedef long long ll;struct Trie{static const int maxt = 1e7+5;int rt, id, tot, t[maxt][2];int cnt[maxt], val[maxt], end[maxt];inline int newnode(){++tot;t[tot][0] = t[tot][1] = 0;cnt[tot] = end[tot] = val[tot] = 0;return tot;}inline void init(){tot = 0;rt = newnode();}inline void add(int x){rt = 1;for(int i=31; ~i; i--){id = x >> i & 1;if(!t[rt][id]) t[rt][id] = newnode();rt = t[rt][id];++cnt[rt];}end[rt] = 1, val[rt] = x;}inline int query(int x){rt = 1;for(int i=31; ~i; i--){id = x >> i & 1;if(t[rt][id^1]) rt = t[rt][id^1];else rt = t[rt][id];}return x ^ val[rt];}
} t; const int maxn = 4e5 + 5;
int n, a[maxn], pre[maxn], suf[maxn], dp[maxn];
int main() {scanf("%d", &n);for(int i=1; i<=n; i++) {scanf("%d", a+i);pre[i] = pre[i-1] ^ a[i];}for(int i=n; i; i--) suf[i] = suf[i+1] ^ a[i];t.init();t.add(0);for(int i=1; i<=n; i++){dp[i] = max(dp[i-1], t.query(pre[i]));t.add(pre[i]);}t.init();t.add(0);int ans = 0;for(int i=n; i; i--){ans = max(ans, dp[i-1] + t.query(suf[i]));t.add(suf[i]);}printf("%d\n", ans);
}