Codeforces 282E Sausage Maximization(字典树)

题目链接：282E Sausage Maximization

题目大意：给定一个序列A，要求从中选取一个前缀，一个后缀，可以为空，当时不能重叠，亦或和最大。

解题思路：预处理出前缀后缀亦或和，然后在字典树中维护，每次添加并查询，过程中维护ans。

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; typedef long long ll; const int maxn = 1e5 + 5; struct Tire { int sz, g[maxn * 100][2]; void init(); void insert(ll s); ll find(ll s); }T; int N; ll A[maxn], prefix[maxn], suffix[maxn]; int main () { scanf("%d", &N); for (int i = 1; i <= N; i++) scanf("%lld", &A[i]); for (int i = 1; i <= N; i++) prefix[i] = prefix[i-1] ^ A[i]; for (int i = N; i; i--) suffix[i] = suffix[i+1] ^ A[i]; ll ans = 0; T.init(); for (int i = N; i >= 0; i--) { T.insert(suffix[i+1]); ans = max(ans, T.find(prefix[i])); } printf("%lld\n", ans); return 0; } void Tire::init() { sz = 1; memset(g[0], 0, sizeof(g[0])); } void Tire::insert(ll s) { int u = 0; for (int i = 60; i >= 0; i--) { int v = (s>>i)&1; if (g[u][v] == 0) { memset(g[sz], 0, sizeof(g[sz])); g[u][v] = sz++; } u = g[u][v]; } } ll Tire::find (ll s) { int u = 0; ll ret = 0; for (int i = 60; i >= 0; i--) { int v = ((s>>i)&1) ^ 1; if (g[u][v]) ret |= (1LL<