介绍
Trie树可以快速查找字符串，通过合并前缀来节省空间，一般用于解决字符串和最大异或和（01Trie）问题。
一般在插入字符串时，会在串的尾部打上标记，用于统计类问题。
题目
P8511 [Ynoi Easy Round 2021] TEST_68
思路
假设在树上任取两点，当两点异或值最大时，点的编号为 \(x\) 和 \(y\)，那么子树内不包含这两个点的点的答案都为 \(a_x \oplus a_y\)。
可以发现这些点都不在 \(x \to 1\) 和 \(y \to 1\) 上，于是对这两类点分讨。
实现
全部数中的异或最大值显然可以用 01Trie 解决，于是先预处理 \(x\) 和 \(y\)，然后暴力找到 \(x \to 1\) 和 \(y \to 1\)。对于这两条路径，从根开始遍历，每次把每个非链上的儿子所在的子树加入 \(trie\)，然后再顺着链往下跑。
因为 \(x,y\) 都不固定，所以每次加入时都要查询一次并取最值。
code:(耗时 5h T^T)
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
//#define int long long
//#define int unsigned long long
using namespace std;
//const int p=415411;
const int iinf=2147483647;
const long long linf=9223372036854775807;
const int N=5e5+10;
int n,fa[N],mx,my,nxt[N];
long long a[N],ans[N],maxn;
bool fl[N];
vector<int> g[N];
struct Trie
{
int len=1,t[N*64][2],g[70],end[N*64];
void init()
{
maxn=0;
memset(t,0,sizeof(t));
memset(end,0,sizeof(end));
len=1;
}
void ins(int id)
{
long long x=a[id];
for(int i=1;i<=60;i++)g[i]=x%2,x/=2;
int now=1;
for(int i=60;i>=1;i--)//逆序!!1111
{
if(!t[now][g[i]])t[now][g[i]]=len+1,len++;
now=t[now][g[i]];
}
end[now]=id;
}
int que(long long x)
{
for(int i=1;i<=60;i++)g[i]=x%2,x/=2;
int now=1;
for(int i=60;i>=1;i--)
{
if(t[now][g[i]^1])now=t[now][g[i]^1];
else if(t[now][g[i]])now=t[now][g[i]];
else return 0;
}
return end[now];
}
}tr;
int find(int x,int y)
{
fl[x]=1;
while(x!=1)nxt[fa[x]]=x,x=fa[x],fl[x]=1;
fl[y]=1;//
while(!fl[fa[y]])
{
nxt[fa[y]]=y;
fl[fa[y]]=1,y=fa[y];
}
return y;
}
void find2(int x)
{
while(x!=1)nxt[fa[x]]=x,x=fa[x];
}
void dfs2(int x)
{
tr.ins(x);
maxn=max(maxn,a[x]^a[tr.que(a[x])]);
for(int v:g[x])dfs2(v);
}
void dfs(int x)
{
ans[x]=maxn;
int q=tr.que(a[x]);
if(q)maxn=max(maxn,a[x]^a[q]);
//注意一定要在有值的时候才更新，不然会被根和儿子相同的情况卡掉T^T
tr.ins(x);
for(int v:g[x])
{
if(v==nxt[x])continue;
dfs2(v);
}
if(nxt[x])dfs(nxt[x]);
}
signed main()
{
tr.init();
scanf("%d",&n);
for(int i=2;i<=n;i++)
{
scanf("%d",&fa[i]);
g[fa[i]].push_back(i);
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
int id=tr.que(a[i]);
tr.ins(i);
if(id&&(a[id]^a[i])>=maxn)maxn=(a[id]^a[i]),mx=id,my=i;
}
long long mmm=maxn;
int lca=find(mx,my);//找链
tr.init();
dfs(1);
tr.init();
find2(lca);
dfs(1);
for(int i=1;i<=n;i++)if(!fl[i])ans[i]=mmm;//不在链上
for(int i=1;i<=n;i++)printf("%lld\n",ans[i]);
}
P4735 最大异或和
思路
可持久化 \(01trie\) 板子。
维护一个前缀异或和序列 \(b\)，每个询问变为 \(max_{l-1}^{r-1} \ b_i \oplus b_n \oplus x\)，\(b_n \oplus x\) 为定值，预处理即可。
实现
code:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<set>
//#define int long long
//#define int unsigned long long
using namespace std;
//const int p=415411;
const int iinf=2147483647;
const long long linf=9223372036854775807;
const int N=6e5+10;
int n,m,len=1,rt[N],t[N*30][2],a[N],qt=1,cnt[N*30],l,r,x;
char ch;
void ins(int q,int p,int w,int x)
{
if(w<0)return;
int now=(x>>w)&1;
t[q][now^1]=t[p][now^1];
t[q][now]=qt;
qt++;
cnt[t[q][now]]=cnt[t[p][now]]+1;
ins(t[q][now],t[p][now],w-1,x);
}
int que(int p,int q,int w,int x)
{
if(w<0)return 0;
int now=(x>>w)&1;
if(cnt[t[q][now^1]]>cnt[t[p][now^1]])return (1<<w)+que(t[p][now^1],t[q][now^1],w-1,x);
return que(t[p][now],t[q][now],w-1,x);
}
signed main()
{
scanf("%d%d",&n,&m);
rt[0]=qt;
qt++;
ins(rt[0],0,25,0);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
a[i]^=a[i-1];
rt[i]=qt;
qt++;
ins(rt[i],rt[i-1],25,a[i]);
}
while(m--)
{
cin>>ch;
if(ch=='A')
{
cin>>x;
n++;
a[n]=a[n-1]^x;
rt[n]=qt;
qt++;
ins(rt[n],rt[n-1],25,a[n]);
}
if(ch=='Q')
{
cin>>l>>r>>x;
l--,r--;
if(!l)cout<<que(0,rt[r],25,x^a[n])<<endl;
else cout<<que(rt[l-1],rt[r],25,x^a[n])<<endl;
}
}
}