题目大意
给出一个序列和一些操作,每次查询一段区间内的最大异或子串.
分析
考虑全局最大异或子串怎么做.
记 (g_i=a_1oplus a_2oplus a_3opluscdotsoplus a_{i-1}oplus a_i),考虑用 01trie 维护 ({g_i,g_{i+1},cdots,g_{n-1},g_n}),那么这个集合中的数 (xor g_{i-1}) 后就变成了以 (i) 为开头的所有子串的异或值(这是 01trie 的基本操作),这样就可以做到 (mathcal{O}(nlog_2v))(其中 (v) 指值域)查询整个区间的最大异或子串.
继续考虑区间查询,很显然建可持久化 01trie 后可以做到 (mathcal{O}(nlog_2v)) 的复杂度单次查询,但这显然是不行的,考虑继续优化.
发现这个东西很显然可以分块,那么记录一下 (f_{i,j}) 表示第 (i) 块的左端点到 (j) 这段区间内的最大异或子串,那么就只查询的时候就只需要查询左端点在 (leftsim r_{id_{left}})((r_i) 表示第 (i) 块的左端点位置, (id_i) 表示 (i) 所属块的编号),右端点在 (leftsim right) 范围内的最大值,直接在可持久化 01trie 上查询就好了.
最后的时间复杂度是 (mathcal{O}(nsqrt{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
",last_answer=MaXor(l,r));
}
return 0;
}