Description
给定一个长度为 n 的序列 a_i，有 m 个询问，查询一段区间内的子区间的异或和最大值。
强制在线。
1leq nleq 10^5
Solution
首先肯定考虑使用 Trie 树。
然而普通 Trie 树并不能处理这个问题，所以我们考虑先使其可持久化，处理区间异或值。
然后再分块，记 F[i][j] 表示从第 i 个块开始到位置 j 的答案，显然可以 mathcal O(Nsqrt N) 枚举每一个块以及每一个位置，再加一只 log 在可持久化 Trie 树上求得答案。
对于询问，只需要把最左端块的散块部分暴力枚举即可，剩下的直接 mathcal O(1) 查询。
总时间复杂度：O((N Q)sqrt N log V)
Code
代码语言：javascript复制#include<bits/stdc .h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define W while
#define I inline
#define RI register int
#define int long long
#define Cn const
#define CI Cn int&
#define gc getchar
#define D isdigit(c=gc())
#define pc(c) putchar((c))
using namespace std;
namespace Debug{
Tp I void _debug(Cn char* f,Ty t){cerr<<f<<'='<<t<<endl;}
Ts I void _debug(Cn char* f,Ty x,Ar... y){W(*f!=',') cerr<<*f ;cerr<<'='<<x<<",";_debug(f 1,y...);}
Tp ostream& operator<<(ostream& os,Cn vector<Ty>& V){os<<"[";for(Cn auto& vv:V) os<<vv<<",";os<<"]";return os;}
#define gdb(...) _debug(#__VA_ARGS__,__VA_ARGS__)
}using namespace Debug;
namespace FastIO{
Tp I void read(Ty& x){char c;int f=1;x=0;W(!D) f=c^'-'?1:-1;W(x=(x<<3) (x<<1) (c&15),D);x*=f;}
Ts I void read(Ty& x,Ar&... y){read(x),read(y...);}
Tp I void write(Ty x){x<0&&(pc('-'),x=-x,0),x<10?(pc(x '0'),0):(write(x/10),pc(x '0'),0);}
Tp I void writeln(Cn Ty& x){write(x),pc('n');}
}using namespace FastIO;
Cn int N=1e5 10,M=sqrt(N) 10;
int n,m,S,a[N],bl[N],Ans[M][N],L[M],R[M],F[M][N],tot;
class Trie{
private:
int id,rt[N];
struct node{int nxt[2],v;}T[N*31];
I void U(int& x,CI y,CI v,CI d){ (T[x= id]=T[y]).v,~d&&(U(T[x].nxt[v>>d&1],T[y].nxt[v>>d&1],v,d-1),0);}
I int Q(CI x,CI y,CI v,CI d){
if(!~d) return 0;
#define o (v>>d&1^1)
return T[T[x].nxt[o]].v^T[T[y].nxt[o]].v?Q(T[x].nxt[o],T[y].nxt[o],v,d-1)(1<<d):Q(T[x].nxt[o^1],T[y].nxt[o^1],v,d-1);
}
public:
I void U(CI x,CI v){U(rt[x],x?rt[x-1]:0,v,30);}
I int Q(CI l,CI r,CI v){return Q(rt[l-1],rt[r],v,30);}
}T;
I void B(){
RI i,j;for(T.U(0,0),S=sqrt(n),i=1;i<=n;i ) !((i-1)%S)&&(R[tot]=i-1,L[ tot]=i),bl[i]=tot,T.U(i,a[i]);R[tot]=n;
for(i=1;i<=tot;i ) for(j=L[i] 1;j<=n;j ) F[i][j]=max(F[i][j-1],T.Q(L[i],j-1,a[j]));
}
I int Q(CI l,CI r){
RI i,X=0;if(bl[l]==bl[r]){for(i=l;i<r;i ) X=max(X,T.Q(i 1,r,a[i]));return X;}
for(i=l;i<=R[bl[l]];i ) X=max(X,T.Q(i 1,r,a[i]));return max(X,F[bl[l] 1][r]);
}
signed main(){
RI i,x,y,l,r,p=0;for(read(n,m),i=1;i<=n;i ) read(a[i]),a[i]^=a[i-1];B();
W(m--) read(x,y),writeln(p=Q(min((x p)%n 1,(y p)%n 1)-1,max((x p)%n 1,(y p)%n 1)));return 0;
}
