替罪羊树套Trie，Trie合并用线段树合并，注意常数优化。

 

顺便AC800题纪念~~~

 

#include
     
      #include
      
       #include
       
        using namespace std;const int N=200010,inf=19,M=32000010;struct info{  int v1,v2;  info(){v1=v2=0;}  info(int _v1,int _v2){v1=_v1,v2=_v2;}}maxv;inline info merge(info a,info b){  if(b.v1>a.v1){    a.v2=b.v2>a.v1?b.v2:a.v1;    a.v1=b.v1;  }else if(b.v1>a.v2)a.v2=b.v1;  return a;}struct node{int l,r,v;node(){}node(int _l,int _r,int _v){l=_l,r=_r,v=_v;}}T[M];int rub,getn[M];const double A=0.8;int size[N],real[N],ex[N],son[N][2],val[N],f[N],tot,root,id[N],cnt;info mv[N];int h[N],pool[N];int ans,cntpool,cntone,one[N];int n,q,x,y,i,Pow[20],Inv[20];char ch;//Trie begininline void Max(int&a,int b){if(a
        
         ans&&~a;a--)if(c&Pow[a]){    if(T[T[x].l].v)x=T[x].l;else t&=Inv[a],x=T[x].r;  }else{    if(T[T[x].r].v)x=T[x].r;else t&=Inv[a],x=T[x].l;  }  return t;}inline void Ask(int c){  int i;  for(i=1;i<=cntone;i++)Max(ans,one[i]^c);  for(i=1;i<=cntpool;i++)Max(ans,Ask(pool[i],c));}void deltree(int x){  if(!x)return;  deltree(T[x].l);deltree(T[x].r);  getn[++rub]=x;}//Trie end//Scapegoat begininline void up(int x){  mv[x]=info(ex[x]?val[x]:0,0);  if(son[x][0])mv[x]=merge(mv[x],mv[son[x][0]]);  if(son[x][1])mv[x]=merge(mv[x],mv[son[x][1]]);}inline int newnode(int p,int fa){  int x=++tot;  f[x]=fa;size[x]=real[x]=ex[x]=1;son[x][0]=son[x][1]=0;  val[x]=p;  mv[x]=info(p,0);  Ins(h[x]=0,inf,p,1);  return x;}inline int Newnode(int x,int fa){  f[x]=fa;size[x]=1;real[x]=ex[x];son[x][0]=son[x][1]=0;  mv[x]=info(ex[x]?val[x]:0,0);  h[x]=0;  return x;}int ins(int x,int p,int b){  size[x]++;real[x]++;mv[x]=merge(mv[x],info(p,0));  Ins(h[x],inf,p,1);  if(!son[x][b])return son[x][b]=newnode(p,x);else return ins(son[x][b],p,b);}void dfs(int x){  if(son[x][0])dfs(son[x][0]);  id[++cnt]=x;  if(son[x][1])dfs(son[x][1]);}int build(int fa,int l,int r){  int mid=(l+r)>>1,x=Newnode(id[mid],fa);  if(l
         
          mid)size[x]+=size[son[x][1]=build(x,mid+1,r)],real[x]+=real[son[x][1]];  h[x]=Merge(h[son[x][0]],h[son[x][1]]);  if(ex[x])Ins(h[x],inf,val[x],1);  up(x);  return x;}inline int rebuild(int x){  cnt=0;dfs(x);  for(int i=1;i<=cnt;i++)deltree(h[id[i]]);  return build(f[x],1,cnt);}inline int kth(int k,int p){  int x=root,rank;  while(1){    size[x]++;real[x]++;mv[x]=merge(mv[x],info(p,0));Ins(h[x],inf,p,1);    rank=real[son[x][0]]+1;    if(k==rank&&ex[x])return x;    if(k
          
           n)x=ins(root,p,1); else{ x=kth(k,p); if(son[x][0])x=ins(son[x][0],p,1);else{ son[x][0]=newnode(p,x); x=son[x][0]; } } int z=x,deep=0;while(f[z])z=f[z],deep++; if(deep
           
            =mid+ex[x])ask(son[x][1],mid+ex[x],b,c,d);}//Scapegoat endinline void read(int&a){ char ch;while(!(((ch=getchar())>='0')&&(ch<='9'))); a=ch-'0';while(((ch=getchar())>='0')&&(ch<='9'))(a*=10)+=ch-'0';}int main(){ for(Pow[0]=i=1;i<=inf;i++)Pow[i]=Pow[i-1]<<1; for(i=0;i<=inf;i++)Inv[i]=Pow[i]^1048575; for(i=1;i