每日一题 01trie专题 总结

The XOR Largest
Pair 奶牛异或
这前两道题比较简单，而且 我们直接运用01trie上查找最优值就可以，代码就不给了。

主要讲一下底下的几道题吧
Vitya and Strange Lesson
这道题我们首先要发现一个性质，就是其实我们每次xor上一个数的时候都是整体xor上，因此所有数之间相对的关系是不变的，所以我们只要记录这个xor上的值，剩下我们要查询的这个东西在trie上是可以二分的，于是我们在trie上二分这个mex就可以了，具体的我们如果这以为是t，那么因为我们首先是要求的是mex，那么要从0~1这样的一个过程，我们就让当前节点的t的这个儿子看看可以走满吗？如果可以那么就走否则我们t^1，并且加上当前的答案，大概就是一个这样的过程，这个做法还是比较清奇的，感觉这个思路也不错，这题的收获还是挺大的。
然后我们剩下就需要一个unique的过程，建立trie树的过程还是同上！
代码：

#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 300020
int n,m,a[M],xr,son[M<<5][2],siz[M<<5],tot;
inline void ins(int x){
    int nw=0;
    for(int i=20;~i;i--){
        int t=(x&(1<<i))>0;
        if(!son[nw][t]) son[nw][t]=++tot;
        nw=son[nw][t],siz[nw]++;
    }
}
inline int qry(int x){
    int nw=0,ret=0;
    for(int i=20;~i;i--){
        int t=(x&(1<<i))>0;
        if(siz[son[nw][t]]==(1<<i)) ret+=(1<<i),nw=son[nw][t^1];
        else nw=son[nw][t];
        if(!nw) return ret;
    } return ret;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1),n=unique(a+1,a+n+1)-a-1;
    for(int i=1;i<=n;i++) ins(a[i]);
    while(m--){
        int x=read(); xr^=x;
        printf("%d\n",qry(xr));
    }
    return 0;
}

Perfect Security
这道题相比上一道题就简单好多了，我们只需要考虑这个字典序的过程贪心，在trie树上查询带修就可以了
代码：

#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 300020
int n,a[M],b[M],son[M<<5][2],tot,sz[M<<5],ed[M<<5];
inline void ins(int x){
    int nw=0;
    for(int i=30;~i;i--){
        int t=(x&(1<<i))>0;
        if(!son[nw][t]) son[nw][t]=++tot;
        nw=son[nw][t],sz[nw]++;
    } ed[nw]=x;
}
inline int qry(int x){
    int nw=0,ret=0;
    for(int i=30;~i;i--){
        int t=(x&(1<<i))>0;
        if(sz[son[nw][t]]) nw=son[nw][t],sz[nw]--; else nw=son[nw][t^1];
    } return ed[nw];
} 
int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    for(int i=1;i<=n;i++) b[i]=read(),ins(b[i]);
    for(int i=1;i<=n;i++) printf("%d ",a[i]^qry(a[i]));
    puts(""); return 0;
}

Xor-MST
题意非常简单，但是乍一看没有任何想法
于是我们转换一下思路，我们考虑最小生成树的过程，我们按照边权排序然后能练就连
于是我们发现这题是要求异或的结果，那么我们也建一个trie树，于是我们考虑在一个trie上怎么考虑有关边权的相关。
首先有一个贪心的策略，我们考虑两个点u和v他们合并一定会在u和v的lca处合并，不可能在更上方，这样的边权一定是最优的，因此我们就可以分治在trie树上的每一个有两个儿子的几点上加速这个过程就可以了，
考虑到我们的深度是一个log的加上我们trie树的一个log，总复杂度是两个log的
代码：

#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 200020
#define INF 2000000000 
int n,a[M],son[M<<5][2],tot=1,pl[M<<5],pr[M<<5];
inline void ins(int x,int p){
    int nw=1;
    for(int i=30;~i;i--){
        int t=(x&(1<<i))>0;
        if(!son[nw][t]) son[nw][t]=++tot;
        nw=son[nw][t];
        if(!pl[nw]) pl[nw]=p; pr[nw]=p;
    }
}
inline int qry(int nw,int dep,int x){
    int ret=0;
    for(int i=dep;~i;i--){
        int t=(x&(1<<i))>0;
        if(son[nw][t]) nw=son[nw][t];
        else nw=son[nw][t^1],ret+=(1<<i);
    } return ret;
}
#define LS son[nw][0]
#define RS son[nw][1]
inline LL solve(int nw,int dep){
    if(dep<0) return 0;
    if(pl[LS]&&pl[RS]){
        int ret=INF;
        for(int i=pl[LS];i<=pr[LS];i++) ret=min(ret,qry(RS,dep-1,a[i]));
        return solve(LS,dep-1)+solve(RS,dep-1)+(LL)ret+(1LL<<dep);
    }
    if(pl[LS]) return solve(LS,dep-1);
    if(pl[RS]) return solve(RS,dep-1);
    return 0;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    sort(a+1,a+n+1);
    for(int i=1;i<=n;i++) ins(a[i],i);
    printf("%lld\n",solve(1,30));
    return 0;
}

最大异或和
这道挺水的，就是忘了copy节点了，调了好长时间，要注意一下！！！
具体就是直接套路可持久化就可以了，可以强制在线，但是作者认为离线更好写就离线了。
代码：

#include<bits/stdc++.h>
#define fgx cerr<<"-----------------------"<<endl
#define LL long long
#define DB double
#define pb push_back
using namespace std;
inline int read(){
    int nm=0,fh=1; char c=getchar();
    for(;!isdigit(c);c=getchar()) if(c=='-') fh=-1;
    for(;isdigit(c);c=getchar()) nm=nm*10+c-'0';
    return nm*fh;
}
#define M 600020
#define INF 2000000000
int n,m,a[M],p[M],rt[M],son[M<<5][2],sz[M<<5],tot=1;
int typ[M],pl[M],pr[M],pn[M],X[M];
inline void ins(int nw,int pnw,int x){
    for(int i=25;~i;i--){
        int t=((x&(1<<i))>0); son[nw][t^1]=son[pnw][t^1];
        son[nw][t]=++tot,nw=son[nw][t],pnw=son[pnw][t],sz[nw]=sz[pnw]+1;
    }
}
inline int qry(int nw,int pnw,int x){
    int ret=0;
    for(int i=25;~i;i--){
        int t=((x&(1<<i))>0);
        if(sz[son[nw][t^1]]-sz[son[pnw][t^1]]>0) nw=son[nw][t^1],pnw=son[pnw][t^1],ret+=(1<<i);
        else nw=son[nw][t],pnw=son[pnw][t];
    } return ret;
}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++) a[i]=read(),p[i]=p[i-1]^a[i];
    for(int i=1;i<=m;i++){
        char ch[15]; scanf("%s",ch);
        if(ch[0]=='A'){int x=read(); typ[i]=1,n++,p[n]=p[n-1]^x;}
        else typ[i]=2,pn[i]=n,pl[i]=read(),pr[i]=read(),X[i]=read();
    }
    rt[0]=1; for(int i=1;i<n;i++) ins(rt[i]=++tot,rt[i-1],p[i]);
    for(int i=1;i<=m;i++) if(typ[i]==2){
        int x=X[i]^p[pn[i]],ret;
        if(pl[i]==1) ret=x; else ret=x^p[pl[i]-1];
        if(pl[i]<pr[i]) ret=max(ret,qry(rt[pr[i]-1],rt[pl[i]-1],x));
        printf("%d\n",ret);
    } return 0;
}