题目描述

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

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

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

注意：子数组可以为空。

输入格式

第一行包含两个整数 N,M。

第二行包含 N 个整数，其中第 i 个为 ai。

输出格式

输出可以得到的子数组异或和的最大值。

数据范围

对于 20% 的数据，1≤M≤N≤100
对于 50% 的数据，1≤M≤N≤1000
对于 100% 的数据，1≤M≤N≤10^5,0≤ai≤2^{31}−1

输入样例：

3 2
1 2 4

输出样例：

6

思路

由于数据范围比较大，暴力是不可能的。我们可以发现利用前缀和先预处理一下，这样我们求任意区间的连续子数组的异或和时就可以在O(1)的时间范围内得到，那么对于任意区间的异或和，我们可以通过任意选择预处理出的前缀和中的两个值来得到，但此时的时间复杂度仍然是O(N^2)，仍然不能满足要求。
此时，利用Trie这个数据结构可以帮助我们更高效的做到上述的操作。很显然，我们对于两个数（题目中已经说到数字最大不超过2^{31}-1即31位二进制数），我们应该贪心的从二进制位的高位开始往低位去比较，在有与当前位不同的数值时应该选择数值不同的这个子节点，否则只能选择相同的子节点。这样我们就能在在Trie中只做一遍就能找到当数与Trie中那个值异或值最大了。对于长度小于等于M这个条件，我们可以对Trie中的每个节点记录一个数cnt，当有数值应该从Trie中移除时就让每个位置上的cnt-1，这样即可达到从Trie中移除该数值的目的；同理，当有数值加入Trie时，将每一位的cnt+1即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 100010*31, M = 100010;

int n,m;
int s[M];
int son[N][2], cnt[N], idx;

//从高位开始往下贪心的做，高位不同影响大

void insert(int x, int v)   //v==1表示插入向trie中插入一个元素x，v==-1表示删除一个元素x
{
    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 res = 0, p = 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;
        else p = son[p][u], res = res * 2;
    }
    return res;
}

int main()
{
    cin>>n>>m;
    for(int i = 1; i<=n; i++)
    {
        int x;
        cin>>x;
        s[i] = s[i-1] ^ x;
    }

    int res = 0;
    insert(s[0],1);

    for(int i = 1; i<=n; i++)
    {
        if(i > m) insert(s[i-m-1], -1); //超过m个了，就将最前面的那个删除
        res = max(res, query(s[i]));
        insert(s[i],1);
    }
    cout<<res<<endl;
    return 0;
}