本文共 2513 字，大约阅读时间需要 8 分钟。

题意：

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

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

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

如何优化呢？ 分块！

时间复杂度呢？

我们把数组分成大小为$\sqrt{n}$的块，那么可以分成$(n-1)/\sqrt{n}+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;    }}

然后对于每次查询，如果l和r属于同一个块之间，那么我们直接暴力即可

代码：

#include
   
    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   "<
    
     <
     
      >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<
      
       <
      
     
    
   

转载地址：https://blog.csdn.net/xxxxxiao123/article/details/116167178 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！