【bzoj4260】 Codechef REBXOR trie树

Input

输入数据的第一行包含一个整数N，表示数组中的元素个数。

第二行包含N个整数A1,A2,…,AN。

Output

输出一行包含给定表达式可能的最大值。

Sample Input

5

1 2 3 1 2

Sample Output

Hint

满足条件的(l1,r1,l2,r2)有：(1,2,3,3)，(1,2,4,5)，(3,3,4,5)。

对于100%的数据，2 ≤ N ≤ 4*105，0 ≤ Ai ≤ 109。

题解：

其实很好想的，维护一个lmx[i]表示到1-i中最大的连续的xor和。

rmx[i]表示i-n重最大的连续的xor和，然后就是前缀和的形式

插入字典树，然后在字典树中找两个值的xor最大值。

就是找1的时候向0的方向找，0的时候向1的方向找。

很好理解吧。

 #include<cstring>

 #include<cmath>

 #include<algorithm>

 #include<iostream>

 #include<cstdio>

 #define N 400007

 using namespace std;

 int n,cnt=;

 int a[N],lmx[N],rmx[N];

 struct Node

 {

     int point[];

     void init()

     {

         point[]=point[]=;

     }

 }trie[*];

 void insert(int x)

 {

     int now=;

     for (int i=,t;i>=;i--)

     {

         if (x&(<<i)) t=;

         else t=;

         if (!trie[now].point[t]) trie[now].point[t]=++cnt;

         now=trie[now].point[t];

     }

 }

 int calc(int x)

 {

     int now=,ans=;

     for (int i=,t;i>=;i--)

     {

         if (x&(<<i)) t=;

         else t=;

         if (trie[now].point[t^])

         {

             ans=ans+(<<i);

             now=trie[now].point[t^];

         }

         else now=trie[now].point[t];

     }

     return ans;

 }

 int main()

 {

     scanf("%d",&n);

     for (int i=;i<=n;i++)

         scanf("%d",&a[i]);

     int x=;insert(x);

     for (int i=;i<=n;i++)

     {

         x=x^a[i];

         insert(x);

         lmx[i]=max(lmx[i-],calc(x));

     }

     cnt=;

     for (int i=;i<*;i++) trie[i].init();

     x=;insert(x);

     for (int i=n;i>=;i--)

     {

         x=x^a[i];

         insert(x);

         rmx[i]=max(rmx[i+],calc(x));

     }

     int ans=-;

     for (int i=;i<=n;i++)

         ans=max(ans,lmx[i-]+rmx[i]);

     printf("%d\n",ans);

 }

巴特西

【bzoj4260】 Codechef REBXOR trie树

最新文章

热门文章