BZOJ 3261: 最大异或和

Description

一个序列,支持两个操作.

1.在序列尾加入一个数.

2.询问 [l,r] 中与 x 异或值最大的数.

\(n\leqslant 3*10^5\)

Sol

可持久化 Trie 树.

跟主席树一样建二进值 Trie 树.

异或就是尽量找不相同的就行.

Code

/**************************************************************
Problem: 3261
User: BeiYu
Language: C++
Result: Accepted
Time:4252 ms
Memory:172380 kb
****************************************************************/ #include<cstdio>
#include<iostream>
using namespace std;
#define N 600055
inline int in(int x=0,char ch=getchar()){ while(ch>'9'||ch<'0') ch=getchar();
while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();return x; }
inline char getop(char ch=getchar()){ while(ch>'Z'||ch<'A') ch=getchar();return ch; }
struct Trie{
int ch[N*24][2],s[N*24],cnt;
void insert(int pre,int &o,int val,int w){
if(!o) o=++cnt;s[o]=s[pre]+1;if(!w) return;
if(val&w) ch[o][0]=ch[pre][0],insert(ch[pre][1],ch[o][1],val,w>>1);
else ch[o][1]=ch[pre][1],insert(ch[pre][0],ch[o][0],val,w>>1);
}
int Query(int L,int R,int val,int res=0){
for(int k=1<<24,tmp;k;k>>=1){
if(tmp=!(val&k),s[ch[R][tmp]]-s[ch[L][tmp]]) res+=k,L=ch[L][tmp],R=ch[R][tmp];
else L=ch[L][!tmp],R=ch[R][!tmp];
}return res;
}
}t;
int rt[N];
int main(){
int n=in()+1,m=in(),x;t.insert(rt[0],rt[1],0,1<<24);
for(int i=2;i<=n;i++) x=x^in(),t.insert(rt[i-1],rt[i],x,1<<24);
for(;m--;){
char opt=getop();
if(opt=='A'){
x=x^in(),n++;t.insert(rt[n-1],rt[n],x,1<<24);
}else{
int l=in(),r=in(),v=x^in();printf("%d\n",t.Query(rt[l-1],rt[r],v));
}
}return 0;
}

  

上一篇:11 自定制shell提示符


下一篇:vim下如何删除某行之后的所有行