0-1 Trie
大家都知道，$\text{trie}$ 很有用，具体可以见我的 字符串笔记，而 $\text{0-1 trie}$ 就是字符集只有 ${0,1}$ 的 $\text{trie}$，可以维护各种带修的异或问题。
那默认大家都会 $\text{trie}$ 了，我们直接讲点 $\text{0-1 trie}$ 的应用。
应用 1 维护异或极值
P4551 最长异或路径
对于此题，我们先预处理出根节点到每个点的异或值，记作 $a_u$，此时一条路径 $(u,v)$ 就转化为 $(root,u)\oplus(root,v)$，异或值就是 $a_u\oplus a_v$。
正确性在于，异或两个相同数时会变成 $0$，所以从 $lca(u,v)$ 往上的重复部分都被抵消了。
此时我们把问题转化为在一个数列中找异或值最大的两个数。
所以我们以每个 $a_i$ 的二进制从高位到低位建一棵 $\text{0-1 trie}$。对于每个 $a_i$，尝试每一位都在树上寻找与这一位不同的另一个方向，这样异或以后该位为 $1$。
如果有就统计上答案，否则先跟着走。因为二进制高位更大则一定更大，所以贪心正确。
#include<bits/stdc++.h>
using namespace std;
#define F(i,x,y) for(int i=(x);i<=(y);++i)
#define Fo(i,x,y) for(int i=(x);i>=(y);--i)
const int N=1e5+10,INF=0x3f3f3f3f;
int n;
int dis[N],cnt,ans;
int t[N<<5][2];
void insert(int x){
int p=0;
Fo(i,31,0){
int c=(x>>i)&1;
if(!t[p][c]) t[p][c]=++cnt;
p=t[p][c];
}
}
int query(int x){
int p=0,res=0;
Fo(i,31,0){
int c=(x>>i)&1;
if(t[p][c^1]) p=t[p][c^1],res=res*2+1;
else p=t[p][c],res=res*2;
}
return res;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
F(i,1,n) cin>>dis[i],insert(dis[i]);
F(i,1,n) ans=max(ans,query(dis[i]));
cout<<ans<<endl;
return 0;
}
|
应用 2 维护异或和
我们先来点定义：设 $t_{u,0/1}$ 表示 $u$ 的 左右儿子，$w_u$ 表示 $u$ 子树中的点数，$s_u$ 表示以 $u$ 为根子树的异或和。
对于一些二进制数，从低位向高位建立 $\text{0-1 trie}$，然后类似动态开点线段树的方式维护。
异或和中当前位是 $1$ 的充要条件为：当前位恰有奇数个 $1$。所以我们只关心奇偶性，不关心具体的值。
我们先把每一个数都往前补位补满 $0$，然后我们一直往下走，走到底以后将到根节点所有 $w$ 增加 $1$，递归往上处理信息
因为插入与删除几乎完全相同，区别只有走到底以后增加还是减少，所以合并成了一个函数。记得动态开点。
void modify(int &p,int x,int d,int op){
if(op==1&&!p) p=++cnt;
if(d>Maxh) return (void)(w[p]=w[p]+op);
modify(t[p][x&1],x>>1,d+1,op);
pushup(p);
}
|
代码中的 $\text{op}$ 表示插入/删除，$\text{Maxh}$ 是定义最大深度（二进制最大长度）。
无非就是合并 $w$ 和 $s$，对于 $w$，就是两个子节点的和。
$s$ 要分类讨论一下，左儿子的信息可以直接乘二合并，右儿子则要看一下 $w$ 的奇偶性。
至于为什么乘二，儿子走到父亲的时候相当于在末尾加了一位，也就是左移一位。
void pushup(int p){
w[p]=s[p]=0;
if(ls) w[p]+=w[ls],s[p]^=(s[ls]<<1);
if(rs) w[p]+=w[rs],s[p]^=(s[rs]<<1)|(w[rs]&1);
}
|
这里的 $\text{ls,rs}$ 是 define 的左右儿子。
对于一个二进制，加 $1$ 操作实际就是从低位向高位找第一个 $0$，将其变为 $1$ 后把低位所有的 $1$ 变成 $0$。
比如 $1000111 + 1 = 1001000$。
所以我们不停地交换左右儿子（把低位 $1$ 变成 $0$）直到交换后左二子（原右儿子）不是 $1$，表示这一位一开始是 $0$。
void update(int p){
swap(ls,rs);
if(ls) update(ls);
pushup(p);
}
|
与线段树合并相同，对于两个位置，有一个空时直接赋值为另一个，否则手动维护一下 $w$ 和 $s$。
int merge(int a,int b){
if(!a) return b;
if(!b) return a;
w[a]=w[a]+w[b];
s[a]^=s[b];
t[a][0]=merge(t[a][0],t[b][0]);
t[a][1]=merge(t[a][1],t[b][1]);
return a;
}
|
P6018 [Ynoi2010] Fusion tree
前面的神秘题目背景是什么（晕）
我们考虑对于每个点开 $\text{0-1 trie}$，维护其直系子节点的信息。
以下记 $tire_x$ 表示 $x$ 的那棵树，记 $a_x$ 表示 $x$ 点的值。
操作 $1$，对于儿子，我们修改 $tire_x$ 即可，对于父亲，父亲的信息保存在父亲的父亲（祖父）的 $\text{0-1 trie}$ 里，所以修改 $a_{fa_x}$ 和 $\large trie_{fa_{fa_x}}$。
这里修改祖父时直接删除原父亲值并加入一个新的修改值即可。
操作 $2$，直接修改 $a_x$，并修改 $tire_{fa_x}$ 的信息。
操作 $3$，发现直接查询 $s_x\oplus a_x$ 并不正确，因为没有考虑父亲执行操作 $1$ 时对儿子 $a$ 值的影响。
暴力修改肯定不优，我们用一个标记数组来记录此点执行了几次操作 $1$。查询时异或上即可。
细节比较多，注意数据中有 $\text{hack}$ 点，根节点默认设 $1$ 就能避免。
#include<bits/stdc++.h>
using namespace std;
#define F(i,x,y) for(int i=(x);i<=(y);++i)
#define ls t[p][0]
#define rs t[p][1]
const int N=5e5+10,M=N*23,Maxh=21;
int n,m,rt[N];
int t[M][2],w[M],s[M],cnt;
void pushup(int p){
w[p]=s[p]=0;
if(ls) w[p]+=w[ls],s[p]^=(s[ls]<<1);
if(rs) w[p]+=w[rs],s[p]^=(s[rs]<<1)|(w[rs]&1);
}
void modify(int &p,int x,int d,int op){
if(op==1&&!p) p=++cnt;
if(d>Maxh) return (void)(w[p]=w[p]+op);
modify(t[p][x&1],x>>1,d+1,op);
pushup(p);
}
void update(int p){
swap(ls,rs);
if(ls) update(ls);
pushup(p);
}
int a[N],tag[N],fa[N];
struct edge{
int v,next;
}e[N<<1];
int head[N],tot;
void add(int u,int v){
e[++tot]={v,head[u]};
head[u]=tot;
}
void dfs(int u,int f){
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
if(v==f) continue;
fa[v]=u;
dfs(v,u);
}
}
int find(int x){
if(!fa[x]) return a[x];
return tag[fa[x]]+a[x];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n>>m;
int op,x,y;
F(i,1,n-1){
cin>>x>>y;
add(x,y);
add(y,x);
}
dfs(1,0);
F(i,1,n){
cin>>a[i];
if(fa[i]) modify(rt[fa[i]],a[i],0,1);
}
while(m--){
cin>>op;
if(op==1){
cin>>x;
tag[x]++;
if(x!=1){
if(fa[fa[x]]) modify(rt[fa[fa[x]]],find(fa[x]),0,-1);
a[fa[x]]++;
if(fa[fa[x]]) modify(rt[fa[fa[x]]],find(fa[x])+1,0,1);
}
update(rt[x]);
}
else if(op==2){
cin>>x>>y;
if(x!=1) modify(rt[fa[x]],find(x),0,-1);
a[x]-=y;
if(x!=1) modify(rt[fa[x]],find(x),0,1);
}
else{
cin>>x;
int res=s[rt[x]];
res^=find(fa[x]);
cout<<res<<endl;
}
}
return 0;
}
|
P6623 [省选联考 2020 A 卷] 树
考虑每个点建立 $\text{0-1 trie}$，一开始存权值，使用 dfs 自底向上合并子树以后全局加，表示距离的增加。
有没有人解释一下数据范围有什么特殊含义 qwq。
#include<bits/stdc++.h>
using namespace std;
#define F(i,x,y) for(int i=(x);i<=(y);++i)
#define ls t[p][0]
#define rs t[p][1]
const int N=525100,M=N*23,Maxh=21;
int n,rt[N],a[N];
int t[M][2],w[M],s[M],cnt;
long long ans;
void pushup(int p){
w[p]=s[p]=0;
if(ls) w[p]+=w[ls],s[p]^=(s[ls]<<1);
if(rs) w[p]+=w[rs],s[p]^=(s[rs]<<1)|(w[rs]&1);
}
void modify(int &p,int x,int d){
if(!p) p=++cnt;
if(d>Maxh) return (void)(w[p]++);
modify(t[p][x&1],x>>1,d+1);
pushup(p);
}
int merge(int a,int b){
if(!a) return b;
if(!b) return a;
w[a]=w[a]+w[b];
s[a]^=s[b];
t[a][0]=merge(t[a][0],t[b][0]);
t[a][1]=merge(t[a][1],t[b][1]);
return a;
}
void update(int p){
swap(ls,rs);
if(ls) update(ls);
pushup(p);
}
struct edge{
int v,next;
}e[N<<1];
int head[N],tot;
void add(int u,int v){
e[++tot]={v,head[u]};
head[u]=tot;
}
void dfs(int u){
for(int i=head[u];i;i=e[i].next){
int v=e[i].v;
dfs(v);
update(rt[v]);
rt[u]=merge(rt[u],rt[v]);
}
ans+=1ll*s[rt[u]];
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin>>n;
F(i,1,n) cin>>a[i],modify(rt[i],a[i],0);
int x;
F(i,2,n) cin>>x,add(x,i);
dfs(1);
cout<<ans<<endl;
return 0;
}
|
