题解 | #小Q与彼岸花#

题意：

题解：因为这个题目是弱化以后的，正常的范围是5e4 .
看了官方题解去学习了一波可持久化01trie然后回来把这个题补完。

可持久数据结构其实就是我们的数据结构的内容会不断发生变化，而我们还要查询以前的历史版本，比如某个区间的情况。

听名字可以听出来，可持久化01trie跟可持久化线段树差不多的效果，对于01字典树来说，可以指定查询 范围内的数组成的字典树。

但是针对于这个题目我们直接使用可持久化01trie进行维护，时间还是不能被允许的，所以说， 我们还需要去继续优化。

如何优化呢？ 分块！
我们用数组预处理出来 块x到块y之间的区间任意两数的最大异或值。

时间复杂度呢？

我们把数组分成大小为的块，那么可以分成个块
所以预处理的复杂度为： （类似于区间求解众数--强制在线）
应该没错。。。

for(int i=1;i<=sumblocks;i++){
    for(int j=i;j<=sumblocks;j++){
        int nowmax=ans[i][j-1];
        for(int k=(j-1)*sz+1;k<=min(n,j*sz);k++){
            int res=query(rt[min(j*sz,n)],a[k],(i-1)*sz+1);
            nowmax=max(nowmax,res);
        }
        ans[i][j]=nowmax;
    }
}

然后对于每次查询，如果l和r属于同一个块之间，那么我们直接暴力即可
那么如果不在同一个块呢，那么就跟最简单的分块一样了，先让最大值等于中间完整的块，然后我们暴力处理一下两边不全的块并不断更新最大值，然后返回最大值即可。

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e6+10;


int ans[300][300];
int a[maxn],buck[maxn];
int rt[maxn];
int sz,idx;
int trie[maxn*20][2];
int max_id[maxn];


void ins(int x,int pre,int now){
    for(int i=12;i>=0;i--){
        max_id[now]=x;
        int val=(a[x]>>i)&1;
        trie[now][val^1]=trie[pre][val^1];
        trie[now][val]=++idx;
        now=idx;
        pre=trie[pre][val];
    }
    max_id[now]=x;
}

int query(int root,int C,int L){
    int p=root;
    for(int i=12;i>=0;i--){
        int val=(C>>i)&1;
        if(max_id[trie[p][val^1]]>=L) p=trie[p][val^1];
        else p=trie[p][val];
    }
    return C^a[max_id[p]];
}

int get_block(int x){
    return (x-1)/sz+1;
}

int sol(int l,int r){
    int st=get_block(l);
    int ed=get_block(r);
    if(st==ed){
        int imax=0;
        for(int i=l;i<=r;i++){
            imax=max(imax,query(rt[r],a[i],l));
        }
        return imax;
    }
    else{
        int imax=ans[st+1][ed-1];
        //cout<<"debug   "<<imax<<endl;
        for(int i=l;i<=st*sz;i++){
            imax=max(imax,query(rt[r],a[i],l));
        }
        for(int i=(ed-1)*sz+1;i<=r;i++){
            imax=max(imax,query(rt[r],a[i],l));
        }
        return imax;
    }
}


int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    sz=sqrt(n);
    for(int i=1;i<=n;i++){
        cin>>a[i];
        rt[i]=++idx;
        ins(i,rt[i-1],rt[i]);
    }
    int sumblocks=(n-1)/sz+1;

    for(int i=1;i<=sumblocks;i++){
        for(int j=i;j<=sumblocks;j++){
            int nowmax=ans[i][j-1];
            for(int k=(j-1)*sz+1;k<=min(n,j*sz);k++){
                int res=query(rt[min(j*sz,n)],a[k],(i-1)*sz+1);
                nowmax=max(nowmax,res);
            }
            ans[i][j]=nowmax;
        }
    }

    while(m--){
        int l,r;
        cin>>l>>r;
        int xxx=sol(l,r);
        cout<<xxx<<endl;
    }
    return 0;

}