最大异或和

题目描述

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

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

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

注意：子数组可以为空。

输入格式

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

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

输出格式

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

数据范围

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

输入样例：

3 2
1 2 4

输出样例：

6

思路

前缀和+trie+滑动窗口+贪心

• 对于从区间$[n,m]$的异或和可以表示为$s[m] \bigoplus s[n-1]$，可以先使用前缀和的思想，求出前缀异或和的结果

• 贪心：对于每一个树要异或和最大，就需要高位不同，从高到低枚举每个数的每一位，在前缀和中查询是否存在不同的位，计算最大值

• 滑动窗口，要求区间的长度不超过$m$，如果长度超过$m$，就删除前面添加到trie中的元素

实现代码

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 30 * 100010;
// 每个数最多有30个点，
int cnt[N], idx;
int son[N][2], s[100010];
int n, m;
// 1表示插入，0表示删除
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;
    int res = 0;
    for(int i = 30;i >= 0;i --)
    {
        int u = x >> i & 1;
        if(cnt[son[p][!u]]) res = res * 2 + 1, p = son[p][!u];
        else res = res * 2, p = son[p][u];
    }
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);   
    // 求异或和
    for(int i = 1;i <= n;i ++)
    {
        int x;
        scanf("%d",&x);
        s[i] = s[i -1] ^ x;
    }

    int res = 0;
    insert(0, 1);
    for(int i = 1;i <= n;i ++)
    {
        // 这里是删除i-m-1是因为 需要用的其实是比区间长度的位置多1
        if(i > m) insert(s[i - m - 1], -1);
        res = max(res,query(s[i]));
        insert(s[i],1);
    }
    printf("%d",res);
    return 0;
}