Trie 树
用来高效的快速存储和查找字符串集合的数据结构
如存储：abcdef,abdef,aced,...
从根节点开始存储，从前往后存储，看是否有a，没有就创建，依次存储。
一般在最后一个字符打个标记，意思就是当前字符结尾有个单词。
对于查找，要找aced
就从根节点看，如果走到结尾且有标记，就是存在，没有就不存在。
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的字符串数量// 插入一个字符串
void insert(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx;
p = son[p][u];
}
cnt[p] ++ ;
}// 查询字符串出现的次数
int query(char *str)
{
int p = 0;
for (int i = 0; str[i]; i ++ )
{
int u = str[i] - 'a';
if (!son[p][u]) return 0;
p = son[p][u];
}
return cnt[p];
//Trie树快速存储字符集合和快速查询字符集合
#include <iostream>
using namespace std;
const int N = 100010;
//son[][]存储子节点的位置，也存储第几个结点（idx的值），分支最多26条；
//cnt[p]存储以p节点结尾的字符串个数（同时也起标记作用）
//idx表示当前要插入的节点是第几个,每创建一个节点值+1
int son[N][26], cnt[N], idx;
char str[N];
void insert(char *str)
{
int p = 0; //类似指针，指向当前节点
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a'; //将字母转化为数字
if(!son[p][u]) son[p][u] = ++idx; //该节点不存在，创建节点
p = son[p][u]; //使“p指针”指向下一个节点
}
cnt[p]++; //结束时的标记，也是记录以此节点结束的字符串个数
}
int query(char *str)
{
int p = 0;
for(int i = 0; str[i]; i++)
{
int u = str[i] - 'a';
if(!son[p][u]) return 0; //该节点不存在，即该字符串不存在
p = son[p][u];
}
return cnt[p]; //返回字符串出现的次数
}
int main()
{
int m;
cin >> m;
while(m--)
{
char op[2];
cin>>op>>str;
if(*op == 'I') insert(str);
else cout<<query(str)<<endl;
//改成char op; op == 'I'也行
}
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100010,M=31*N;
int a[N];
int son[M][2],idx;
//M代表一个数字串二进制可以到多长
void insert(int x)
{
int p=0; //根节点
for(int i=30;i>=0;i--)
{
int u=x>>i&1; //取x的二进制中的第i位数字
if(!son[p][u]) son[p][u]=++idx; ///如果插入中发现没有该子节点,开出这条路
p=son[p][u]; //指针指向下一层
}
}
//异或运算相同为0不同为1
int search(int x)
{
int p=0;int res=0;
for(int i=30;i>=0;i--)
{
int u=x>>i&1; //从最大位开始找
if(son[p][!u]) //如果当前层有对应的不相同的数，res左移一位并加一
{
p=son[p][!u];
res=res*2+1;
//*2相当左移一位 然后如果找到对应位上不同的数res+1
}
else //如果当前层有对应的相同的数，res左移一位并加零 //刚开始找0的时候是一样的所以+0 到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
{
p=son[p][u];
res=res*2+0;
}
}
return res;
}
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>a[i];
insert(a[i]);
}
int res=0;
for(int i=0;i<n;i++)
{
res=max(res,search(a[i])); ///search(a[i])查找的是a[i]值的最大与或值
}
cout<<res<<endl;
return 0;
}
并查集（常考）
常见操作：
1.将两个集合合并
2.询问两个元素是否在一个集合当中近乎O(1)
基本原理：每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储
它的父节点，p[x]表示x的父节点
问题1：如何判断树根：if(p[x]==x)
问题2：如何求x的集合编号：while(p[x]!=x)x = p[x]
问题3：如何合并两个集合：px是x的集合编号，py是y的集合编号。p[x]=y(1)朴素并查集：
int p[N]; //存储每个点的祖宗节点
// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;// 合并a和b所在的两个集合：
p[find(a)] = find(b);
(2)维护size的并查集：int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
size[i] = 1;
}// 合并a和b所在的两个集合：
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
(3)维护到祖宗节点距离的并查集：int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离// 返回x的祖宗节点
int find(int x)
{
if (p[x] != x)
{
int u = find(p[x]);
d[x] += d[p[x]];
p[x] = u;
}
return p[x];
}// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ )
{
p[i] = i;
d[i] = 0;
}// 合并a和b所在的两个集合：
p[find(a)] = find(b);
d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量
#include<iostream>
using namespace std;
const int N=100010;
int p[N];//存储父节点的数组，p[x]=y表示x的父节点为y
//找根节点（集合编号）的函数 ，查找过一遍后所有经过的x的父节点的父节点都会变为集合编号以降低时间复杂度
int find(int x)
{
if(p[x]!=x) p[x]=find(p[x]);//只有根节点的p[x]=x，所以要一直找直到找到根节点
return p[x];//找到了便返回根节点的值
}
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++) p[i]=i;//刚开始每个数自成一个集合，每个数自己为根节点
while(m--)
{
char op;
int a,b;
cin>>op>>a>>b;
if(op=='M') p[find(a)]=find(b);//集合合并操作(把a合并到b集合)
else{
if(find(a)==find(b)) cout<<"Yes"<<endl;//如果根节点一样,就输出yes
else cout<<"No"<<endl;
}
}
return 0;
}
2.连通块中的点的数量
#include <iostream>
using namespace std;
const int N = 100010;
//只有根节点的size能代表集合的节点数量，所以size中括号里一般都要有find函数先找出根节点
int p[N],size[N];
int find(int x){
if(p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main(){
int n,m;
cin>>n>>m;
for(int i = 1; i <= n;i++){
p[i] = i;
size[i] = 1;
}
while(m--){
string op;
int a,b;
cin>>op;
if(op == "C"){
cin>>a>>b;
if(find(a) == find(b)) continue;
size[find(b)]+=size[find(a)];//先加size
p[find(a)] = find(b);//再连
}
else if(op == "Q1"){
cin>>a>>b;
if(find(a) == find(b)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
else{
cin>>a;
cout<<size[find(a)]<<endl;
}
}
return 0;
}
#include <iostream>
using namespace std;
const int N = 50010;
//d[x]表示x到父节点的距离，p[x]表示x的父节点
int p[N],d[N];/*int find(int x)函数两个作作用：
1.使根节点成为x的父节点，并返回x的根节点
2.将d[x]即x到父节点的距离变为x到根节点的距离*/
int find(int x){
if(p[x]!=x){
int t = find(p[x]);
//find完之后，p[x]直接连接根节点了，d[p[x]]是x的父节点p[x]到根节点的距离，即：
/*x到根节点的距离 = x到父节点的距离 + 父节点到根节点的距离
d[x] = d[x] + d[p[x]];*/
//如果不先find那么d[p[x]]就是x的父节点p[x]到父节点的距离，就不一定是p[x]到根节点的距离，即：
/*x到根节点的距离 = x到父节点的距离 + 父节点到父节点的距离
d[x] = d[x] + d[p[x]];*/
//因为find完之后p[x]的子节点就是x，父节点就是根节点0
d[x] += d[p[x]];//这步进行完d[x]是没错的了，就是x到根节点的总距离
//这步再把x的父节点改为根节点，取代之前x和根节点之间的父节点，这样x和根节点就是距离也没错也是直接连接的了
p[x] = t;
}
return p[x];
}int main(){
int n,m;
cin>>n>>m;
for(int i = 1; i<= n; i++) p[i] = i;
int res = 0;
while(m--){
int t,x,y;
cin>>t>>x>>y;
//1.X或Y比N大，假话
if( x>n || y>n) res++;
else{
//为什么px一定要等于py也就是x和y为什么一定要在一个集合内呢
//如果不在同一个集合内，就无法正确地模拟食物链的关系。因为在同一个集合内，才能通过距离数组 d 来维护元素之间的食物链关系，并查集核心思想也是要在一个集合内
int px = find(x),py = find(y);
if(t == 1){//此时t == 1，表示已经告诉我们x和y是同类
//在一个树上并且x和y不是同类即(d[x] - d[y])%3余1或余2，假话+1
if(px == py && (d[x] - d[y])%3) res++;//注意此时已经经过了find函数所以d[x]是x到根节点的距离
else if(px != py){//当x和y不在一个集合内时把他们合并，注意if条件不要漏，不要直接else，是只有x和y不在一个集合时才要合并
p[px] = py;
d[px] = d[y] - d[x];//1式
}
}
else{//此时告诉我们x吃y
//在一个树上并且x不吃y即(d[x] - d[y] - 1)%3不等于0，假话+1
if(px == py && (d[x] - d[y] - 1)%3) res++;
else if(px != py){//当x和y不在一个集合内时把他们合并，注意if条件不要漏，不要直接else，是只有x和y不在一个集合时才要合并
p[px] = py;
d[px] = d[y] +1-d[x];//2式，1式和2式具体思路看图
}
}
}
}
cout<<res<<endl;
return 0;
//简洁版
#include <iostream>
using namespace std;
const int N = 50010;
int p[N],d[N];
int find(int x){
if(p[x] != x){
int t= find(p[x]);
d[x]+=d[p[x]];
p[x] = t;
}
return p[x];
}
int main(){
int n,m;
cin>>n>>m;
for(int i = 1; i <= n ; i++) p[i] = i;
int res = 0;
while(m--){
int op,x,y;
cin>>op>>x>>y;
if(x > n ||y > n) res++;
else{
int px = find(x),py = find(y);
if(op == 1){
if( px == py && (d[x]-d[y])%3) res++;
else if(px != py){
p[px] = py;
d[px] = d[y]-d[x];
}
}
else{
if( px == py && (d[x]-d[y]-1)%3) res++;
else if(px != py){
p[px] = py;
d[px] = d[y]-d[x] + 1;
}
}
}
}
cout<<res<<endl;
return 0;
}
堆
堆是一颗完全二叉树（除了最后一层节点，其他都是满的，最后一层也是从左到右排的）
根节点是最小值，其他父节点小于等于左右两节点
//h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
//ph存储堆中的下标，ph是插入顺序数组
//hp存储元素的插入顺序，h存储的是元素的值，h和hp都是堆数组
//se表示size，插入点在堆中的下标，因为size是关键字所以用se代替
int h[N], ph[N], hp[N], se;void heap_swap(int a, int b){
//下面三个交换只要保证 swap(hp[a], hp[b])在swap(ph[hp[a]], ph[hp[b]])后面就行，其他无所谓
swap(ph[hp[a]], ph[hp[b]]);//交换堆中的下标
/*上面这一步是交换堆中的下标，为什么不能直接交换a和b：首先，是因为交换a和b会影响后面两个交换。
但是这么交换的实际意思是：只是交换了ph数组中对应a和b的那个值，所以这样既正确修改了映射，又没影响到a和b*/
swap(hp[a], hp[b]);//交换插入顺序
swap(h[a], h[b]);//交换值
}void down(int r){
int t=r;
if (r * 2 <= se && h[r * 2]< h[t]) t = r * 2;
if (r *2 + 1 <= se && h[r * 2 + 1]< h[t]) t = r * 2 + 1;
if (r != t){
heap_swap(r, t);
down(t);
}
}
void up(int u){
//只要保证比根结点的值大就行了
while (u / 2 && h[u] < h[u / 2]){//此节点索引为u，根节点为u/2
heap_swap(u /2, u);
u /= 2;//下次循环再跟根节点的根节点比...以此类推
}
}// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);
1.堆排序
//小顶堆：1.根节点小于等于两个子节点；2.假如根节点的索引为x，则左子节点索引为2x，右为2x+1；3.堆在几何意义上是一颗完全二叉树
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
int h[N], se;//se是数组长度size
int n, m;
void down(int r)
{
int t = r;//t是最小值
//一定要用h[t]比较，如上图
if (2 * r <= se && h[2 * r] < h[t])//先跟左子节点比
t = 2 * r;
if (2 * r + 1 <= se && h[2 * r + 1] < h[t])//再跟右子节点比
t = 2 * r + 1;
if (r != t)
{
swap(h[r], h[t]);//跟最后比出来的最小的那个结点换值
/*为什么要在if (r != t)里面down(t)，而不是这个函数的最后或其他位置：因为当r == t时，根节点就是最小值，也就是之前t没被赋索引；如果t被赋索引了，此时t是两个子节点中最小的那一个，因为这个最小的值被这个小子树的根节点换走了，所以此时这个子节点的值就是根结点的值，是比原来的值更大的，所以以这个子节点为根节点的子树可能就不满足小顶堆了，所以要再down一下，同理，到了以这个子节点为根节点的小子树如果也是这种情况也要继续再down，以此类推。*/
down(t);
}
}
int main()
{
cin >> n >> m;
se = n;
for (int i = 1; i <= n; i++) cin>>h[i];
//使数组成为堆，即初始化堆
for (int i = n / 2; i > 0; i--) down(i);
while (m--)
{
cout << h[1] << " ";
h[1] = h[se--];//删除
down(1);
}
return 0;
}
2.模拟堆
#include<iostream>
#include<algorithm>
using namespace std;
const int N = 100010;
//ph存储堆中的下标，ph是插入顺序数组
//hp存储元素的插入顺序，h存储的是元素的值，h和hp都是堆数组
//se表示size，插入点在堆中的下标
int h[N], ph[N], hp[N], se;
//参数是堆中的下标
void heap_swap(int a, int b){
swap(ph[hp[a]], ph[hp[b]]);//交换堆中的下标
/*上面这一步是交换堆中的下标，为什么不能直接交换a和b：首先，是因为交换a和b会影响后面两个交换。
但是这么交换的实际意思是：只是交换了ph数组中对应a和b的那个值，所以这样既正确修改了映射，又没影响到a和b*/
swap(hp[a], hp[b]);//交换插入顺序
swap(h[a], h[b]);//交换值
}
void down(int r){
int t=r;
if (r * 2 <= se && h[r * 2]< h[t]) t = r * 2;
if (r *2 + 1 <= se && h[r * 2 + 1]< h[t]) t = r * 2 + 1;
if (r != t){
heap_swap(r, t);
down(t);
}
}
void up(int u){
//只要保证比根结点的值大就行了
while (u / 2 && h[u] < h[u / 2]){//此节点索引为u，根节点为u/2
heap_swap(u /2, u);
u /= 2;//下次循环再跟根节点的根节点比...以此类推
}
}
int main(){
int m;
cin>>m;
int n = 0;//n表示插入的第几个数
while(m--)
{
string op;
int k,x;
cin>>op;
//1.插入一个数x
if(op=="I")
{
cin>>x;
n++;
se++;//se表示在堆中的下标
h[se]=x;
hp[se]=n;
ph[hp[se]]=se;
up(se);//新插入的值浮上去，注意这点易忘
}
//2.输出当前集合中的最小值
else if(op=="PM") cout<<h[1]<<endl;
//3.删除当前集合中的最小值
else if(op=="DM")
{
heap_swap(1,se);//删除操作都是通过交换实现，删除完要进行沉或者浮
se--;
down(1);
}
//4.删除第k个插入的数
else if(op=="D")
{
cin>>k;
int u = ph[k];
heap_swap(u,se);//删除操作都是通过交换实现，删除完要进行沉或者浮
se--;
up(u);
down(u);
}
//5.修改第 k个插入的数，将其变为 x
else if(op=="C")
{
//ph[k]表示第k个数在堆中的下标
cin>>k>>x;
h[ph[k]]=x;
down(ph[k]);
up(ph[k]);
}
}
return 0;
}