XCPC第五站！Trie树+并查集+堆，字符串和数字，你想要的全都有！ _并查集

一.Trie树
1.存储
Trie树是一种用于高效存储和查找字符串的数据结构。它有一个根节点，遇到一个字符时，首先查找根节点（或父节点）的子节点中有无该字符。若有，则往下走；若无，则创建。例如：
注意4的创建。首先对于b ，它已经是根节点的一个子节点，无需重复创建；对于c同理。而对于f ， c的已有子节点中没有f ，故创建一个；对于p、o同理。一般来说，我们会在单词的结尾打上一个标记表示结束（图中星号）。
代码实现：
注意，要理解下面两个数组的含义，我们必须先知道，在这个算法中，我们把a-z这26个字母依次映射到0-25这26个数字。那么， son[x1][x2]表示Trie树的第x1个父节点的x2位置的值（不管情况如何，我们总是给每个父节点都虚拟出26个子节点。如果该子节点的编号对应的字母确实是字符串中的下一个字母，那么就给该子节点赋值为++idx ，否则为默认值0 。那么到最后， son[x1][x2]的值如果是0 ，表示这一层没有出现x2对应的字母；若为非零，则出现了x2对应的字母）， cnt[x3]表示以x3作为结尾编号的字符串条数，由于先后出现的相同字符串会有相同编号，因此它可以用于统计字符串条数。idx表示我们已经用到的下标，即：当前字母出现的位置顺序。如果先后插入相同的字符，例如cdm,ce,cdm ，那么在第二次插入cdm时idx不会发生变化，当p往下走时最后会得到跟第一次插入cdm时最后p的值，那么cnt在相同的位置加一，就实现计算字符串的统计条数加一了。
const int N = 1e5+10;int son[N][26],cnt[N],idx;void Insert(char str[]){int p = 0;//从0开始向下走for(int i = 0;str[i];i++){int u = str[i] - 'a';//获取str[i]映射后的像if(!son[p][u]) son[p][u] = ++idx;p = son[p][u];}cnt[p]++;}
2.查找
比如说我们想查找abef ，只需要从上往下遍历，找到结束的星号标志即可。若我们查找一个不存在的单词，例如mpsq ，它一定会从某个节点开始找不到下一个节点。还有一种情况是查找的单词比已有的单词要短，例如bcee ，那么虽然可以走到第二个e ，但是第二个e处没有结束标志，所以这个单词不存在。
问题：既然我们已经一一检查给出的字符串的字母与已有字符串字母的吻合程度，为什么我们仍然需要cnt数组呢？这是为了控制长度。还是上面那个依次插入cdm,cpe,cdm的例子，如果不加cnt数组，那么当输入cd这个部分组，程序也会认为它出现过，但实际上这条字符串不存在！
int query(char str[]){int p = 0;for(int i = 0;str[i];i++){int u = str[i] - 'a';//若son[p][u]=0 ，说明这个位置对应的字母没出现if(!son[p][u]) return 0;p = son[p][u];}return cnt[p];
二.并查集
并查集支持快速实现以下两个操作：（1）判断两个元素是否属于同一个集合；（2）合并两个区间。我们可以想想，这两个需求如何暴力实现呢？我们可以维护数组，它的第k个位置存储的是k元素属于的集合。那么对于一，只需要判断是否有[x] == [y]即可。但是对于（2），例如把新几何看作集合A的扩充，就必须要全部修改数组中原本是B的值，这样的时间复杂度是很大的。为了优化问题，我们可以利用并查集。我们用树去表示集合，树的根节点的编号就是该集合的编号。每个节点存储它的父节点的编号。图例如下：