题解 SP11444 【MAXOR - MAXOR】

· · 题解

题目大意

给出一个序列和一些操作，每次查询一段区间内的最大异或子串。

分析

考虑全局最大异或子串怎么做。

记 g_i=a_1\oplus a_2\oplus a_3\oplus\cdots\oplus a_{i-1}\oplus a_i，考虑用 \operatorname{01Trie} 维护 \{g_i,g_{i+1},\cdots,g_{n-1},g_n\}，那么这个集合中的数异或 g_{i-1} 后就变成了以 i 为开头的所有子串的异或值（这是 \operatorname{01Trie} 的基本操作），这样就可以做到 \mathcal{O}(n\log_2v)（其中 v 指值域）查询整个区间的最大异或子串。

继续考虑区间查询，很显然建可持久化 \operatorname{01Trie} 后可以做到 \mathcal{O}(n\log_2v) 的复杂度单次查询，但这显然是不行的，考虑继续优化。

发现这个东西很显然可以分块，那么记录一下 f_{i,j} 表示第 i 块的左端点到 j 这段区间内的最大异或子串，那么就只查询的时候就只需要查询左端点在 [left,r_{id_{left}}]（r_i 表示第 i 块的左端点位置, id_i 表示 i 所属块的编号），右端点在 [left,right] 范围内的最大值,直接在可持久化 \operatorname{01Trie} 上查询就好了。

最后的时间复杂度是 \mathcal{O}(n\sqrt{n}\log_2v)，可能有点卡常，不建议对于左右不完整的块都暴力查询，可能会 TLE。

代码

#include<bits/stdc++.h>
#define REP(i,first,last) for(register int i=first;i<=last;++i)
#define DOW(i,first,last) for(register int i=first;i>=last;--i)
using namespace std;
inline int read()
{
    int x(0);
    char c(getchar());
    while(c<'0'||c>'9')
    {
        c=getchar();
    }
    while(c>='0'&&c<='9')
    {
        x=(x<<1)+(x<<3)+c-'0';
        c=getchar();
    }
    return x;
}
const int MAXN=1e5+5;
const int MAX_SQRTN=505;
int n,m;
int len,len_,root;
int arr[MAXN];
int id[MAXN];
int l[MAX_SQRTN],r[MAX_SQRTN];
int l_root[MAXN];
int l_xor[MAXN];
int f[MAX_SQRTN][MAXN];
struct Trie//01trie不是重点,不会的可以自行学习
{
    int son[2];
    int sum;
}trie[MAXN*1024];
int trie_cnt=0;
#define SON(n) trie[now].son[n]
#define NEW_SON(n) trie[new_tree].son[n]
inline void PushUp(int now)//合并信息
{
    trie[now].sum=trie[SON(0)].sum+trie[SON(1)].sum;
}
void Insert(int num,int &now,int deep=30)//普通01trie的插入节点部分
{
    if(!now)
    {
        now=++trie_cnt;
    }
    if(deep==-1)
    {
        trie[now].sum++;
        return;
    }
    bool p=(bool)(num&(1<<deep));
    Insert(num,SON(p),deep-1);
    PushUp(now);
}
void Insert_2(int num,int &new_tree,int now,int deep=30)//可持久化01trie的插入节点部分
{
    new_tree=++trie_cnt;
    if(deep==-1)
    {
        trie[new_tree].sum=trie[now].sum+1;
        return;
    }
    bool p=(bool)(num&(1<<deep));
    Insert_2(num,NEW_SON(p),SON(p),deep-1);
    NEW_SON(p^1)=SON(p^1);
    PushUp(new_tree);
}
int Query(int num,int now,int deep=30,int result=0)//查询整个集合内num异或的最大值
{
    if(deep==-1)
    {
        return result;
    }
    int p=(bool)(num&(1<<deep));
    if(SON(p^1))
    {
        return Query(num,SON(p^1),deep-1,result+((p^1)<<deep));
    }
    else
    {
        return Query(num,SON(p),deep-1,result+(p<<deep));
    }
}
int Query_2(int num,int cut,int now,int deep=30,int result=0)//查询区间内num异或的最大值
{
    if(deep==-1)
    {
        return result;
    }
    int p=(bool)(num&(1<<deep));
    if(trie[SON(p^1)].sum-trie[trie[cut].son[p^1]].sum)
    {
        return Query_2(num,trie[cut].son[p^1],SON(p^1),deep-1,result+((p^1)<<deep));
    }
    else
    {
        return Query_2(num,trie[cut].son[p],SON(p),deep-1,result+(p<<deep));
    }
}
#undef SON
#undef NEW_SON
inline int MaXor(int left,int right)//区间查询
{
    if(right-left<len_)//小范围就暴力查询,方法和查询全局最大异或子串类似
    {
        root=0;
        Insert(0,root);
        int x=0,result=0;
        REP(i,left,right)
        {
            x^=arr[i];
            result=max(result,x^Query(x,root));
            Insert(x,root);
        }
        return result;
    }
    int result=max(Query_2(l_xor[left-1],l_root[left-1],l_root[right])^l_xor[left-1],//查询左端点在left处的最大值
                   f[id[left]+1][right]/*左端点不在查询范围左端点所在块的最大值*/);
    REP(i,left,r[id[left]])//考虑枚举左端点,直接在可持久化01trie上查询最大值
    {
        result=max(result,Query_2(l_xor[i],l_root[i],l_root[right])^l_xor[i]);
    }
    return result;
}
int main()
{
    scanf("%d%d",&n,&m);
    REP(i,1,n)
    {
        arr[i]=read();
    }
    len=sqrt(n);
    len_=len*1.2;
    id[1]=0;//预处理内个位置所在的块以及内个块的左右端点
    l[0]=1;
    REP(i,2,n)
    {
        id[i]=(i-1)/len;
        if(id[i]^id[i-1])
        {
            l[id[i]]=i;
            r[id[i-1]]=i-1;
        }
    }
    r[id[n]]=n;
    root=0;
    REP(i,0,id[n])//预处理f数组
    {
        int x=0,maxor=0;
        root=0;
        Insert(0,root);
        REP(j,i,id[n])
        {
            REP(k,l[j],r[j])
            {
                x^=arr[k];
                maxor=max(maxor,x^Query(x,root));
                f[i][k]=maxor;//类似全局计算的方式得到f数组
                Insert(x,root);
            }
        }
    }
    Insert(0,l_root[0]);
    REP(i,1,n)//预处理可持久化01trie
    {
        l_xor[i]=l_xor[i-1]^arr[i];
        Insert_2(l_xor[i],l_root[i],l_root[i-1]);
    }
    int last_answer=0,l,r;
    REP(i,1,m)
    {
        last_answer%=n;
        l=(read()+last_answer)%n+1;
        r=(read()+last_answer)%n+1;
        if(l>r)
        {
            swap(l,r);
        }
        printf("%d\n",last_answer=MaXor(l,r));
    }
    return 0;
}
\operatorname{Updata\ on\ 2023.10.5}

