【BZOJ4260】CodechefREBXOR|trie

用trie求异或最大

利用异或的性质!

#include
#include
#include
#include
using namespace std;
const int MAXN&＃61;4e5&＃43;10;
int n,tot,num[MAXN],to[MAXN*30][2],head[MAXN],tail[MAXN];
void add(int v)
{int now&＃61;0;for(int i&＃61;1<<29;i;i>>&＃61;1){int x&＃61;0;if(i&v) x&＃61;1;if(to[now][x]&＃61;&＃61;0) to[now][x]&＃61;&＃43;&＃43;tot;now&＃61;to[now][x];}
}
int q(int v)
{int ans&＃61;0;int now&＃61;0;for(int i&＃61;1<<29;i;i>>&＃61;1){int x&＃61;1;if(v&i) x&＃61;0;if(to[now][x]!&＃61;0) ans&＃43;&＃61;i,now&＃61;to[now][x];else now&＃61;to[now][x^1];}return ans;
}
int main()
{scanf("%d",&n);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;)scanf("%d",&num[i]);int x&＃61;0;add(0);for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){x^&＃61;num[i];add(x);head[i]&＃61;q(x);head[i]&＃61;max(head[i],head[i-1]);} memset(to,0,sizeof(to));x&＃61;0;tot&＃61;0;add(0);for(int i&＃61;n;i>&＃61;1;i--){x^&＃61;num[i];add(x);tail[i]&＃61;q(x);tail[i]&＃61;max(tail[i],tail[i&＃43;1]);}int ans&＃61;0;for(int i&＃61;2;i<&＃61;n;i&＃43;&＃43;) ans&＃61;max(ans,head[i-1]&＃43;tail[i]);printf("%d",ans);return 0;
}