AcWing
3485. 最大异或和
异或的性质：
$a{}^\wedge b{}^\wedge b = a$.
$a_k{}^\wedge a_{k+1}{}^\wedge \cdots {}^\wedge a_n = (a_1 {}^\wedge a_2 {}^\wedge \cdots {}^\wedge a_k{}^\wedge \cdots {}^\wedge a_n) {}^\wedge (a_1 {}^\wedge a_2 {}^\wedge \cdots {}^\wedge a_{k - 1})$，即$s[k, n] = s[n] - s[k - 1]$. 使用前缀和。
枚举区间的右端点$i\in [1, n]$，其则左端点$l\in [i - m + 1, i]$，$l - 1\in [i - m, i - 1]$，特殊地，当$i - m < 1$时，令$i - m = 0$，则$s[l, i] = s[i] - s[l - 1]$. 即滑动窗口。
在每次枚举右端点及窗口范围时，需要取得当前窗口内最大的区间异或和。如果再在窗口内枚举左端点，其时间复杂度为$O(mn)$，超时。所以使用Trie(字典树)维护窗口内元素值的方式。对于给定的右端点值，从其二进制的高位到低位，取Trie中的位相反值(如果有)，即贪心，最终将取出窗口内的最大区间异或和。其时间复杂度为$K\cdot O(n)$.
#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N1 = 100010;
const int N2 = 100000 * 31 + 10;
// trie，模板
int idx = 0;
int s[N1], trie[N2][2], cnt[N2];
void insert(int x, int v){
int p = 0;
for(int i = 30; i >= 0; i--){
int u = x >> i & 1;
if(!trie[p][u]) trie[p][u] = ++idx;
p = trie[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[trie[p][!u]]){
p = trie[p][!u];
res = res * 2 + 1;
}
else{
p = trie[p][u];
res = res * 2;
}
}
return res;
}
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i++){
cin >> s[i];
s[i] = s[i] ^ s[i - 1];
}
int res = 0;
insert(s[0], 1);
for(int i = 1; i <= n; i++){
if(i - m >= 1) insert(s[i - m - 1], -1);
res = max(query(s[i]), res);
insert(s[i], 1);
}
cout << res << endl;
return 0;
}