【51nod 6级题目】XOR key 问题

这题挺有意思的，就是给你一个数和一段区间，求区间内的一个数与这个数Xor起来的最大值，输出之。
很自然的想到Trie树来做，然后用线段树套起来，发现效率O(Q∙lg(N)∙lg(10^9))很不错嘛，于是做之，写了Trie的合并，判漏了当主树存在副树不存在的合并情况，调之；写个宏定义导致max内多次调用solve导致超时，调之。终于在一个多小时之后成功AC.
二话不说上代码

---

#include<cstdio>
#define lc(x) ch[x][0]
#define rc(x) ch[x][1]
#define ls o<<1
#define rs (ls)+1
#define tls ls,l,mid
#define trs rs,mid+1,r
#define cm int mid=(l+r)>>1
#define root 1,1,n
using namespace std;
const int N = 50000+10;
const int LEN = 32;
const int SIZ = N*LEN*2;
int cnt=0;
int n,q,a[N],tmp[LEN+1];
int cn,ch[SIZ][2];
int max(int a,int b){
return a>b?a:b;
}
int create(){
    ++cn; lc(cn)=rc(cn)=0; return cn;
}
struct Trie{
int rt;
    void insert(int x){
int o=rt;
for(int i=LEN;i>=1;--i) tmp[i]=x&1,x>>=1;
for(int i=1;i<=LEN;++i){
if(ch[o][tmp[i]]) o=ch[o][tmp[i]];
else o=ch[o][tmp[i]]=create();
        }
    }
int solve(int x){
int o=rt,ret=0;
for(int i=LEN;i>=1;--i) tmp[i]=x&1,x>>=1;
for(int i=1;i<=LEN;++i){
if(ch[o][tmp[i]^1]) o=ch[o][tmp[i]^1],ret=ret<<1|1;
else o=ch[o][tmp[i]],ret=ret<<1;
        }
return ret;
    }
    void Merge(int o,int o1,int o2,int dep){
if(!lc(o1)) lc(o)=lc(o2);
else if(lc(o2)) lc(o)=create(),Merge(lc(o),lc(o1),lc(o2),dep+1);
else lc(o)=lc(o1);
if(!rc(o1)) rc(o)=rc(o2);
else if(rc(o2)) rc(o)=create(),Merge(rc(o),rc(o1),rc(o2),dep+1);
else rc(o)=rc(o1);
    }
};
struct Tree{
    Trie tr[N*4];
    void PushUp(int o){
tr[o].rt=create();
tr[o].Merge(tr[o].rt,tr[ls].rt,tr[rs].rt,0);
    }
    void Build(int o,int l,int r){
if(l==r){ 
tr[o].rt=create(); tr[o].insert(a[l]); return; 
        }
        cm; Build(tls); Build(trs);
        PushUp(o);
    }
int Query(int o,int l,int r,int L,int R,int v){
if(L<=l && r<=R){
return ++cnt,tr[o].solve(v);
        }
int ret=0; cm;
if(L<=mid) ret=max(ret,Query(tls,L,R,v));
if(mid+1<=R) ret=max(ret,Query(trs,L,R,v));
return ret;
    }
}T;
int main(){
    scanf("%d%d",&n,&q);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    T.Build(root);
for(int x,y,z,i=1;i<=q;++i){
        scanf("%d%d%d",&x,&y,&z); ++y,++z;
        cnt=0;
int Ans = T.Query(root,y,z,x);
printf("%d\n",Ans);
    }
return 0;
}