01 Trie 解决异或小专题

说在前面的

我希望以后的每日一题也是以小专题出现的，我觉得这样的练习效果才好。而且题有点少，并且有很多重复。例如 $\text{01 Trie}$ 解决异或和，权值 $\text{01 Trie}$ ，合并 $\text{01 Trie}$ 没有出现，有点小伤心。牛客工作人员找了这么多的例题真的很辛苦。感谢牛客。

异或

异或是一种位运算。满足 $A\oplus B = \sum_{bit=0} [A(bit)\not=B(bit)] \times 2^{bit}$ 。这个比较好理解，大概就是两个数异或，那么在一位上相同的的数变为 $0$ ，反之变为 $1$ 。

性质

那么异或又满足什么性质呢，个人认为下面的式子非常简单，如果有问题可以私聊。

交换率 $a\oplus b = b\oplus a$
结合率 $(a\oplus b)\oplus c = a\oplus (b\oplus c)$
$a\oplus a = 0$

01 Trie

$\text{01 Trie}$ 算是 $\text{Trie}$ 的一种变形。关于 $\text{Trie}$ 的讲解，为了方便大家，我直接把以前的博客搬过来这里，自我感觉还是不错的。

例题

牛客的例题只有由高到低建树的 $\text{01 Trie}$ ，但是覆盖的非常全面。

The XOR Largest Pair
异或最大值的模板，算是一个引入。这里讨论最大值。一个数和一个序列中一个数的异或最大值是多少？要支持询问。
考虑把序列插入，构建一个 $\text{Trie}$ 树。那么在询问时，只需要讨论该数的位是 $0$ 还是 $1$ 就行了。这样就需要 $O(n\log w)$ 的预处理， $O(\log w)$ 的询问和修改，为什么是对的。因为异或中我们如果可以满足最高位，那么没有理由不改变最高位，因为 $2^{bit} >\sum_{i=0}^{i < bit}2^i$ 。那么由高位到地位贪心就可以了。
奶牛异或
这道题和上一道题没有本质区别，由于我们知道 $a\oplus a = 0$ ，所以我们可以考虑做一次前缀异或和。那么区间操作就变为单点操作了，和上一道就一样了。
Vitya and Strange Lesson
这题就有点不一样了，先说 $(a_1,a_2,a_3..a_n) \oplus A\oplus B$ 根据结合率，等价于 $(a_1,a_2,a_3..a_n) \oplus (A\oplus B)$ 。
因为我们要求的是 $mex$ ，那么我们就考虑 $0$ 到 $mex-1$ 的数是否全部出现过。那么就变为查询异或最小值了，我们在构建 $\text{01 Trie}$ 时要顺便记录 $\text{Trie}$ 中的元素个数，当一个节点的元素个数填满时，我们是不能考虑的。
Perfect Security
这道题引入了删除操作，如果没有删除操作，这道题就是单纯的求出异或最小值。但是现在要求删除。那么我们在 $\text{01 Trie}$ 上再维护一个 $si_u$ 标记，表示是否这个节点下还有没有可用元素。那么删除和插入都只会影响一条链。
Xor-MST
考察了一个最小生成树算法 $\text{Boruvka}$ 算法，关于这个算法在网上并没有比较好的讲解，这个算法也不是常用的解决 $MST$ 算法，但是在类生成树的题中，这个思想还是挺广泛的。大概意思用一张图来讲解就是加一句话
对每个连通块，找到一条与该连通块相连的，且另一端点不在此连通块中的边权最小的边。将所有的这些边都加入最小生成树。重复若干遍上述操作，直到图连通。
那么运用在 $xor$ 最小生成树中，我们可以按一位为 $1/0$ 划分出两个集合，那么显然两个集合中只有可能出现一条边，而且该边是最小的，那么我们可以枚举一个集合的所有元素，在另一个集合中查询异或最小值，那么我们按高位到低位考虑一次就做完了。
最大异或和
引入了可持久化 $\text{01 Trie}$ ，我们发现序列操作先转为为异或前缀和的单点操作。那么现在就是考虑 $L,R$ 这个区间的中的可用元素有哪些。如果我们知道主席树的操作。那么我们可以类比。给每个前缀构建一个 $\text{01 Trie}$ 。那么当两个节点的 $si_u$ 做差。如果差还大于 $0$ ，那么就可以证明这个还有可以元素。而我们其实没必要对每个前缀都建一个 $\text{01 Trie}$ 树，我们只需要修改上一棵树的一条链就可以了（这个可以参见主席树的建树）。那么剩下的就是查询异或最大值的模板了。

