Codechef REBXOR 题解

题目链接：Nikitosh and xor

题意：

给定 \(n\) 个数 ，求 \[ \max_{1 \le l_1 \le r_1 < l_2 \le r_2 \le n}\left\{\left(\bigoplus_{i=l_1}^{r_1} a_i\right) + \left(\bigoplus_{i=l_2}^{r_2} a_i\right)\right\} \] \(2 \le n \le 4\times 10^5,~0\le a_i \le 10^9\)

先考虑只有 \(\bigoplus_{i=l_1}^{r_1} a_i\) 该怎么求

u1s1，我觉得目前能看到我博客的人应该都会求 \(\bigoplus_{i=l_1}^{r_1} a_i\) 的最大值吧

那就直接建一个 \(\mathtt{01trie}\) 把异或前缀和全插入

然后在树上贪心找较大异或值就好啦

那么两个的情况其实是一样的

其实难在选第二个可能会与第一个有交集，以及不好枚举之类的问题

考虑从左往右依次插入每个串，这样枚举第一个是不重不漏的

此时 \(i\) 右侧的都没有插，但是我们要知道 \(i+1\) 到 \(n\) 的最大答案，然后把它们合并

怎么办？预处理呗！设 \(\mathtt{res}_i\) 表示 \(i\) 到 \(n\) 的最大值

这个预处理只要一开始从右往左跑一遍就好啦！

时间复杂度 \(O(n\log \max\{a_i\})\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{
    #define gc() readchar()
    #define pc(a) putchar(a)
    #define SIZ (int)(1e6+15)
    char buf1[SIZ],*p1,*p2;
    char readchar()
    {
        if(p1==p2)p1=buf1,p2=buf1+fread(buf1,1,SIZ,stdin);
        return p1==p2?EOF:*p1++;
    }
    template<typename T>void read(T &k)
    {
        char ch=gc();T x=0,f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=gc();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
        k=x*f;
    }
    template<typename T>void write(T k)
    {
        if(k<0){k=-k;pc('-');}
        static T stk[66];T top=0;
        do{stk[top++]=k%10,k/=10;}while(k);
        while(top){pc(stk[--top]+'0');}
    }
}using namespace FastIO;
#define N ((int)(4e5+15))
#define L (N << 5)

void up(int &x,int y){ x = (x > y) ? x : y;}
int n,a[N],res[N];
struct Trie
{
    int tot,trie[L][2],ed[L];
    void clear()
    {
        tot=0;
        memset(trie,0,sizeof(trie));
        memset(ed,0,sizeof(ed));
    }
    void insert(int i)
    {
        int u=0, x=a[i];
        for(int j=30,c; j>=0; j--)
        {
            c = (x >> j) & 1;
            if(!trie[u][c]) trie[u][c]=++tot;
            u=trie[u][c];
        }
        ed[u]=i;
    }
    // find max{x xor a[j]} (j ≠ i)
    int query(int x)
    {
        int u=0;
        for(int j=30,c; j>=0; j--)
        {
            c = (x >> j) & 1;
            if(trie[u][c^1]) u=trie[u][c^1];
            else if(trie[u][c]) u=trie[u][c];            
        }
        return a[ed[u]];
    }
}tr;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    read(n);
    for(int i=1; i<=n; i++)
    {
        read(a[i]);
        a[i] ^= a[i-1];
    }
    for(int i=n-1; i; i--)
    {
        tr.insert(i+1);
        res[i] = a[i] ^ tr.query(a[i]);
        up(res[i], res[i+1]);
    }
    int ans=0; tr.clear();
    for(int i=1,cur; i<n; i++)
    {
        tr.insert(i-1);
        cur = a[i] ^ tr.query(a[i]);
        up(ans, cur + res[i]);
    }
    write(ans);
    return 0;
}