1. Trie字符串统计 （Trie树）
Trie树作用：高效地存储和查找字符串集合的数据结构。
维护一个字符串集合，支持两种操作：
（1）I x 向集合中插入一个字符串 x ；
（2）Q x 询问一个字符串在集合中出现了多少次。
共有 N 个操作，输入的字符串总长度不超过 10^5 ，字符串仅包含小写英文字母。
输入格式
第一行包含整数 N ，表示操作数。 接下来 N 行，每行包含一个操作指令，
指令为 I x 或 Q x 中的一种。
输出格式
对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。
每个结果占一行。
数据范围
1≤N≤2?10^4
输入样例：
5
I abc
Q abc
Q ab
I ab
Q ab
输出样例：
1
0
1
#include<iostream>
using namespace std;
const int N = 100010;
int son[N][26],cnt[N],idx = 0;
// 因为有26个字母，所以每个节点的子节点最多有26个
// cnt 存的是以当前这个点结尾的点有多少个
// idx 存当前用到的是哪个下标
// 下标是0的点既是根节点，又是空节点（如果一个节点没有子节点，我们会让它指向 0 ）
char str[N];
void insert(char str[])
{
int p = 0;
for(int i = 0;str[i];i++) // c++ 字符串的结尾是 "/0"
{
int u = str[i] - 'a'; // 当前节点子节点的编号 ，把 a ~ z 映射成 0 ~ 25
if(!son[p][u]) // 如果 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];
}
int main(void)
{
int n;
scanf("%d",&n);
while(n--)
{
char op[2];
// 这里 op 是长度为2的数组，因为 op 和 str 之间有个空格
scanf("%s%s",op,str);
if(op[0] == 'I')
{
insert(str);
}
else if(op[0] == 'Q')
{
printf("%d\n",query(str));
}
}
return 0;
}
2. 合并集合（并查集）
并查集作用：快速处理
（1）将两个集合合并；
（2）询问两个元素是否在一个集合当中。
近乎O(1)
并查集基本原理：用一棵树来维护一个集合（一个点代表一个元素），每个集合根节点的编号就是当前集合的编号；对于树上的每一个点x都存储一下父节点 p[x] ；查找一个元素所在的集合，只需不断往上找父节点，直到找到根节点，根节点的编号就是当前元素所属集合的编号；
（1）如何判断树根：if( p[x] == x )
（2）如何求 x 的集合编号：while( p[x] != x) x = p[x]; 最终 x 的值就是结合编号；
（3）如何合并两个集合：比如合并集合1和2，直接把1这整棵树插到2上。
px 是x的集合编号，py 是y的集合编号，p[x] = py;
并查集优化：查找根节点的优化（路径压缩优化）
比如现在查找1的根节点，查完就把集合的形式从左边变成右边的，这样之后查找节点1的时候，时间复杂度就变成O(1)了
一共有 n 个数，编号是 1～n ，最开始每个数各自在一个集合中。
现在要进行 m 个操作，操作共有两种：
（1）M a b，将编号为 a 和 b的两个数所在的集合合并，
如果两个数已经在同一个集合中，则忽略这个操作；
（2）Q a b，询问编号为 a 和 b 的两个数是否在同一个集合中；
输入格式
第一行输入整数 n 和 m 。接下来 m 行，每行包含一个操作指令，
指令为 M a b 或 Q a b 中的一种。
输出格式
对于每个询问指令 Q a b，都要输出一个结果，如果 a 和 b 在同一集合内，则输出 Yes，
否则输出 No。
每个结果占一行。
数据范围
1≤n,m≤10^5
输入样例：
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4
输出样例：
Yes
No
Yes
p[find(a)] = find(b);
#include<iostream>
using namespace std;
const int N = 100010;
int p[N];
// p[x]：存储数字x的父节点下标
int n,m;
int find(int x) // 返回 x 的祖宗节点 + 路径压缩操作
{
if(p[x] != x) p[x] = find(p[x]);
// 如果 x 的父节点不是祖宗节点，那么就让 x 的父节点 等于 x 的父节点的祖宗节点
//（往上走了一层）
return p[x]; // 如果 x 的父节点是祖宗节点，那么就直接返回x的父节点
}
int main(void)
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++) p[i] = i;
while(m--)
{
char op[2];
int a,b;
scanf("%s%d%d",op,&a,&b);
if(op[0] == 'M')
{
p[find(a)] = find(b);
// 让 a 的祖宗节点的父节点 等于 b 的祖宗节点（就是把a所在的树插到 b 所在树的祖宗节点的下边）
}
else
{
if(find(a) == find(b))
printf("Yes\n");
else printf("No\n");
}
}
return 0;
}
3. 连通块中点的数量 （并查集，维护集合中元素的数量）
给定一个包含 n 个点（编号为 1～n）的无向图，初始时图中没有边。
现在要进行 m 个操作，操作共有三种：
（1）C a b，在点 a 和点 b 之间连一条边，a 和 b 可能相等；
（2）Q1 a b，询问点 a 和点 b 是否在同一个连通块中，a 和 b 可能相等；
（3）Q2 a，询问点 a 所在连通块中点的数量；
输入格式
第一行输入整数 n 和 m。
接下来 m 行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。
输出格式
对于每个询问指令 Q1 a b，如果 a 和 b 在同一个连通块中，则输出 Yes，否则输出 No。
对于每个询问指令 Q2 a，输出一个整数表示点 a 所在连通块中点的数量
每个结果占一行。
数据范围
1≤n,m≤10^5
输入样例：
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5
输出样例：
Yes
2
3
#include<iostream>
using namespace std;
const int N = 100010;
int p[N],sum[N];
// p[x]：存储数字x的父节点下标
// sum[x]: x 是头结点的下标，sum[x] 是该连通块中点的数量
int n,m;
int find(int x) // 返回 x 的祖宗节点 + 路径压缩操作
{
if(p[x] != x) p[x] = find(p[x]); // 如果 x 的父节点不是祖宗节点，那么就让 x 的父节点 等于 x 的父节点的祖宗节点
return p[x]; // 如果 x 的父节点是祖宗节点，那么就直接返回x的父节点
}
int main(void)
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
{
p[i] = i;
sum[i] = 1;
}
while(m--)
{
char op[2];
int a,b;
scanf("%s",op);
if(op[0] == 'C')
{
scanf("%d%d",&a,&b);
if(find(a) != find(b)) // 如果a,b不在同一个联通块中再合并
{
sum[find(b)] += sum[find(a)];
p[find(a)] = find(b);
// 让 a 的祖宗节点的父节点 等于 b 的祖宗节点
//（就是把a所在的树插到 b 所在树的祖宗节点的下边）
}
}
else if(op[1] == '1') // Q1
{
scanf("%d%d",&a,&b);
if(a == b)
printf("Yes\n");
else if(find(a) == find(b))
printf("Yes\n");
else printf("No\n");
}
else // Q2
{
scanf("%d",&a);
printf("%d\n",sum[find(a)]);
}
}
return 0;
}
4. 堆排序
如何手写一个堆？
堆是维护一个数据集合。
-
堆的操作：
（1）插入一个数；
（2）求集合当中的最小值；
（3）删除最小值；
（4）删除任意一个元素；
（5）修改任意一个元素。 -
堆的基本结构：堆是一个完全二叉树；
完全二叉树：若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树。
以小跟堆为例，小根堆：每个点的值都 小于等于 左右两个儿子的值；根节点的值就是整个树（堆）的最小的值。 -
堆的存储：
用一维数组存储。
-
小根堆的两个基本操作：down、up
时间复杂度都是 O(logn)
堆的5个操作都可以down、up为基础完成；
一维数组heap表示堆（下标一定要从1开始，左右儿子的下标就好表示），size表示堆的大小,
（1）插入一个数x：
在数组的最后一个位置插入x，在把这个数不断往上移，直到移动到合适的位置。
heap[++size] = z;
up(size);
（2）求集合当中的最小值：
heap[1];
（3）删除最小值：
把最后一个元素覆盖掉堆顶元素，size - -，再down一遍;
heap[1] = heap[size - -];
down[1];
（4）删除任意一个元素；
假如删除下标是k的点，与删除最小值类似；
因为不知道你要删除的heap[k]，与heap[size]谁大谁小，所以先down一遍，再up一遍。
heap[k] = heap[size - -];
down[k];
up[k];
（5）修改任意一个元素：
与（4）类似
heap[k] = x;
down[k];
up[k];
输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。
输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。
输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。
数据范围
1≤m≤n≤10^5 ，1≤数列中元素≤10^9
输入样例：
5 3
4 5 1 3 2
输出样例：
1 2 3
#include<iostream>
using namespace std;
const int N = 100010;
int h[N];
int Size = 0,n,m;
void down(int k) // k 是节点的下标
{
int t = k; // t 存的是 要down的节点k 和 k的左右儿子 2*k, 2*k + 1 中最小的
if(2*k <= Size && h[2*k] < h[t]) t = 2*k;
if(2*k + 1 <= Size && h[2*k + 1] < h[t]) t = 2*k + 1;
if(t != k) // k 在左右儿子中不是最小的，就要交换
{
swap(h[k],h[t]);
down(t);
}
}
int main(void)
{
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
scanf("%d",&h[i]);
Size = n;
// 把一个数组建成堆
// O(n) 建堆方式：从 n/2 down 到 1
for(int i = n/2;i;i--)
down(i);
for(int i = 0;i < m;i++)
{
printf("%d ",h[1]);
h[1] = h[Size--];
down(1);
}
return 0;
}
5. 模拟堆
维护一个集合，初始时集合为空，支持如下几种操作：
（1）I x，插入一个数 x；
（2）PM，输出当前集合中的最小值；
（3）DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
（4）D k，删除第 k 个插入的数；
（5）C k x，修改第 k 个插入的数，将其变为 x；
现在要进行 N 次操作，对于所有第 2 个操作，输出当前集合的最小值。
输入格式
第一行包含整数 N。接下来 N 行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
输出格式
对于每个输出指令 PM，输出一个结果，表示当前集合中的最小值。
每个结果占一行。
数据范围
1≤N≤10^5
?10^9≤x≤10^9
数据保证合法。
输入样例：
8
I -10
PM
I -10
D 1
C 2 8
I 6
PM
DM
输出样例：
-10
6
#include<iostream>
#include<string.h>
using namespace std;
const int N = 100010;
int h[N];
int Size = 0,n;
int ph[N],hp[N];
// ph[x] 是 第 x 个插入的数在堆中的下标 ，hp[x] ：堆中的下标为 x 的点是第几个插入的
// 例如： ph[j] = k;hp[k] = j
void heap_swap(int a,int b) // a 和 b 是堆中节点的下标
{
/*
比如：a,b; h[a] = 1,h[b] = 2; ph[i] = a,ph[j] = b; hp[a] = i,hp[b] = j;
现在要让 下标为a,b节点中的值做交换
即： h[a] = 2,h[b] = 1; ph[i] = b,ph[j] = a; hp[a] = j,hp[b] = i;
*/
swap(h[a],h[b]); // h[a] = 2,h[b] = 1;
swap(ph[hp[a]],ph[hp[b]]); // ph[i] = b,ph[j] = a;
swap(hp[a],hp[b]); // hp[a] = j,hp[b] = i;
}
void down(int k) // k 是节点的下标
{
int t = k; // t 存的是 要down的节点k 和 k的左右儿子 2*k, 2*k + 1 中最小的
if(2*k <= Size && h[2*k] < h[t]) t = 2*k;
if(2*k + 1 <= Size && h[2*k + 1] < h[t]) t = 2*k + 1;
if(t != k) // k 在左右儿子中不是最小的，就要交换
{
// swap(h[k],h[t]);
heap_swap(k,t);
down(t);
}
}
void up(int k)
{
// if(k/2 && h[k] < h[k/2])
// {
// heap_swap(k,k/2);
// up(k/2);
// } 两种写法都可以
while(k/2 && h[k] < h[k/2])
{
heap_swap(k,k/2);
k /= 2;
}
}
int main(void)
{
int m = 0; // m 是当前插入操作的次数
scanf("%d",&n);
while(n--)
{
char op[3];
scanf("%s",op);
if(!strcmp(op,"I")) // 插入
{
int x;
scanf("%d",&x);
h[++Size] = x;
m++;
ph[m] = Size;
hp[Size] = m;
up(Size);
}
else if(!strcmp(op,"PM")) // 输出当前集合的最小值
{
printf("%d\n",h[1]);
}
else if(!strcmp(op,"DM")) // 删除最小值
{
heap_swap(1,Size);
Size--;
down(1);
}
else if(!strcmp(op,"D")) // 删除第 k 个插入的数
{
int k;
scanf("%d",&k);
k = ph[k];
heap_swap(k,Size);
Size--;
down(k);
up(k);
}
else // 修改第 k 个插入的数
{
int k,x;
scanf("%d%d",&k,&x);
k = ph[k];
h[k] = x;
down(k);
up(k);
}
}
return 0;
}