Nikitosh 和异或

本文主要是介绍Nikitosh 和异或，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题面

设 \(l_{i}\) 为以 \(i\) 为结尾的区间中最大的一段异或值，\(r_{i}\) 为以 \(i\) 为开头的区间中最大的一段异或值。

则有

\[l_{i}=\max\left(l[i-1],sum_{l-1}\oplus sum_{r}\right) \]

\[r_{i}=\max\left(r[i+1],sum_{l-1}\oplus sum_{r}\right) \]

\(sum_{i}\) 为异或前缀和，跟前缀和是差不多的，就是运算的方式改成了异或。

最后的答案则为

\[ans=\max\left(ans,l_{i}+r_{i+1}\right) \]

Code：

#include<cstdio>
#define MAX 400001
#define re register
namespace OMA
{
   int n;
   int l[MAX],r[MAX];
   int sum[MAX],num[MAX];
   struct Trie
   {
     int tot;
     int ch[MAX*31][2];
     void begin()
     {
       tot = 0;
       for(re int i=0; i<=n*31; i++)
       {
         for(re int j=0; j<=1; j++)
         { ch[i][j] = 0; }
       }
     }
     inline void insert(int x)
     {
       int u = 0;
       for(re int i=30; i>=0; i--)
       {
         int pos = (x>>i)&1;
         if(!ch[u][pos])
         { ch[u][pos] = ++tot; }
         u = ch[u][pos];
       }
     }
     inline int query(int x)
     {
       int u = 0,ans = 0;
       for(re int i=30; i>=0; i--)
       {
         int pos = (x>>i)&1;
         if(ch[u][pos^1])
         { u = ch[u][pos^1],ans += 1<<i; }
         else
         { u = ch[u][pos]; }
       }
       return ans;
     }
   }tree;
   inline int max(int a,int b)
   { return a>b?a:b; }
   inline int read()
   {
     int s=0,w=1; char ch=getchar();
     while(ch<'0'||ch>'9'){ if(ch=='-')w=-1; ch=getchar(); }
     while(ch>='0'&&ch<='9'){ s=s*10+ch-'0'; ch=getchar(); }
     return s*w;
   }
   signed main()
   {
     n=read();
     int ans = 0;
     for(re int i=1; i<=n; i++)
     { num[i] = read(); }
     for(re int i=1; i<=n; i++)
     { tree.insert(sum[i] ^= sum[i-1]^num[i]); }
     for(re int i=1; i<=n; i++)
     { l[i] = max(l[i-1],tree.query(sum[i])); }
     tree.begin();
     for(re int i=1; i<=n; i++)
     { sum[i] = 0; }
     for(re int i=n; i>=1; i--)
     { tree.insert(sum[i] ^= sum[i+1]^num[i]); }
     for(re int i=n; i>=1; i--)
     { r[i] = max(r[i+1],tree.query(sum[i])); }
     for(re int i=1; i<n; i++)
     { ans = max(ans,l[i]+r[i+1]); }
     printf("%d\n",ans);
     return 0;
   }
}
signed main()
{ return OMA::main(); }

这篇关于Nikitosh 和异或的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！