前言：
回来上课吧，不然真的就没人了。现在也是没有脑子
一、Trie树学习笔记+杂题（进阶1 Trie）
相关题单：戳我
1.trie树简介
字典树，英文名 trie。顾名思义，就是一个像字典一样的树，核心原理就是用空间换时间，利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，所以它可以处理多个字符串，不像哈希每一次只能针对一个字符串进行处理。
查询和修改的时间复杂度都是\(O(len)\)的，\(len\)是单词的长度。（所以空间充足的情况下可以考虑trie树）
一般来说你需要三个数组，分别代表trie树，当前节点被遍历的次数，以及是否有以当前节点为结尾的单词。
int tree[M][27],num[M],endd[M];//一般来说，trie树你需要开：单词总长度（前一维）*出现不同字符数（比如小写字母的字符数就是26个）
int cnt=1;//这个就是你的节点标号，一般从1开始
写成结构体可能会清晰一点
struct Tire{
int x[27],num,endd;
};Tire tree[M];
（1）字典树的建立
暴力的将每一个单词全部插入进树中，每走到一个节点就判断当前节点的儿子中是否有我们当前要插入的字符，有的话就直接到对应儿子，没有的话就新建一个节点，然后跳到新建节点上。
代码：
inline void insert()
{
int pos=1,len=strlen(s+1);//s是单词
for(int i=1;i<=len;i++)
{
int num=s[i]-'a';//字符转化为数字
if(!tree[pos].x[num]) tree[pos].x[num]=++cnt;//当前节点没有代表这个字符的儿子就新建一个
pos=tree[pos].x[num];//继续向下建树
tree[pos].num++;//当前节点遍历次数+1
}
tree[pos].endd++;//当前单词以pos为结尾
}
（2）字典树的查询
其实和字典树的建立是一样的，从前向后依次遍历单词中每一个字符，如果当前节点有代表需要字符的儿子，那么就跳到儿子上去，如果没有代表其的儿子，那么说明匹配失败，返回0。
inline int find()
{
int pos=0,len=strlen(s+1);
for(int i=1;i<=len;i++)
{
int num=getnum(s[i]);
if(!tree[pos].x[num]) return 0;//没有找到匹配失败
pos=tree[pos].x[num];//跳儿子
}
return tree[pos].endd;//返回以当前节点结尾的单词个数
}
（3）删除
还是和查找一个操作，你还是一样的遍历一棵树，然后对于每一个被遍历的节点减一就可以了。
2.01trie简介
实际上就是将每一个数都拆成了二进制，将每个数的二进制建成一颗字典树，在处理异或/异或和方面比较有用，见到题的时候再说。
（1）01trie的建立
将每一个数的二进制插入树中，依据题目的要求观察是从高位向低位插，还是从低位向高位插
inline void insert(int x)
{
int pos=1;
for(int i=(1<<30);i;i>>=1)//一般来说最高位要依据题目说明的值域来设
{
bool opt=i&x;//要使用bool类型，因为int类型得到的是1 2 4 8 等数值
if(!tree[pos][opt]) tree[pos][opt]=++cnt;
pos=tree[pos][opt];
num[pos]++;
}//正常建树
}
（2）查询
一样的，一般来说01trie都不考查询的，都是与异或相关的操作。
3.AC自动机
我会专门写哒，咕咕咕。
4.习题
（1）普通trie树
P8306 【模板】字典树
就是一道板子题咯，直接就是用上面给出的操作+输入输出就可以了，要注意的是有多组数据，由于字典树开的空间很大，所以每一次memset是不行的，只能是用了几个节点就清空几个节点。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=3e6+5;//由于输入字符串的总长度不超过3e6
int T,n,q;
char s[M];
int cnt=1;
struct Trie{
int x[65],num;//不同的字符有小写字母+大写字母+阿拉伯数字 每个节点出现了多少次
};Trie tree[M];
inline void pre()//清空
{
for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=64;j++) tree[i].x[j]=0;
tree[i].num=0;
}
}
inline int getnum(char x)
{
if(x>='0'&&x<='9') return x-'0';//阿拉伯数字就是0-9
if(x>='A'&&x<='Z') return x-'A'+10;//大写字母就是10-36
return x-'a'+37;//小写字母37-63
}
inline void insert()
{
int pos=1,len=strlen(s+1);
for(int i=1;i<=len;i++)
{
int num=getnum(s[i]);
if(!tree[pos].x[num]) tree[pos].x[num]=++cnt;//没有就新建
pos=tree[pos].x[num];//向下建树
tree[pos].num++;//每个被遍历的节点次数+1
}
}
inline int find()
{
int pos=1,len=strlen(s+1);
for(int i=1;i<=len;i++)
{
int num=getnum(s[i]);
if(!tree[pos].x[num]) return 0;//找不到了，匹配失败
pos=tree[pos].x[num];//向下搜
}
return tree[pos].num;//直接搜完之后的节点被遍历到的次数，因为求得是前缀
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>T;
while(T--)
{
cin>>n>>q;
pre();cnt=1;//每一次都是新的字典树，节点数清零
for(int i=1;i<=n;i++)
{
cin>>s+1;
insert(); //插入
}
for(int i=1;i<=q;i++)
{
cin>>s+1;
cout<<find()<<"\n";//查找
}
}
return 0;
}
P2580 于是他错误的点名开始了
同样是一道典题，但是我么每一次查找的时候需要进行一些操作。首先肯定是将所有同学的名字全部插入，建成一颗字典树，然后进行查找。
在查找的时候，根据题目的要求，如果没要找到那自然是输出WRONG。如果我们找到了一个节点，但是我们发现那个节点上没有终止标记，说明没有单词在当前节点结束，所以相当于还是没有这个名字，输出WRONG。如我我们最后到达了一个节点，并且发现了有结束标记，那么代表匹配上了，输出OK，然后打上标记。如果我们搜索完一个名字，到达一个节点并有结束标记，但是是被标记匹配过的，那么就说明名字已经念过了，输出REPEAT。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
#define int long long
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=1e6+5;//最多有1e4个名字，每个名字最长50，实际上开5e5就可以了
int n,q;
char s[M];
int cnt=0;
struct Tire{
int x[27],num;//全是小写字母，不同字符的个数就是26
};Tire tree[M];
inline void insert()
{
int pos=0,len=strlen(s+1);
for(int i=1;i<=len;i++)
{
int num=s[i]-'a';
if(!tree[pos].x[num]) tree[pos].x[num]=++cnt;
pos=tree[pos].x[num];
}
tree[pos].num=1;//每个单词的最后打上标记
}//正常插入
inline void find()
{
int pos=0,len=strlen(s+1);
for(int i=1;i<=len;i++)
{
int num=s[i]-'a';
if(!tree[pos].x[num])
{
cout<<"WRONG\n";return ;//如果没有找到对应的字符，那么就肯定念错了，输出后返回
}
pos=tree[pos].x[num];//向下跳
}
if(!tree[pos].num)//没有结尾
{
cout<<"WRONG\n";return ;//说明没有这个单词
}
else if(tree[pos].num==1)//有以当前节点结尾的单词，并且没有被念过
{
cout<<"OK\n";tree[pos].num=2;//输出并标记
return ;
}
cout<<"REPEAT\n";//剩下的情况说明是念重了
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>s+1,insert();
cin>>q;
for(int i=1;i<=q;i++) cin>>s+1,find();
return 0;
}//主函数里都是正常的操作
SP4033 PHONELST - Phone List
上两道题的多倍经验，也是多组询问，所以注意清空方式。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
#define int long long
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=3e6+5;
int T,n,q,flag;
char s[M][11];
int cnt=1;
struct Trie{
int x[10],num;//字符集只有阿拉伯数字哒
};Trie tree[M];
inline void pre()//注意清空方式
{
for(int i=0;i<=cnt;i++)
{
for(int j=0;j<=9;j++) tree[i].x[j]=0;
tree[i].num=0;
}
}
inline void insert(int id)
{
int pos=1,len=strlen(s[id]+1);
for(int i=1;i<=len;i++)
{
int num=s[id][i]-'0';
if(!tree[pos].x[num]) tree[pos].x[num]=++cnt;
pos=tree[pos].x[num];
tree[pos].num++;
}
}
inline void find(int id)
{
int pos=1,len=strlen(s[id]+1);
for(int i=1;i<=len;i++)
{
int num=s[id][i]-'0';
if(!tree[pos].x[num]) return ;
pos=tree[pos].x[num];
}
if(tree[pos].num>1) flag=1;//就是找前缀嘛，但是要注意由于自己肯定是遍历过的，所以如果当前好嘛是其他号码的前缀的话，当前节点被便利不止一次。
return ;
}
signed main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
cin>>T;
while(T--)
{
cin>>n;
pre();cnt=1,flag=0;
for(int i=1;i<=n;i++)
{
cin>>s[i]+1;
insert(i);
}
for(int i=1;i<=n;i++)
{
find(i);if(flag) break; //记录一下有没有，已经找到了就退出，节约时间
}
if(flag) cout<<"NO\n";
else cout<<"YES\n";
}
return 0;
}
P1481 魔族密码
可以用字典树嘛？好像有点麻烦了，建议使用STL+DP直接水过去。详情见这
P3879 [TJOI2010] 阅读理解
同样的，字符串很多的题在现在功能强大的STL与骗分神奇哈希思想的结合下都成了水题，当然你也可以思考这道题的字典树写法。但是肯定不如STL来的暴力。详情见这
P5149 会议座位
有点离谱了，原来我这道题还是用STL+哈希莽过去的，那就说一下STL+哈希的写法吧。
首先对于每一个老师的名字定义一个map来映射，映射的值就是一开始老师们的座位表。然后将新的座位输入后通过map映射回来，那么不满值就很简单了，就是找这个序列的逆序对。
说起来有点抽象，以样例为例。
3
Stan Kyle Kenny
Kyle Stan Kenny
使用map将Stan映射成1，Kyle映射成2，Kenny映射成3。然后用一个数组存改变后映射回来的值，就是2 1 3，答案就是这个序列的逆序对数，显然是1。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<map>
#define int long long
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=1e5+5;
int n,ans=0;
int a[M],c[M];
string s;
map<string,int> mapp;//map去映射老师的名字，相当方便
inline void msort(int l,int r)//求逆序对有归并排序和树状数组两种方式，这里使用的是归并排序
{
if(l==r) return ;
int mid=(l+r)>>1,lx=l,rx=mid+1,cnt=l;
msort(l,mid),msort(mid+1,r);
while(lx<=mid&&rx<=r)
{
if(a[lx]<=a[rx])
{
c[cnt++]=a[lx++];
}
else c[cnt++]=a[rx++],ans+=mid-lx+1;//归并的同时求出逆序对数
}
while(lx<=mid) c[cnt++]=a[lx++];
while(rx<=r) c[cnt++]=a[rx++];
for(int i=l;i<=r;i++) a[i]=c[i];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>s,mapp[s]=i;
for(int i=1;i<=n;i++) cin>>s,a[i]=mapp[s];//映射过去又映射回来
msort(1,n);//求数组a的逆序对数
cout<<ans<<"\n";
return 0;
}
CF898C Phone Numbers
这道题有一点极端，主要是数组开太多了，导致后面有点没法理清思路了。
首先给出了有多少排电话号码，每一排的电话号码都对应一个名字，题目中给出的数据范围是\(n\le 20\)，也就是说最多也就只有20个不同的人，对于这20个人，每个人建一个字典树，使用一个map去映射每个人对应的是第几个字典树，然后将后面的号码插入每个人的字典树。
题目中要求，如果一个人有两个号码\(x\)与\(y\)，且\(x\)是\(y\)的后缀，那么我们就应该将\(x\)删去，最后输出总共有多少个人，每个人的名字与最后合法的号码个数+号码，但是还是比较良心的，不需要按顺序输出。字典树又叫前缀树，只能判断两个字符串之间是否有前缀关系，所以转化一下，将每个字符串都倒着插入字典树中，这样我们就可以用字典树维护后缀了。
对于删除的情况，先将每个人的所有号码放入答案中，再在建树的过程中标记不合法的号码，最后输出的时候只统计并输出合法的号码就可以了。
对于不合法也就两种情况，第一种是前面有一个短的号码，现在在插入一个长的号码，短的号码是长的号码的后缀。那么这种情况，插入的时候，判断便利的每一个点是否被打上了结束标记，如果有，那么就说明在此位置结束的号码是当前插入号码的后缀，将结束标记中存下的号码标记。
第二种是当前插入的是短号码，那么我们需要判断一下结束的时候遍历的那一个点的遍历次数，如果遍历次数大于了1，那么说明除了自己还有其他号码经过了这个点，自己肯定是那个已经插入的点的后缀，那么把自己标记。
每一个人的每一个号码都给它标上号就比较好处理。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
#include<map>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int N=21,M=2e3+5;
int n,idx=0,cnt[N],numb[N];//每个字典树都有一个cnt，numb代表当前插入的是第i个人的第几个号码
string s;
map<string,int> mapp1;map<int,string> mapp2;//映射过去映射回来
struct TREE{
int x[10],num;vector<int> endd;//每个人可能有多个相同的号码，它们会在同一个地方结尾，所以用vector存下全部
};TREE tree[N][M];//每一个人建一个树
int vis[N][N*N]; //记录每个人的每个号码是否合法
vector<string> ans[N];//记录一下每一个人的答案
inline void insert(int id,int number)//当前是第几个人的第几个号码
{
int pos=1;
for(int i=s.size()-1;i>=0;i--)//倒着插
{
int num=s[i]-'0';
if(!tree[id][pos].x[num]) tree[id][pos].x[num]=++cnt[id];
pos=tree[id][pos].x[num];
if(tree[id][pos].endd.size()&&i>=1)//遍历到后缀了
{
for(int j=0;j<tree[id][pos].endd.size();j++)
{
vis[id][tree[id][pos].endd[j]]=1;//将所有以此节点为结尾的字符串标记不合法
}
}
tree[id][pos].num++;//节点遍历次数++
}
tree[id][pos].endd.push_back(number);//将自己的号码放入当前节点的结束标记
if(tree[id][pos].num>1)//已经有比自己长的了，该杀的是自己
{
vis[id][number]=1;//标记自己
}
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
for(int i=1;i<=20;i++) cnt[i]=1;
cin>>n;int id,len;
for(int i=1;i<=n;i++)
{
cin>>s;
if(mapp1[s]) id=mapp1[s];//这个名字已经出现过了
else id=++idx,mapp1[s]=idx,mapp2[idx]=s;.//没有出现过的名字，新开一个
cin>>len;
for(int j=1;j<=len;j++)
{
cin>>s;insert(id,numb[id]++);//这是第几个人，第几个号码了
ans[id].push_back(s);//先全部存上
}
}
cout<<idx<<"\n";//最后到底有多少人
int num=0;
for(int i=1;i<=idx;i++)
{
num=0,cout<<mapp2[i]<<" ";//映射数组，第i个人的名字
for(int j=0;j<numb[i];j++) if(!vis[i][j]) num++;//统计有多少个合法的，没有被标记的
cout<<num<<" ";
for(int j=0;j<numb[i];j++)
{
if(!vis[i][j]) cout<<ans[i][j]<<" ";//输出合法号码
}
cout<<"\n";
}
return 0;
}
P4683 [IOI2008] Type Printer
同样是一道比较麻烦的题，其实trie树本质上就是一颗树，所以你可以在上面运用树的性质或者使用dfs，对于01trie由于每个节点最多就两个儿子，其实就是一棵二叉树，满足线段树的性质，所以有的01trie可以使用线段树或树状数组等数据结构维护。
题目的意思是想让我们实现三种操作，在当前词的尾部添加一个字母；在当前次的尾部减去一个字母（至少有一个字母时）；打印当前词。给出几个单词，问我们将这些单词全部打印出来操作数最少需要多少次，并且输出每一步应该如何操作，其中添加一个字母，用这个小写字母的自身来表示；删去一个字母，用减号表示；打印单词时，用 P 表示。
那我们可以贪心的想，由于打印和添加字母的操作是必须的，为了使最后的操作数最少，那么我们应该让删除的操作最少。那字典树的特点不就是将每个字符串插入其中，具有公共前缀的字符串会遍历相同的节点嘛。那其实答案就是将每一个字符串插入字典树中，然后dfs遍历一棵树就行了，向下遍历的时候就是添加字符，到达一个有结束标记的节点就需要打印，回溯的时候就是删除操作。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=5e6+5;
using namespace std;
int n,tree[M][28];
int val[M],vis[M],f,maxx=-1,cnt,idx;
char s[30000][22],ans[M];
inline void insert(char s[])
{
int pos=0;
for(int i=0;i<strlen(s);i++)
{
int u=s[i]-'a';
if(!tree[pos][u]) tree[pos][u]=++idx;
pos=tree[pos][u];
}
val[pos]=1;
}
inline void mark(char s[])
{
int pos=0;
for(int i=0;i<strlen(s);i++)
{
int u=s[i]-'a';
pos=tree[pos][u];
vis[pos]=1;
}
}
inline void dfs(int now)
{
if(val[now]) ans[++cnt]='P';//如果当前有结束标记就打印
int flag=-1;
for(int i=0;i<26;i++)
{
int ver=tree[now][i];//向下依次遍历
if(!ver) continue;
if(vis[ver])
{
flag=i;
}
else
{
ans[++cnt]=i+'a';
dfs(ver);
}
}
if(flag!=-1)
{
ans[++cnt]=flag+'a';
dfs(tree[now][flag]);
}
if(flag==-1&&vis[now])
{
f=1;
}
if(!f) ans[++cnt]='-';//回溯了
}
signed main()
{
cin>>n;int pos=0;
for(int i=0;i<n;i++)
{
cin>>s[i];
int len=strlen(s[i]);
if(len>maxx) maxx=len,pos=i;
insert(s[i]);//建立字典树
}
mark(s[pos]);//标记最长的单词
dfs(0);//dfs扫一遍，将答案存下来
cout<<cnt<<"\n";
for(int i=1;i<=cnt;i++) cout<<ans[i]<<"\n";
return 0;
}
CF514C Watto and Mechanism
和上面那一道题是差不多类型的，也需要在建好的字典树上dfs找答案。题目需要让我们判断当前字符串是否与其中一个给定的模式串恰好有一个字符不相同。观察数据范围\(n, m \le 3 \times 10^5\)，其中所有字符串的字符属于{'a','b','c'}，且输入总长度 \(\le 6 \times 10^5\)。字符集是3，内存给了250MB，还是相当充裕的，所以可以考虑使用字典树。
建树还是一样的，那么将给出的模式串全部建好字典树之后，我们可以用搜索在字典树上跑，具体的实现方法见代码。我们就将有一位不一样看作是一次操作（改变一个字符），是否可以将询问的字符串进行一次操作使得有给出字符串与它一样。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=6e5+5;
int n,q;
int cnt=1,len=0;
int tree[M][4],endd[M];//输入总长度6e5，字符集是3
char s[M];
inline void insert()
{
int pos=1;len=strlen(s+1);
for(int i=1;i<=len;i++)
{
int opt=s[i]-'a';
if(!tree[pos][opt]) tree[pos][opt]=++cnt;
pos=tree[pos][opt];
}
endd[pos]=1;//结束标记
}
inline int check(int pos,int u,int flag)//分别代表现在是在字典树的哪个节点上，到拿去匹配的字符串的第几位，是否已经有一个字符不一样了
{
if(u!=len)//那没有搜完
{
int opt=s[u+1]-'a';
if(tree[pos][opt])//如果说当前节点有儿子代表当前第u位的字符
{
if(check(tree[pos][opt],u+1,flag)) return 1;//跳到儿子，匹配下一位，是否使用操作的情况不变
}
if(!flag)//没有使用过操作
{
for(int i=0;i<3;i++)
{
if(i!=opt&&tree[pos][i])//不能和这一位一样，并且当前节点要有这个儿子
{
if(check(tree[pos][i],u+1,1)) return 1;//调到对应儿子，匹配下一位，操作情况为1
}
}
}
return 0;
}
else return (flag&&endd[pos]);//坑点是你需要满足两个要求，必须要有在当前节点结束的字符串并且必须要使用一次操作（有一个字符不相同）
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>q;
for(int i=1;i<=n;i++) cin>>s+1,insert();//建树
while(q--)
{
cin>>s+1;len=strlen(s+1);
if(check(1,0,0)) cout<<"YES\n";//如果有匹配的
else cout<<"NO\n";//否则
}
return 0;
}
P2922 [USACO08DEC] Secret Message G
是一道比较水的题。给出一些模式串，然后每次询问给出一个串，问你有多少个模式串与给定的串有相同的前缀，前缀长度等于模式串与给定的串的较小者。
其实思路比较简单，首先将模式串全部插入字典树中。有相同的前缀总共就两种可能，一种是当前串是模式串的前缀，另一种就是模式串是当前串的前缀，对于这两种情况，在建树的时候维护每个点遍历了多少次，以及结束标记。
对于每一次询问，第一种可能的统计方法就是加上匹配不断跳儿子的过程中，加上每一个点的结束标记，如果自己遍历到模式串的结束标记，那么说明这个模式串肯定是自己的前缀。第二种可能就是加上最后匹配完后的那个节点的遍历次数，遍历次数可以说明有多少字符串遍历过这个点，自己一定是这些点的前缀。但是需要进行排重。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=1e4+5,N=3e6+5;
int n,m,len;
int a[M];
int cnt=1;
int tree[N][2],endd[N],num[N]; //就只有01两种字符
inline void insert()
{
int pos=1;
for(int i=1;i<=len;i++)
{
if(!tree[pos][a[i]]) tree[pos][a[i]]=++cnt;
pos=tree[pos][a[i]];
num[pos]++;
}
endd[pos]++;
}
inline int find()
{
int pos=1,res=0;
for(int i=1;i<=len;i++)
{
if(!tree[pos][a[i]]) return res;
pos=tree[pos][a[i]];
res+=endd[pos];//加上一路上的结束标记
}
return res-endd[pos]+num[pos];//加上结束节点的遍历次数，进行排重，遍历次数中已经包含了当前节点的结束标记数
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>m>>n;
for(int i=1;i<=m;i++)
{
cin>>len;
for(int i=1;i<=len;i++) cin>>a[i];
insert();//插入
}
for(int i=1;i<=n;i++)
{
cin>>len;
for(int i=1;i<=len;i++) cin>>a[i];
cout<<find()<<"\n";//查找
}
return 0;
}
（2）01trie
01trie实质上就是将每个数转化为二进制数插入进字典树中，一般都是考察与二进制位运算有关的内容，可以比较巧妙地维护异或等信息。还是得多练。
P4551 最长异或路径
第一题还是讲板子题比较好。体面非常的简洁：给定一棵 \(n\) 个点的带权树，结点下标从 \(1\) 开始到 \(n\)。寻找树中找两个结点，求最长的异或路径。异或路径指的是指两个结点之间唯一路径上的所有边权的异或。
那么由于都说是一棵树了，借助异或的性质，两个相同的数异或起来等于0并且异或具有传递性，所以我们设一个点为根，为了方便就让1为根。那么\((u,v)\)这条路径上的异或值实际上就可以转化为\((1,u)\)的异或值异或上\((1,v)\)的异或值。 首先先将树dfs一遍，与处理出每个点到根节点路径上的异或值，然后将所有节点到根节点路径的异或值全部插入一颗字典树上（要将异或值转化成二进制进行插入）。
然后对于每一个点到根的异或值我们都进行一次查找。由于在二进制下高位严格大于低位，所以每一次都可以贪心的只看当前状态下使答案最大的情况。当我们走到一个节点上时，如果当前节点有与当前来搜索的值二进制下相反的儿子（因为异或是相反就为1），那么我们肯定是走这个相反的儿子，并统计答案。否则我们就只能走二进制下与自己相同的那个儿子。统计最大值并输出。
当然了，这道题肯定是从高位向低位建，不然就没法贪心了。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=2e6+5;
int n;
int cnt=0;
struct N{
int next,to,val;
};N p[M<<1];
int head[M],d[M];
struct Trie{
int x[3];
};Trie tree[M];
inline void add(int a,int b,int c)
{
++cnt;
p[cnt].next=head[a];
head[a]=cnt;
p[cnt].to=b;
p[cnt].val=c;
}
inline void dfs(int u,int fa)
{
for(int i=head[u];i!=0;i=p[i].next)
{
int v=p[i].to;
if(v==fa) continue;
d[v]=d[u]^p[i].val;//预处理出根节点到每一个节点的路径异或值
dfs(v,u);
}
}//遍历整棵树
inline void insert(int id)
{
int pos=0;
for(int i=(1<<30);i;i>>=1)//题目中说w是小于2^31哒，插入操作其实差不了太多
{
bool num=d[id]&i;
if(!tree[pos].x[num]) tree[pos].x[num]=++cnt;
pos=tree[pos].x[num];
}
}
inline int find(int id)
{
int pos=0,res=0;
for(int i=(1<<30);i;i>>=1)
{
bool num=d[id]&i;//求当前这一位上二进制是0是1，注意使用bool类型
if(tree[pos].x[!num]) res+=i,pos=tree[pos].x[!num];//有相反的，那就走相反的，贡献就是当前的i
else pos=tree[pos].x[num];//否则的话就走相同的
}
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
int a,b,c;
for(int i=1;i<n;i++)
{
cin>>a>>b>>c;
add(a,b,c),add(b,a,c);
}
dfs(1,0);
cnt=0;int ans=0;
for(int i=1;i<=n;i++) insert(i);//插入
for(int i=1;i<=n;i++) ans=max(ans,find(i));//统计最大值
cout<<ans<<"\n";
return 0;
}
CF842D Vitya and Strange Lesson
与线段树有关的一道题，但是只是一些基础的思想迁移，整体还是较为简单的。给出你一个长度为 \(n\)的非负整数序列以及\(m\)个询问，每次询问先给你一个整数 \(x\)，把序列中所有数异或上\(x\)输出序列的 \(mex\)（\(mex\)就是最小的没有出现的非负数），在每个询问过后序列是发生变化的。
既然是整体异或，那么我们就不要写一些极为恐怖的维护操作，由于异或具有交换律与结合律，所以只需要一个全局异或变量将所有给出的异或值全部异或在一起就可以了。而mex似乎用字典树并不是那么好的去维护，那我们考虑在二进制下，如果一个区间里面的数全部都存在，那么我们需要什么。很显然，我们需要一个siz数组，来记录字典树中每一个节点下有多少个点。（md，还是有点太抽象了，语文水平不足，还是上图吧）。
以样例三进行建树，至于没那么大，所以前面的的点就不展现出来了，反正就是根节点一直连向代表0的那条边。样例三一开始数组中有5个数，0，1，5，6，7。那我们可以明显的看出0的结束位置就是8号，1是9号，5是13号，6是14号，7是15号。第一个询问是1，此时全局异或变量异或上\(x\)，此时也是1。由于要找最小的没有出现过的非负数，肯定是贪心的走与自己二进制下这一位相同的边（这里的边在trie上其实表现为儿子）。
但是有时候就不能走了，比如说我们想走的那条边已经被塞满了，如图，1从节点1出发，贪心的走0边到达了2号点。然后它本应该继续的贪心走0边到达4号点（因为现在是倒数第二位，表现为数值就是2，1的二进制倒数第二位是0），但是它发现4号节点下面转满了（siz[4]==（1<<i）），没有位置塞下另外一个数了，所以它只能走1边，然后再走1边，到达mex。（现在应该要直观一点了）。
所以我们就需要利用与线段树类似的方法处理每一个节点下数值的个数。
具体看代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=1e7+5;
int n,q;
int cnt=1;
int tree[M][2],num[M],siz[M],sum=0;//全局异或变量
inline void insert(int x,int pos,int now)
{
if(now==-1)
{
siz[pos]=1;return ;
}
bool opt=x>>now&1;
if(!tree[pos][opt]) tree[pos][opt]=++cnt;//没有就建
insert(x,tree[pos][opt],now-1);//向下建树
siz[pos]=siz[tree[pos][0]]+siz[tree[pos][1]];//处理siz数组
}//trie树线段树类似得建法
inline int query(int x)
{
int u=1,res=0;
for(int i=19;i>=0;--i)
{
int s=x>>i&1;
if(siz[tree[u][s]]==((1<<i))) u=tree[u][s^1],res|=(1<<i);//如果与全局异或二进制下相同的点siz满了，那么就累加答案，走相反的边
else u=tree[u][s];//可以走相同的边就走相同的边
if(!u) return res;//闯入死路了，这时它可以随便走，就没法产生贡献了，返回（例如上图中走4号节点的1儿子，这时里面没有数字了，没法产生贡献）
}
return res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>q;int x;
for(int i=1;i<=n;i++) cin>>x,insert(x,1,19); //建树
while(q--)
{
cin>>x;sum^=x;
cout<<query(sum)<<"\n";
}
return 0;
}
CF665E Beautiful Subarrays
题目要求我们求出求以第\(i\)个数结尾的区间异或和大于等于k的有多少，使用异或前缀和来解题。
将每个点的前缀异或和放入字典树中，然后对于每一个点的异或前缀和进行查找。由高位到低位考虑每位，如果到该位异或的结果已经大于k，就累计，如果小于k，直接无视，到该位不能确定，接着往下一层走。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=3e7+5;
int n,k;
int cnt=1;
int tree[M][2],num[M];
inline void insert(int x)
{
int pos=1;
for(int i=(1<<30);i;i>>=1)
{
bool opt=i&x;
if(!tree[pos][opt]) tree[pos][opt]=++cnt;
pos=tree[pos][opt];
num[pos]++;//建字典树
}
}
inline int find(int x)
{
int pos=1,res=0;
for(int i=(1<<30);i;i>>=1)
{
bool opt1=i&x,opt2=i&k;
if(opt2) pos=tree[pos][opt1^1];//如果这一位上k是1，那么无论怎样都不可能比1大，所以去1儿子找
else//如果这意味上k是0，那么我们可以将这一位上二进制是1的数加上，然后去0儿子。
{
res+=num[tree[pos][opt1^1]];
pos=tree[pos][opt1];
}
}
res+=num[pos];
return res;
}
signed main()
{
cin>>n>>k;int x,pre=0;
long long ans=0;
for(int i=1;i<=n;i++)
{
insert(pre);//将上一个点的异或前缀和插入，当前点要找的答案都在前面。
cin>>x,pre^=x;//每个点的异或前缀和
ans+=find(pre);//累加答案
}
cout<<ans<<endl;
return 0;
}
CF706D Vasiliy's Multiset
有q次操作和一个集合A，开始时集合中只有一个数0，下面有三种类型的操作：
- x 把x插入集合A
-
x 把x从集合A中删去，保证x已存在于集合A中
-
? x 给一个数x在集合A中找一个y使得x^y最大，并求出这个值
数据范围:\(1\leq q\leq 200000\) \(1\leq x_i\leq10^9\)
这不就是板子题。对于插入和删除开头都已经介绍了，对于操作建好字典树，查询的时候就贪心的走与二进制下与自己不同的儿子，累加答案，最后输出就可以了。
注意的是，一开始集合有一个0，所以你要先把0插入字典树中（我做的时候没看到，疑惑了半天）。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=3e6+5;
int q;
int cnt=1;
int tree[M][2],num[M],val[M];
inline void insert(int x,int k)
{
int pos=1;
for(int i=(1<<30);i;i>>=1)
{
bool opt=i&x;
if(!tree[pos][opt]) tree[pos][opt]=++cnt;
pos=tree[pos][opt];
num[pos]+=k;//加上权值，插入遍历数就++，否则就--
}
val[pos]=x;//记录一下这个点代表的真实值（其实你可以不用这么写，find的时候边find边累加答案）
}
inline int find(int x)
{
int res=0,pos=1;
for(int i=(1<<30);i;i>>=1)
{
bool opt=x&i;
if(tree[pos][!opt]&&num[tree[pos][!opt]])//如果存在与自己相反的点，并且没有被删（还有数遍历了这个点）
{
pos=tree[pos][!opt];
}
else pos=tree[pos][opt];
}
return x^val[pos];
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>q;char opt;int x;
insert(0,1);
while(q--)
{
cin>>opt>>x;
if(opt=='+') insert(x,1);
else if(opt=='-') insert(x,-1);//插入的权值就是1，删除的权值就是-1。
else
{
cout<<find(x)<<"\n";
}
}
return 0;
}
CF817E Choosing The Commander
和上几道题的思路是一样的吧，首先插入和删除操作都与上一道题一样，加一个权值就可以了，之前那道好像是要让值大于\(k\)，而这道题是让值小于一个数，那么每一次当前位上如果为0，那么就没有比自己小的，调到0儿子上面，但如果这一位上是1，比自己值小的加上。
代码：
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cstdio>
#define int long long
using namespace std;
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x>y?y:x;}
const int M=2e6+5;
int n;
int cnt=1;
int tree[M][3],res[M];
inline void insert(int x,int k)
{
int pos=1;
for(int i=(1<<30);i;i>>=1)
{
bool num=i&x;
if(!tree[pos][num]) tree[pos][num]=++cnt;
pos=tree[pos][num];
res[pos]+=k;
}
}
inline int query(int p,int limit)
{
int pos=1,sum=0;
for(int i=(1<<30);i;i>>=1)
{
bool x=p&i,y=limit&i;
if(y)//如果当前位为1
{
sum+=res[tree[pos][x]],pos=tree[pos][x^1];//加上
}
else pos=tree[pos][x];
}
return sum;
}
signed main()
{
//ios::sync_with_stdio(false);
//cin.tie(0);cout.tie(0);
cin>>n;int opt,x,y;
for(int i=1;i<=n;i++)
{
cin>>opt>>x;
if(opt==1)
{
insert(x,1);
}
else if(opt==2)
{
insert(x,-1);
}//插入和删除都加上权值
else
{
cin>>y;
cout<<query(x,y)<<"\n";
}
}
return 0;
}