Nikitosh 和异或

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1900 字
前缀异或加 Trie 求左右最大子段异或
一本通
例
正文

// 原题：https://oj.yecheng.tv/p/T1473
// 题意：给定数组 A，求两个不相交区间 [l1,r1] 与 [l2,r2]（前者整体在后者之前）的区间异或和之和的最大值。
// 思路：令前缀异或 s[i]。用 01 Trie 求出 left[i]（[1,i] 内最大子段异或）与 right[i]（[i,n] 内最大子段异或），答案即 max(left[i] + right[i+1])。
// 复杂度：O(N × 31) 时间 / O(N × 31) 空间
// 易错点：前缀异或要把 s[0]=0 也插进 Trie，否则漏掉从 1 开始的子段。
// 易错点：两个区间必须不相交且有序，枚举分界点 i 时是 left[i]+right[i+1]，写成 right[i] 会让两区间重叠。
#include <bits/stdc++.h>
using namespace std;
struct Node {
    int ch[2];
    Node(){
        ch[0] = ch[1] = 0;
    }
};
vector<Node> tr;
void insertVal(int x){
    int u = 0;
    for(int i = 30; i >= 0; i--){
        int b = (x >> i) & 1;
        if(!tr[u].ch[b]){
            tr[u].ch[b] = (int)tr.size();
            tr.push_back(Node());
        }
        u = tr[u].ch[b];
    }
}
int queryVal(int x){
    int u = 0;
    int res = 0;
    for(int i = 30; i >= 0; i--){
        int b = (x >> i) & 1;
        if(tr[u].ch[b ^ 1]){
            res |= (1 << i);
            u = tr[u].ch[b ^ 1];
        }else{
            u = tr[u].ch[b];
        }
    }
    return res;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    if(!(cin >> n)) return 0;
    vector<int> s(n + 1, 0);
    for(int i = 1; i <= n; i++){
        int x;
        cin >> x;
        s[i] = s[i - 1] ^ x;
    }
    int cap = (n + 2) * 31;
    vector<int> left(n + 2, 0), right(n + 2, 0);
    tr.reserve(cap);
    tr.push_back(Node());
    insertVal(0);
    for(int i = 1; i <= n; i++){
        int v = queryVal(s[i]);
        left[i] = max(left[i - 1], v);
        insertVal(s[i]);
    }
    tr.clear();
    tr.push_back(Node());
    insertVal(s[n]);
    for(int i = n; i >= 1; i--){
        insertVal(s[i - 1]);
        int v = queryVal(s[i - 1]);
        right[i] = max(right[i + 1], v);
    }
    int ans = 0;
    for(int i = 1; i < n; i++){
        ans = max(ans, left[i] + right[i + 1]);
    }
    cout << ans << "\n";
    return 0;
}
Nikitosh 和异或

正文

一本通·提高篇的其它内容