这个 \operatorname{ds} 写这个题太麻烦了，可以发现 n\leq 1.2\times 10^4，那么是否可以预处理所有的答案然后直接查询呢。伟大的 \color{black}\sf{S}\color{red}\sf{tarSilk} 给出了一个 \mathcal{O}(n^2+m) 的优秀做法，碾压 \mathcal{O}(n\sqrt{n}\log_2v) 的分块套 \operatorname{01Trie}，成为目前最优解。

可以将问题转化为区间中两值异或的最大值，那么考虑如何合并两段区间 [l,r-1] 和 [l+1,r]，显然 [l,r] 将这两段区间完全覆盖，但没有计算 [l,l] 和 [r,r] 之间的贡献，因为这两段长度为 1 ，所以其本身没有贡献，只有两者之间的异或可能有贡献，于是就得到了一个 \mathcal{O}(n^2) 的优秀转移，每次 \mathcal{O}(1) 查询。

#include<bits/stdc++.h>
#define REP(i,f,l) for(int i(f);i<=l;++i)
using namespace std;
const int MAXN=1.2e4+3;
int n,m;
int arr[MAXN];
int f[MAXN][MAXN];
int main()
{
    scanf("%d%d",&n,&m);
    REP(i,1,n)
    {
        scanf("%d",&arr[i]);
        arr[i]^=arr[i-1];
    }
    REP(i,1,n)
    {
        f[0][i]=arr[i]^arr[i-1];
    }
    REP(i,1,n-1)
    {
        REP(j,1,n-i)
        {
            f[i][i+j]=max(f[i-1][i+j-1],f[i-1][i+j]);//访问连续地址会更快，所以可以将第一维改成区间长度使得访问连续
            f[i][i+j]=max(f[i][i+j],arr[j-1]^arr[i+j]);
        }
    }
    int l,r;
    int last_answer=0;
    REP(i,1,m)
    {
        scanf("%d%d",&l,&r);
        l=(l+1ll*last_answer)%n+1;
        r=(r+1ll*last_answer)%n+1;
        if(r<l)
        {
            swap(l,r);
        }
        printf("%d\n",last_answer=f[r-l][r]);
    }
    return 0;
}

退役多年后发现题解审核居然变严了