代码（按题目讲解顺序给出）

~~悄悄告诉你，这都是每道题比较短的代码。~~

#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 100;
int ch[N][2],n,rt,size;
int read() {int x;scanf("%d",&x);return x;}
void ins(int u,int t,int x) {
    if(t < 0) return;
    int i = ((x >> t) & 1);
    if(!ch[u][i]) ch[u][i] = ++size;
    ins(ch[u][i],t - 1,x);
}
int ask(int u,int t,int x) {
    if(t < 0) return 0;int i = ((x >> t) & 1);
    if(ch[u][!i]) return ask(ch[u][!i],t - 1,x) + (1 << t);
    return ask(ch[u][i],t - 1,x);
}
int main() {
    n = read();int ans = 0;rt = ++size;
    for(int i = 1,x;i <= n;i++) {
        x = read();ins(rt,30,x);
        if(i != 1) ans = max(ans,(ask(rt,30,x)));
    }  
    cout << ans << endl;return 0;
}

#include<bits/stdc++.h>
using namespace std;
int read() {int x = 0;scanf("%d",&x);return x;}
const int N = 2e7 + 100;
int ch[N][2],n,a[N],id[N];
int Ans1,Ans2 = 1,Ans3 = 1,rt = 1,size = 1;
void insert(int u,int t,int x,int Id) {
    if(t < 0) {id[u] = Id;return;}    
    int i = ((x >> t) & 1);
    if(!ch[u][i]) ch[u][i] = ++size;
    insert(ch[u][i],t - 1,x,Id);
}
int ask(int u,int t,int x) {
    if(t < 0) return id[u];
    int i = ((x >> t) & 1);
    if(ch[u][!i]) return ask(ch[u][!i],t - 1,x);
    else return ask(ch[u][i],t - 1,x);
}
int main() {
    n = read();a[0] = 0;
    for(int i = 1;i <= n;i++) a[i] = (a[i - 1] ^ read());
    for(int i = 1;i <= n;i++) {
        insert(rt,22,a[i - 1],i);
        int x = ask(rt,22,a[i]) - 1;
        if((a[x] ^ a[i]) > Ans1) 
        {Ans1 = (a[x] ^ a[i]);Ans2 = x + 1;Ans3 = i;}
    }
    cout << Ans1 << " " << Ans2 << " " << Ans3 << endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;
const int N = 6e6 + 10;
int read() {int x;scanf("%d",&x);return x;}
int si[N],ch[N][2],size = 1,rt = 1;
int n,m,last;
void insert(int u,int t,int x) {
    if(t < 0) {si[u] = 1;return;}
    int i = (x >> t) & 1;
    if(!ch[u][i]) ch[u][i] = ++size;
    insert(ch[u][i],t - 1,x);
    si[u] = si[ch[u][0]] + si[ch[u][1]]; 
}
int query(int u,int t,int x) {
    if(t < 0 || u == 0) return 0;
    int i = (x >> t) & 1;
    if((1 << t) != si[ch[u][i]]) return query(ch[u][i],t - 1,x);
    else return query(ch[u][!i],t - 1,x) + (1 << t);
}
int main() {
    n = read();m = read();
    for(int i = 1,a;i <= n;i++) a = read(),insert(rt,20,a);
    while(m--) {
        int x = read();last ^= x;
        printf("%d\n",query(rt,20,last));
    }
    return 0;
}


#include<bits/stdc++.h>
using namespace std;
const int N = 6e6 + 100;
int read() {int x;scanf("%d",&x);return x;}
int ch[N][2],si[N],size = 1,rt = 1;
void insert(int u,int t,int x) {
    if(t < 0) return;
    int i = (x >> t) & 1;
    if(!ch[u][i]) ch[u][i] = ++size;
    si[ch[u][i]]++;insert(ch[u][i],t - 1,x);
}
void erase(int u,int t,int x) {
    if(t < 0) return;
    int i = (x >> t) & 1;
    si[ch[u][i]]--;erase(ch[u][i],t - 1,x);
} 
int query(int u,int t,int x) {
    if(t < 0) return 0;
    int i = (x >> t) & 1;
    if(si[ch[u][i]]) return query(ch[u][i],t - 1,x) + (i << t);
    else return query(ch[u][!i],t - 1,x) + ((!i) << t);
}
int a[N],b[N];
int main() {
    int n = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    for(int i = 1;i <= n;i++) b[i] = read(),insert(rt,30,b[i]);
    for(int i = 1;i <= n;i++) {
        int y = query(rt,30,a[i]);
        printf("%d ",(y ^ a[i]));
        erase(rt,30,y);
    }
}



#include<bits/stdc++.h>
using namespace std;
#define ll long long
int read() {int x;scanf("%d",&x);return x;}
const int N = 4e6 + 100;
const ll inf = 0x3f3f3f3f3f3f3f3f;
int L[N],R[N],a[N],ch[N][2],size = 1,rt = 1,n;
void ins(int u,int t,int x,int id) {
    if(L[u]) L[u] = min(id,L[u]);else L[u] = id;
    if(R[u]) R[u] = max(id,R[u]);else R[u] = id;    
    if(t < 0) return;
    int i = ((x >> t) & 1);
    if(!ch[u][i]) ch[u][i] = ++size;
    ins(ch[u][i],t - 1,x,id);
}
ll query(int u,int t,int x) {
    if(t < 0) return 0;
    int i = ((x >> t) & 1);
    if(ch[u][i]) return query(ch[u][i],t - 1,x);
    else return query(ch[u][!i],t - 1,x) + (1 << t);
}
ll solve(int u,int t) {
    if(t < 0) return 0;
    if(ch[u][0] && ch[u][1]) {
        ll mi = inf;
        for(int i = L[ch[u][1]];i <= R[ch[u][1]];i++) mi = min(mi,query(ch[u][0],t - 1,a[i]));
        return solve(ch[u][0],t - 1) + solve(ch[u][1],t - 1) + (1 << t) + mi;  
    }
    if(ch[u][0]) return solve(ch[u][0],t - 1);
    if(ch[u][1]) return solve(ch[u][1],t - 1);
}
int main() {
    n = read();
    for(int i = 1;i <= n;i++) a[i] = read();
    sort(a + 1,a + 1 + n);
    for(int i = 1;i <= n;i++) ins(rt,31,a[i],i);
    printf("%lld\n",solve(rt,31));
} 


#include<bits/stdc++.h>
using namespace std;
const int N = 4000100;
int rt[N],ch[N<<2][2],cnt[N<<2],size = 0,n,m,qz[N];
int read(){int x;scanf("%d",&x);return x;}
void ins(int a,int b,int t,int x)
{
    if(t < 0) return;
    int i = (x>>t)&1;
    ch[a][i^1] = ch[b][i^1];
    ch[a][i] = ++size;
    cnt[ch[a][i]] = cnt[ch[b][i]] + 1;
    ins(ch[a][i],ch[b][i],t-1,x); 
}
int qu(int a,int b,int t,int x){
    if(t < 0) return 0;
    int i = (x>>t)&1;
    if(cnt[ch[b][!i]] > cnt[ch[a][!i]])
    return (1<<t)+qu(ch[a][!i],ch[b][!i],t-1,x);
    return qu(ch[a][i],ch[b][i],t-1,x);
}
int main()
{
    n = read();m = read();
    rt[0] = ++size;
    ins(rt[0],0,25,0);
    for(int i = 1;i <= n;i++) {
        int a = read();
        qz[i] = qz[i-1]^a;
        rt[i] = ++size;
        ins(rt[i],rt[i-1],25,qz[i]);
    }
    for(int i = 1;i <= m;i++) {
        char ch[5];
        scanf("%s",ch);
        if(ch[0] == 'A') {
            int b = read();
            n++;
            qz[n] = qz[n-1]^b;
            rt[n] = ++size;
            ins(rt[n],rt[n-1],25,qz[n]);
        }
        else {
            int a = read(),b = read(),x = read();
            a--;b--;
            if(a == 0) printf("%d\n",qu(0,rt[b],25,qz[n]^x));
            else printf("%d\n",qu(rt[a-1],rt[b],25,qz[n]^x));
        }
    }
    return 0;
}