题目链接:https://www.acwing.com/problem/content/description/1416/
思路:任意一段可以通过前缀和转换成两个点的最大值
那么就变成了最简单的trie求一对 数 的最大异或了,然后要求左边界最大,有边界最小
只需要 保留第一个答案 并且更新的时候直接覆盖掉即可
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1e5+10; 4 const int mod=998244353; 5 #define ll long long 6 #define ull unsigned long long 7 #define pi pair<int,int> 8 #define fi first 9 #define sc second 10 #define pb push_back 11 int a[maxn]; 12 int trie[maxn*22][2]; 13 int id[maxn*22]; 14 int tot; 15 16 void add(int x,int k) 17 { 18 int p=0; 19 for(int i=21;i>=0;i--) 20 { 21 int u=(x>>i)&1; 22 if(!trie[p][u]) trie[p][u]=++tot; 23 p=trie[p][u]; 24 } 25 id[p]=k; 26 } 27 28 int query(int x) 29 { 30 int p=0; 31 for(int i=21;i>=0;i--) 32 { 33 int u=(x>>i)&1; 34 if(trie[p][!u]) p=trie[p][!u]; 35 else p=trie[p][u]; 36 } 37 return id[p]; 38 } 39 40 41 42 43 44 int main() 45 { 46 ios::sync_with_stdio(0); 47 cin.tie(0); 48 int n; 49 cin>>n; 50 for(int i=1;i<=n;i++) 51 { 52 cin>>a[i]; 53 a[i]^=a[i-1]; 54 } 55 int ans=-1,l=-1,r=-1; 56 add(0,0); 57 for(int i=1;i<=n;i++) 58 { 59 int p=query(a[i]); 60 int tmp=a[i]^a[p]; 61 if(tmp>ans) ans=tmp,l=p+1,r=i; 62 add(a[i],i); 63 } 64 cout<<ans<<" "<<l<<" "<<r<<'\n'; 65 66 67 68 }View Code