SP11444 MAXOR - MAXOR & bzoj 2741 【FOTILE模拟赛】L

(Updated: )
oi
, ,

Description

给定一个长度为 $n$ 的序列 $a_i$，有 $m$ 个询问，查询一段区间内的子区间的异或和最大值。

强制在线。

$1\leq n\leq 10^5$

Solution

首先肯定考虑使用 Trie 树。

然而普通 Trie 树并不能处理这个问题，所以我们考虑先使其可持久化，处理区间异或值。

然后再分块，记 $F[i][j]$ 表示从第 $i$ 个块开始到位置 $j$ 的答案，显然可以 $\mathcal O(N\sqrt N)$ 枚举每一个块以及每一个位置，再加一只 $log$ 在可持久化 Trie 树上求得答案。

对于询问，只需要把最左端块的散块部分暴力枚举即可，剩下的直接 $\mathcal O(1)$ 查询。

总时间复杂度：$O((N+Q)\sqrt N \log V)$

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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%10+'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;
}