https://www.acwing.com/problem/content/3488/
不同于一般的子数组异或和（异或前缀和+前缀树），本题对子数组长度作了限制。
依旧考虑维护一颗前缀树，记录前缀树的每个节点在当前状态是否可达。只是规定树内涉及的节点规模不大于m。
可以发现，我们在[x, x + m - 1]区间，和[x + 1, x + m]区间作检索，并不需要O(m)的处理。
只需要去除x节点，加上x+m节点，并对x+m节点查询即可（由于异或的可交换性）。
还有一个小细节，例如要求[l, r]的异或前缀和，我们用data[r] ^ data[l - 1]。
那么对于前m项，我们实际所需维护的应是m+1个数，包括0，这样才能保证前m个同时取到。
同理，对于[2, 2 + m - 1]，我们实际需要的前缀和应包括[1, 2 + m - 1]。因而在加上2+m-1这一项前，应确保第0项（含0）前的元素均被删去。
所以对于i > m的第i次维护，应add(i)，并del(i - m - 1)。
1 #include<iostream>
2 #include<algorithm>
3 #include<vector>
4 #include<string>
5 #include<queue>
6 #include<map>
7 #include<set>
8 #define ll long long
9 #define pii pair<int, int>
10 using namespace std;
11 const int N = 1E5 + 10;
12 const ll INF = INT64_MAX;
13 using namespace std;
14
15 int m, n, pre[N], a[N];
16 int t[N * 31][2];
17 int check[N * 31];
18 int cnt = 0;
19
20 void build(int x, int u)
21 {
22 for(int i = 30 ; i >= 0 ; i--) {
23 int tmp = (1 << i) & x;
24 if(tmp) {
25 if(!t[u][1]) {
26 t[u][1] = ++cnt;
27 }
28 u = t[u][1];
29 }else {
30 if(!t[u][0]) {
31 t[u][0] = ++cnt;
32 }
33 u = t[u][0];
34 }
35 check[u]++;
36 }
37 }
38
39 int find(int x, int u)
40 {
41 int res = 0;
42 for(int i = 30 ; i >= 0 ; i--) {
43 int tmp = (1 << i) & x;
44 if(tmp) { // x此位为1
45 if(check[t[u][0]]) {
46 u = t[u][0];
47 }else {
48 u = t[u][1];
49 res |= (1 << i);
50 }
51 }else {
52 if(check[t[u][1]]) {
53 u = t[u][1];
54 res |= (1 << i);
55 }else {
56 u = t[u][0];
57 }
58 }
59 }
60 return res;
61 }
62
63 void del(int x, int u)
64 {
65 for(int i = 30 ; i >= 0 ; i--) {
66 int tmp = (1 << i) & x;
67 if(tmp) {
68 u = t[u][1];
69 }else {
70 u = t[u][0];
71 }
72 check[u]--;
73 }
74 }
75
76 int main()
77 {
78 ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
79 cin >> n >> m;
80 for(int i = 1 ; i <= n ; i++) {
81 cin >> a[i];
82 pre[i] = pre[i - 1] ^ a[i];
83 }
84 int ans = 0;
85 for(int i = 0 ; i <= n ; i++) {
86 if(i > m) {
87 del(pre[i - m - 1], 0);
88 }
89 build(pre[i], 0);
90 ans = max(ans, find(pre[i], 0) ^ pre[i]);
91 }
92 cout << ans << endl;
93
94 return 0;
95 }
96 /*
97 acwing 3488
98 */