最大异或和（冬季每日一题 1）

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

请在所有长度不超过

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

注意：子数组可以为空。

输入格式

第一行包含两个整数 。

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

输出格式

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

数据范围

对于 20% 的数据，

对于 50% 的数据，

对于 100% 的数据，

输入样例：

3 2
1 2 4      

输出样例：

6      

思路：

#include<iostream>

using namespace std;

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

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

void insert(int x, int v){
    
    int t = 0;
    for(int i = 30; i >= 0; i--){ // 从高位枚举
        
        int d = x >> i & 1;
        if(!tr[t][d]) tr[t][d] = ++ idx;
        t = tr[t][d];
        cnt[t] += v;
    }
}


int query(int x){
    
    
    int t = 0, res = 0;
    for(int i = 30; i >= 0; i--){
        
        int d = x >> i & 1;
        if(cnt[tr[t][!d]]){
            
            res = (res << 1) | 1;
            t = tr[t][!d];
        }else{
            
            res <<= 1;
            t = tr[t][d];
        }
    }
    
    return res;
}

int main(){
    
    scanf("%d%d", &n, &m);
    
    for(int i = 1; i <= n; i++) {
        scanf("%d", &s[i]);
        s[i] ^= s[i-1];
    }
    
    insert(s[0], 1);  // s[m] - s[0] = a[1 ~ m]
    
    int res = 0, x;
    for(int i = 1; i <= n; i++){
        
        if(i > m) insert(s[i - m - 1], -1);
        insert(s[i], 1);
        x = query(s[i]);
        res = max(res, x);
    }
    
    printf("%d\n", res);
    
    return 0;
}