Nikitosh 和异或(trie树)

题目：

#10051. 「一本通 2.3 例 3」Nikitosh 和异或

解析：

首先我们知道一个性质\(x\oplus x=0\)
我们要求\[\bigoplus_{i = l}^ra_i\]的话，相当于求\[(\bigoplus_{i = 1}^la_i)\oplus (\bigoplus_{i = 1}^ra_i)\]
所以我们维护一个异或前缀和\(sum_i\)
我们用\(l_i\)表示从左往右到第\(i\)位时的区间最大异或和
\(r_i\)表示从右往左到第\(i\)位时的区间最大异或和
显然\(l_i = max\{sum_L\oplus sum_R\}1\leq L<R\leq i\)
\(r_i\)同理
最后枚举求和\(ans=max\{ans,l_i+r_{i+1}\}\)

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 5e6 + 10;

int n, m, num, ans;
int a[N], sum[N], l[N], r[N];

struct node {
    int nx[2];
} e[N]; 

void insert(int x) {
    bitset<35>b(x);
    int rt = 0;
    for (int i = 30; i >= 0; --i) {
        int v = (int)b[i];
        if (!e[rt].nx[v]) e[rt].nx[v] = ++num;
        rt = e[rt].nx[v];
    }
}

int query(int x) {
    bitset<35>b(x);
    int rt = 0, ret = 0;
    for (int i = 30; i >= 0; --i) {
        int v = (int)b[i];
        if (e[rt].nx[v ^ 1]) ret = ret << 1 | 1, rt = e[rt].nx[v ^ 1];
        else ret <<= 1, rt = e[rt].nx[v];
    }
    return ret;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]), sum[i] = sum[i - 1] ^ a[i];
    insert(0);
    for (int i = 1; i <= n; ++i) {
        ans = max(ans, query(sum[i]));
        l[i] = ans;
        insert(sum[i]);
    }
    num = ans = 0;
    memset(e, 0, sizeof e);
    for (int i = n; i >= 1; --i) {
        ans = max(ans, query(sum[i]));
        r[i] = ans;
        insert(sum[i]);
    }
    ans = 0;
    for (int i = 1; i < n; ++i) ans = max(ans, l[i] + r[i + 1]);
    cout << ans;
}

原文链接:https://www.cnblogs.com/lykkk/p/11265899.html
如有疑问请与原作者联系

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有