Description

多个询问l，r，求所有子区间异或和中最大是多少

强制在线

Solution

分块+可持久化trie

1.对于每块的左端点L，预处理出L到任意一个i，[L,j] 间所有子区间异或和中最大为多少,\(\Theta(n\sqrt n)\)

2.对于询问x,y:

①x,y属于同一块,O(\(\sqrt n log n\))直接扫

②x,y不属于同一块, 找到x右边第一块的左端点，用预处理求出左端点到y，剩下的直接扫,O(\(\sqrt n log n\))

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;const int M=12930;const int B=30;const int L=111;inline int rd(){ int x=0;bool f=1;char c=getchar(); for(;!isdigit(c);c=getchar())if(c=='-')f=0; for(;isdigit(c);c=getchar())x=x*10+c-48; return x;}int n,m,sn;int a[M];int s[L][M];int tot;int ch[M*32][2];int sz[M*32];int root[M];int F(int x){//写法取决于存法 return x/sn;}int cpynode(int rt){ tot++; ch[tot][0]=ch[rt][0]; ch[tot][1]=ch[rt][1]; sz[tot]=sz[rt]+1; return tot;}int ins(int rt,int d){ int tmp,x,y,i,k; tmp=x=cpynode(rt); for(i=B;i>=0;i--){ k=(d>>i)&1; y=cpynode(ch[x][k]); ch[x][k]=y; x=y; } return tmp;}int get(int lt,int rt,int d){ int i,k,res=0; for(i=B;i>=0;i--){ k=((d>>i)&1)^1; if(sz[ch[rt][k]]-sz[ch[lt][k]]>0) lt=ch[lt][k],rt=ch[rt][k],res+=(1<
          
           =0?(i-1):(n+1)],root[j-1],a[j])); } } int ans=0; for(i=1;i<=m;i++){ ans%=n; ll=rd()%n,rr=rd()%n; x=min((ll+ans)%n+1,(rr+ans)%n+1); y=max((ll+ans)%n+1,(rr+ans)%n+1); x--; ans=0; if(F(x)==F(y)){ //ans=a[y];这样写是错的 for(j=x;j