RT,代码不长,不知道哪里挂了,求大佬帮忙看看,谢谢。
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
const int N = 2e5;
int ans;
int a[N + 1], sum[N + 1];
struct Trie{
vector < int > ch[2];
int Create_Node()
{
ch[0].push_back(0), ch[1].push_back(0);
return ch[0].size() - 1;
}
Trie()
{
Create_Node();
}
void Insert(int x)
{
for(int i = 20, u = 0; i >= 0; i --){
if(ch[!! (x & (1 << i))][u] == 0) ch[!! (x & (1 << i))][u] = Create_Node();
u = ch[!! (x & (1 << i))][u];
}
}
int Query(int x)
{
int res = 0;
for(int i = 20, u = 0; i >= 0; i --){
if(ch[! (x & (1 << i))][u]) res += (1 << i), u = ch[! (x & (1 << i))][u];
else u = ch[!! (x & (1 << i))][u];
}
return res;
}
};
Trie tr[2][N + 1];
int DFS(int l, int r)
{
if(l > r) return 0;
if(l == r) return l;
int maxn = - 1e9, p = 0;
for(int i = l; i <= r; i ++) if(a[i] > maxn) maxn = a[i], p = i;
int pl = DFS(l, p - 1), pr = DFS(p + 1, r);
if(p - l < r - p){
tr[0][pr].Insert(sum[p - 1]), tr[1][pr].Insert(sum[p]);
for(int i = l; i <= p; i ++) ans = max(ans, tr[1][pr].Query(sum[i - 1] ^ a[p]));
for(int i = l; i <= p - 1; i ++) tr[0][pr].Insert(sum[i - 1]), tr[1][pr].Insert(sum[i]);
return pr;
}else{
tr[0][pl].Insert(sum[p - 1]), tr[1][pl].Insert(sum[p]);
for(int i = p; i <= r; i ++) ans = max(ans, tr[0][pl].Query(sum[i] ^ a[p]));
for(int i = p + 1; i <= r; i ++) tr[0][pl].Insert(sum[i - 1]), tr[1][pl].Insert(sum[i]);
return pl;
}
}
void solve()
{
ans = 0;
int n; scanf("%d", & n);
for(int i = 1; i <= n; i ++) scanf("%d", & a[i]);
for(int i = 1; i <= n; i ++) sum[i] = sum[i - 1] ^ a[i];
for(int i = 1; i <= n; i ++) tr[0][i].Insert(sum[i - 1]), tr[1][i].Insert(sum[i]);
DFS(1, n);
printf("%d\n", ans);
}
int main()
{
int t; scanf("%d", & t);
while(t --) solve();
return 0;
}