首页 > 代码库 > BZOJ 2741: 【FOTILE模拟赛】L [分块 可持久化Trie]
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=12005,M=120,L=30;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; 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-1)/block+1; for(int i=1;i<=n;i++) pos[i]=(i-1)/block+1; for(int i=1;i<=m;i++) b[i].l=(i-1)*block+1, b[i].r=i*block; b[m].r=n;} struct _Trie{ int ch[2],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>>1, v);} int tXor(int x,int y,int now,int v){ int ans=0; while(now){ int p= (now&v)==0; 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>>=1; } 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-1], tXor(root[p-1], root[i-1], 1<<L, a[i]) ); } int Que(int l,int r){ l--; int pl=pos[l], pr=pos[r]; int ans=0; if(pl==pr){ for(int i=l+1;i<=r;i++) ans=max(ans, tXor(root[l-1], root[i-1], 1<<L, a[i]) ); }else{ int p; for(p=l; pos[p]==pos[p-1]; p++); ans=max(ans, f[pos[p]][r]); for(int i=l;i<p;i++) ans=max(ans, tXor(root[l], root[r], 1<<L, a[i]) ); } return ans; }}B;int main(){ freopen("in","r",stdin); n=read();Q=read(); ini(); for(int i=1;i<=n;i++) a[i]=read()^a[i-1], root[i]=root[i-1], ins(root[i],1<<L,a[i]); for(int i=1;i<=m;i++) B.Set(i); int last=0; while(Q--){ l=(read()+last%n)%n+1, r=(read()+last%n)%n+1; if(l>r) swap(l,r); last=B.Que(l,r); printf("%d\n",last); }}
BZOJ 2741: 【FOTILE模拟赛】L [分块 可持久化Trie]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。