BZOJ - 2741 分块维护最大连续异或和-白红宇

BZOJ - 2741 分块维护最大连续异或和

阅读量：5041 次

发布时间：2019-06-12

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

题意:给定\(a[l...r]\),多次询问区间\([l,r]\)中的最大连续异或和\(a_i⊕a_{i+1}⊕...⊕a_{j},l≤i≤j≤r\)

一眼过去认为是不可做的,但题目给出\(n=1.2e4\),提供了分块暴力的余地

首先处理成前缀形式,对于询问\([l,r]\)既为\([l-1,r]\)中寻找两个数xor最大

维护\(f[i][j]\):第i个块到第j个数的任意异或最大值

这个只需\(O(30*n\sqrt{n})\)的代价即可预处理

对于每次询问,首个残缺的块暴力,其余块直接由\(f\)得到答案,复杂度\(O(30*m\sqrt{n})\)

Yet Another Similar Problem :

#include
    
     #define rep(i,j,k) for(register int i=j;i<=k;i++)#define rrep(i,j,k) for(register int i=j;i>=k;i--)#define erep(i,u) for(register int i=head[u];~i;i=nxt[i])#define iter(i,j) for(int i=0;i<(j).size();i++)#define print(a) printf("%lld",(ll)a)#define println(a) printf("%lld\n",(ll)a)#define printbk(a) printf("%lld ",(ll)a)#define IOS ios::sync_with_stdio(0)using namespace std;const int MAXN = 2e4+11;const int oo = 0x3f3f3f3f;typedef long long ll;ll read(){    ll x=0,f=1;register 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;}int T[MAXN],a[MAXN],b[MAXN];struct TRIE{    int tot;    int son[MAXN*40][2],size[MAXN*40];    void init(){        tot=0;        son[0][0]=son[0][1]=size[0]=0;        memset(T,0,sizeof T);    }    int insert(int old,int val){        int rt,o;rt=o=++tot;        rrep(i,30,0){            son[o][0]=son[old][0],            son[o][1]=son[old][1];            size[o]=size[old]+1;            int wh=val>>i&1;            son[o][wh]=++tot;            old=son[old][wh];            o=son[o][wh];        }        size[o]=size[old]+1;        return rt;    }    int query(int l,int r,int val){        int ans=0;        rrep(i,30,0){            int wh=val>>i&1;            if(size[son[r][wh^1]]-size[son[l][wh^1]]){                ans|=(1<

vec[233];int head[233],pos[MAXN];int f[233][MAXN];int main(){ int n,m; while(cin>>n>>m){ trie.init(); rep(i,1,n) a[i]=read(); rep(i,1,n) b[i]=b[i-1]^a[i]; rep(i,1,n) T[i]=trie.insert(T[i-1],b[i]); int sz=sqrt(n)+1; rep(i,1,sz+3) vec[i].clear(); int now=0; rep(i,1,n){ if(vec[now].size()==sz||now==0) head[++now]=i; vec[now].push_back(a[i]); pos[i]=now; } memset(f,0,sizeof f); rep(i,1,now){ rep(j,head[i],n){ f[i][j]=max(f[i][j-1],trie.query(T[head[i]-1],T[j],b[j])); } } int ans=0; while(m--){ int l=read(); int r=read(); int x=((ll)l+ans)%n+1; int y=((ll)r+ans)%n+1; l=min(x,y); r=max(x,y); ans=0; --l; if(pos[l]==pos[r]){ rep(i,l,r){ ans=max(ans,trie.query(T[l-1],T[r],b[i])); } }else{ ans=f[pos[l]+1][r];//best[pos[l+1]][r] rep(i,l,head[pos[l]+1]-1){ ans=max(ans,trie.query(T[l-1],T[r],b[i])); } } println(ans); } } return 0;}

转载于:https://www.cnblogs.com/caturra/p/9465866.html

你可能感兴趣的文章