BZOJ 2741: 【FOTILE模拟赛】L [分块 可持久化Trie]

题意：

区间内最大连续异或和

---

5点调试到现在....人生无望

但总算A掉了

一开始想错可持久化trie的作用了...可持久化trie可以求一个数与一个数集(区间中的一个数)的最大异或和

做法比较明显，前缀和后变成选区间内两个元素异或最大

考虑分块，预处理$f[i][j]$第i块到第j块选两个元素异或最大

询问时两边用可持久化trie暴力，中间整块已经预处理了

可以发现预处理复杂度$O(N\sqrt{N}*30)$，必须要枚举块中元素来算，不如直接保存下来$f[i][j]$为第i块到第j个元素的答案

如果说有什么教训的话，就是写之前想清楚每一个变量的意义

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

#define ch(x,y) t[x].ch[y]

typedef long long ll;

const int N=,M=,L=;

inline int read(){

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-; c=getchar();}

    while(c>=''&&c<=''){x=x*+c-''; c=getchar();}

    return x*f;

}

int n,Q,a[N],l,r;

int block,m,pos[N];

struct _Blo{int l,r;}b[M];

void ini(){

    block=sqrt(n);

    m=(n-)/block+;

    for(int i=;i<=n;i++) pos[i]=(i-)/block+;

    for(int i=;i<=m;i++) b[i].l=(i-)*block+, b[i].r=i*block;

    b[m].r=n;

}

struct _Trie{

    int ch[],size;

}t[N*L];

int sz,root[N];

void ins(int &x,int now,int v){

    t[++sz]=t[x]; x=sz;

    t[x].size++;

    if(!now) return;

    ins( t[x].ch[ bool(now&v) ], now>>, v);

}

int tXor(int x,int y,int now,int v){

    int ans=;

    while(now){

        int p= (now&v)==;

        if(t[ ch(y,p) ].size - t[ ch(x,p) ].size )

            x=ch(x,p), y=ch(y,p), ans+=now;

        else p=!p, x=ch(x,p), y=ch(y,p);

        now>>=;

    }

    return ans;

}

int f[M][N];

struct Block{

    void Set(int x){

        int p=b[x].l;

        for(int i=p; i<=n; i++)

            f[x][i]=max(f[x][i-], tXor(root[p-], root[i-], <<L, a[i]) );

    }

    int Que(int l,int r){

        l--;

        int pl=pos[l], pr=pos[r];

        int ans=;

        if(pl==pr){

            for(int i=l+;i<=r;i++) ans=max(ans, tXor(root[l-], root[i-], <<L, a[i]) );

        }else{

            int p;

            for(p=l; pos[p]==pos[p-]; p++);

            ans=max(ans, f[pos[p]][r]);

            for(int i=l;i<p;i++) ans=max(ans, tXor(root[l], root[r], <<L, a[i]) );

        }

        return ans;

    }

}B;

int main(){

    freopen("in","r",stdin);

    n=read();Q=read(); ini();

    for(int i=;i<=n;i++)

        a[i]=read()^a[i-], root[i]=root[i-], ins(root[i],<<L,a[i]);

    for(int i=;i<=m;i++) B.Set(i);

    int last=;

    while(Q--){

        l=(read()+last%n)%n+, r=(read()+last%n)%n+;

        if(l>r) swap(l,r);

        last=B.Que(l,r);

        printf("%d\n",last);

    }

}