题目描述

给定一个非负整数数列 a，初始长度为 N。

请在所有长度不超过M的连续子数组中，找出子数组异或和的最大值。

子数组的异或和即为子数组中所有元素按位异或得到的结果。

注意：子数组可以为空。

样例

3 2
1 2 4

Trie树

C++ 代码

//主要思想还是靠 a ^ x ^ x = a

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010 * 31; //每个数都会表示成 31 位， 故需要开 100010 * 31 的空间

int son[N][2], cnt[N], idx;

int s[N], a[N];

void insert(int x, int v)
{
    int p = 0;
    for(int i = 30; i >= 0; i --)
    {
        int u = x >> i & 1;
        if(!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
        cnt[p] += v;
    }
}

int query(int x)
{
    int p = 0, res = 0;
    for(int i = 30; i >= 0; i --)//  秦九韶算法
    {
        int u = x >> i & 1;
        if(cnt[son[p][!u]])  p = son[p][!u], res = res * 2 + 1; //从高位开始走，如果存在与它相反的，那么这一位异或之后为1, 结果中需要加上1
        else p = son[p][u], res = res * 2;//如果不存在，那么这一位异或之后为0，也就是这一位会为0，故不需加1
    }
    return res;
}

int main()
{
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i ++)
    {
        cin >> a[i];
        s[i] = s[i - 1] ^ a[i];
    }
    int ans = 0;
    insert(s[0], 1);  //s[0] 也要压入trie树中，保证a[1], a[2], 或者别的数压入
    for(int i = 1; i <= n; i ++)
    {
        if(i - m - 1 >= 0) insert(s[i - m - 1], -1); 
        ans = max(ans, query(s[i]));
        insert(s[i], 1);
    }
    cout << ans;
    return 0;
}