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)
\]

然后丢到01Trie上就可以了。

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];

     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])); }

     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 和异或

最新文章

热门文章