思路：
O(n2)解法
考虑当数据范围为5 e 4的解法：
对于最大异或值一般的解法都是放到01字典树上去跑，这题也不例外。但是对于m个询问来说，每次都对于[ l , r ]重新建立字典树显然时间和空间都不允许，所以这时候就可以用可持久化字典树来查询[ l , r ]的字典树啦
这样的话时间也还不是很够，考虑再怎么进行优化。可以进行分块操作，因为整块区间的值都是固定的，设d p [ i ] [ j ]表示第i块到第j块之间的任取两个数的最大异或值，这个显然可以预处理出来。借鉴分块求区间众数的预处理思想,时间复杂度为O ( n n l o g n )
对于查询，考虑答案的构成：中间整块的最大异或值，左端点所在非完整块的最大异或值，右端点所在非完整块的最大异或值；第一种就是预处理的d p数组的值，后两种可以枚举每一个数，贪心的在[ l , r ]的字典树上查找最大异或值，时间复杂度为O ( 2 n l o g n )
强化版
代码：
//#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll, ll>PLL; typedef pair<int, int>PII; typedef pair<double, double>PDD; #define I_int ll inline ll read(){ll x = 0, f = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')f = -1;ch = getchar();}while(ch >= '0' && ch <= '9'){x = x * 10 + ch - '0';ch = getchar();}return x * f;} inline void write(ll x){if (x < 0) x = ~x + 1, putchar('-');if (x > 9) write(x / 10);putchar(x % 10 + '0');} #define read read() #define closeSync ios::sync_with_stdio(0);cin.tie(0);cout.tie(0) #define multiCase int T;cin>>T;for(int t=1;t<=T;t++) #define rep(i,a,b) for(int i=(a);i<=(b);i++) #define repp(i,a,b) for(int i=(a);i<(b);i++) #define per(i,a,b) for(int i=(a);i>=(b);i--) #define perr(i,a,b) for(int i=(a);i>(b);i--) ll ksm(ll a, ll b,ll mod){ll res = 1;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res;} const int maxn=1e4+7,maxm=maxn*25; int tr[maxm][2],max_id[maxm],idx,root[maxn];///字典树的数组 int n,m,a[maxn]; int block,num,L[maxn],R[maxn],belong[maxn];//分块数组 int dp[1100][1100]; void insert(int i,int k,int p,int q){ if(k<0){ max_id[q]=i;return ; } int v=a[i]>>k&1; tr[q][v^1]=tr[p][v^1]; tr[q][v]=++idx; insert(i,k-1,tr[p][v],tr[q][v]); max_id[q]=max(max_id[tr[q][0]],max_id[tr[q][1]]); } int query(int root,int val,int l){ int p=root; for(int i=23;i>=0;i--){ int v=val>>i&1; if(max_id[tr[p][v^1]]>=l) p=tr[p][v^1]; else p=tr[p][v]; } return val^a[max_id[p]]; } int qask(int l,int r){ int bl=belong[l],br=belong[r]; if(bl==br){ int ans=0; for(int i=l;i<=r;i++) ans=max(ans,query(root[r],a[i],l)); return ans; } else{ int ans=dp[bl+1][br-1]; for(int i=l;i<=R[bl];i++) ans=max(ans,query(root[r],a[i],l)); for(int i=L[br];i<=r;i++) ans=max(ans,query(root[r],a[i],l)); return ans; } } int main(){ n=read,m=read; block=sqrt(n); num=n/block+(n%block>0); //root[0]=++idx; //max_id[0]=-1; //insert(0,23,0,root[0]); rep(i,1,n){ a[i]=read,belong[i]=(i-1)/block+1; root[i]=++idx; insert(i,23,root[i-1],root[i]); } rep(i,1,num) L[i]=(i-1)*block+1,R[i]=i*block; for(int i=1;i<=num;i++){ for(int j=i;j<=num;j++){ int now=dp[i][j-1]; for(int k=L[j];k<=R[j];k++){ now=max(now,query(root[R[j]],a[k],L[i])); } dp[i][j]=now; } } while(m--){ int l=read,r=read; int ans=qask(l,r); write(ans);puts(""); } return 0; }
