Nikitosh 和异或 LibreOJ - 10051 题意： 给定数量为 N N N数列A，要求最大值： ( A [ l 1 ] ⨁ A [ l 1 + 1 ] ⨁ … ⨁ A [ r 1 ] ) + ( A [ l 2 ] ⨁ A [ l 2 + 1 ] … ⨁ A [ r 2 ] ) (A[l1]⨁A[l1+1]⨁…⨁A[r1])+(A[l2]⨁A[l2+1]…⨁A[r2]) (A[l1]⨁A[l1+1]⨁…⨁A[r1])+(A[l2]⨁A[l2+1]…⨁A[r2])，其中 1 ≤ l 1 ≤ r 1 < l 2 ≤ r 2 ≤ N 1≤l1≤r1<l2≤r2≤N 1≤l1≤r1<l2≤r2≤N
思路： 异或有两个性质： x ⨁ x = 0 , x ⨁ 0 = x x⨁x=0,x⨁0=x x⨁x=0,x⨁0=x,所以对一段连续 [ l , r ] [l,r] [l,r]的异或，可以用前缀和算出 l [ l − 1 ] , l [ r ] l[l-1],l[r] l[l−1],l[r],那么 l [ l − 1 ] ⨁ l [ r ] l[l-1]⨁l[r] l[l−1]⨁l[r]就是 [ l , r ] [l,r] [l,r]的区间异或和。 由此问题转化为在 [ 1 , i ] [1,i] [1,i]区间中选择两个数，使得异或结果最大。字典树出现了 设 R [ i ] R[i] R[i]是以i为终点，右半部分的最大区间异或和； L [ i ] L[i] L[i]是以i为终点，左半部分的最大区间异或和。那么答案就是遍历： L [ i ] + R [ i + 1 ] L[i]+R[i+1] L[i]+R[i+1]的最大值。
int n; int trie[maxn*32+5][2],tot=1; int a[maxn],l[maxn],r[maxn],L[maxn],R[maxn]; void inser(int a){//trie插入 int p=1; int ch=1; for(int i=31;i>=0;i--){ ch=(a>>i)&1; if(trie[p][ch]==0)trie[p][ch]=++tot; p=trie[p][ch]; } } int sear(int a){ int p=1; int ch=1,ans=0; for(int i=31;i>=0;i--){ ch=a>>i&1; if(trie[p][ch^1]){ p=trie[p][ch^1]; ans|=1<<i; }else{ p=trie[p][ch]; } } return ans; } int main(){ int n; int res=0; sci(n); inser(0); for(int i=1;i<=n;i++){ sci(a[i]); l[i]=l[i-1]^a[i]; L[i]=max(L[i-1],sear(l[i])); inser(l[i]); } for(int i=n;i>=1;i--){ r[i]=r[i+1]^a[i]; R[i]=max(R[i+1],sear(r[i])); inser(r[i]); } for(int i=1;i<n;i++){ res=max(res,L[i]+R[i+1]); } cout<<res<<endl; return 0; }