题解：P10690 Fotile 模拟赛 L

· · 题解

啊因为 SB 错误调了一天。这题是 P4735 的可持久化 01trie 用分块优化。本题要求有一定 01trie 基础。如果已完成 P4735 可以直接跳至此题思路部分。

可持久化 01trie

看到异或，可以想到转换成 01trie 解决问题。在查询区间最大异或值的时候，不一定是从全局直接查询，故需要使用 可持久化 01trie 结合前缀异或和。

可持久化 01trie 就是可持久的 01trie，对于每一次的插入操作，只需要对于有影响的节点复制一遍，记录修改后的节点，每一次复制只会增加 \log n 个点。相比于暴力的将整棵树复制一遍，节省了大量时间与空间。具体过程与主席树类似。

查询操作从二进制下最高位开始，设需要查询一个 y，使得其与 x 异或和尽可能的大，则每一次在 01trie 中尽可能的选择当前位与二进制下 x 不同的节点。这是一个显然的贪心，例如：(1000)_2 >(0111)_2。

从 1 至 i 的前缀异或和为 xum_i，则最终的答案是：

\max \limits _{l\le i\le j\le r}xum_i \oplus xum_j

显然对于每一次询问可以暴力的枚举一个 i 并用 O(\log n) 的复杂度查找到对应的 xum_j。

运用上面两个操作，再搭配上前缀异或和可以实现 O(n\log n) 的插入所有元素，但查询区间最大异或和还是 O(nm\log n)，需要继续优化。

此题思路

注意到查询是算法的瓶颈，要考虑用某种算法或数据结构维护区间内的答案。因为我非常喜欢暴力数据结构，所以我用分块预处理出部分答案。

设 s_{i,j} 表示以第 i 块的左端点为左端点，以 j 为右端点的区间内的最大异或和。记 M 为在 s_{i,j} 区间内与 xum_j 异或的最大值。不难发现有：

s_{i,j}=\max(s_{i,j-1},M)

接下来在每一次的询问中，就只需要计算考虑散块中的答案即可。

此时的时间复杂度是 O(n\sqrt n\times \log n+m\log n)，当然常数有那么亿点点大，但既然是正确的复杂度就不必深究啦。

代码实现

在实现过程中，因为懒得特判各种 0 的情况，01trie 的 root 统一向右移动一格。

ans 一定要清 0！

int n,m;
int point;
int rt[1000086];
int tr[1000086][2];
int cnt[1000086];
int xum[120086];
int id[120086];
int ltp[586];
int rtp[586];
int ask(int l,int r,int v){
    int ans=0;
    for(int i=63;i>=0;i--){//事实上远到不了2^63
        int qwq=(v>>i)&1;
        if(cnt[tr[r][not qwq]]>cnt[tr[l][not qwq]]){//若可以走与当前为相反的
            ans+=(1<<i);//当前位可以是1
            qwq=not qwq;//当前位取反
        }
        l=tr[l][qwq];
        r=tr[r][qwq];//继续考虑后一位
    }
    return ans;
}
void insert(int l,int r,int v){
    for(int i=63;i>=0;i--){//同上
        int qwq=(v>>i)&1;
        tr[l][not qwq]=tr[r][not qwq];//复制
        tr[l][qwq]=++point;//新增节点
        cnt[tr[l][qwq]]=cnt[tr[r][qwq]]+1;//记为可以走相反的
        l=tr[l][qwq];
        r=tr[r][qwq];//考虑后一位
    }
    return;
}
int ans;
int s[586][100086];
signed main(){
    std::cin>>n>>m;
    rt[1]=++point;
    insert(rt[1],0,0);//01trie 一定要先插入一个0，以后的插入都是在此基础上做修改
    int c=sqrt(n);
    int len=(n+1)/c;
    if(c*c<n+1)//由于向右移了一格，故处理 01trie 时都是 n+1
        len++;
    id[1]=1;
    for(int i=1;i<=n;i++){
        id[i+1]=i/c+1;//预处理id
        int x;
        std::cin>>x;
        xum[i+1]=xum[i] xor x;//前缀异或和
        rt[i+1]=++point;
        insert(rt[i+1],rt[i],xum[i+1]);//插入当前的xum
    }
    for(int i=1;i<=len;i++){
        ltp[i]=rtp[i-1]+1;
        rtp[i]=std::min(n+1,ltp[i]+c-1);//预处理每个块的左右端点
     }
    for(int i=1;i<=len;i++)
        for(int j=ltp[i]+1;j<=n+1;j++)
            s[i][j]=std::max(s[i][j-1],ask(rt[ltp[i]-1],rt[j],xum[j]));//其中ask是查询sij范围内的最大异或和，也就是上面的M
    while(m--){
        int x,y;
        int l,r;
        std::cin>>x>>y;
        l=std::min((ans+x)%n+1,(ans+y)%n+1);
        r=std::max((ans+x)%n+1,(ans+y)%n+1);
        r++;
        ans=0;
        int st=id[l];
        int ed=id[r];
        if(st==ed)//同块内暴力
            for(int i=l;i<=r;i++)
                ans=std::max(ans,ask(rt[l-1],rt[r],xum[i]));
        else{
            ans=s[st+1][r];//前面处理好了答案
            for(int i=l;i<=rtp[st];i++)
                ans=std::max(ans,ask(rt[l-1],rt[r],xum[i]));
        }
        std::cout<<ans<<"\n";

  }
  return 0;//撒花！
}

如有不足，欢迎指正。