第一章 KMP

一、KMP字符串

1. 题目描述

给定一个字符串 $S$，以及一个模式串 $P$，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 $P$ 在字符串 $S$ 中多次作为子串出现。

求出模式串 $P$ 在字符串 $S$ 中所有出现的位置的起始下标。

输入格式

第一行输入整数 $N$，表示字符串 $P$ 的长度。

第二行输入字符串 $P$。

第三行输入整数 $M$，表示字符串 $S$ 的长度。

第四行输入字符串 $S$。

输出格式

共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

数据范围

$1≤N≤10^5$
$1≤M≤10^6$

输入样例：

3
aba
5
ababa

输出样例：

0 2

---

2. 思路分析

求前缀数组，即 $next$ 数组，每一个子串都有一个固定的 $next$ 数组，它记录着字符串匹配过程中失配情况下可以向后多跳几个字符，其实也就是子串的前缀和后缀相同的最长长度。

如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示：

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
int ne[N]; //保存next数组
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1; //下标从1开始
    
    //求next数组
    //j表示匹配成功的长度，i表示p数组中下标，因为p数组的下标是从1开始的，只有1个时，j一定是0，所以i从2开始
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        //匹配不成功，则换到next数组
        while (j && p[i] != p[j + 1]) j = ne[j];
        //匹配成功的话，则j加1
        if (p[i] == p[j + 1]) j ++;
        //对应其下标
        ne[i] = j;
    }
    
    //j表示匹配成功的长度，因为刚开始还未开始匹配，所以长度是0
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        //如果匹配不成功，则切换j到next数组中的值
        while (j && s[i] != p[j + 1]) j = ne[j];
        //匹配成功，则j加1，继续后面的匹配
        if (s[i] == p[j + 1]) j ++;
        if (j == n)
        {
            //因为题目中下标从0开始所以是i - n，如果是从1开始则是i - n + 1
            printf("%d ", i - n);
            //继续切换j到next数组中值，继续匹配是否还能与后面的匹配成功
            j = ne[j];
        }
    }
    return 0;
}

---

第二章 字典树（Tire）

一、Tire字符串统计

1. 题目描述

维护一个字符串集合，支持两种操作：

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

---

2. 思路分析

Trie树中有个二维数组 son[N][26]，表示当前结点的儿子，如果没有的话，可以等于++idx。Trie树本质上是一颗多叉树，对于字母而言最多有26个子结点。所以这个数组包含了两条信息。

建字典树：
儿子数组 son[p][u] 存储节点 p 沿着 u 这条边走到的子节点。边为 26 个小写字母（a ~ z）对应的映射值 0 ~ 25，每个节点最多可以有26个分叉。
比如：son[1][0]=2表示1结点的一个值为a的子结点为结点2; 如果son[1][0] = 0，则意味着没有值为a子结点。这里的son[N][26]相当于链表中的ne[N]。

计数数组cnt[p] 存储以节点 p 结尾的单词的插入次数。

节点编号 idx 用来给节点编号。

1. 空 Tire 仅有一个根节点，编号为0；
2. 从根节点开始插，枚举字符串的每个字符，如果有儿子，则 p 指针走到儿子；如果没有儿子，则先创建儿子，p 指针再走到儿子；
3. 在单词结束点记录插入次数。

---

3. 代码实现

//Tire树快速存储字符集合和快速查询字符集合
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

// son[p][26]存储子节点的位置，分支最多26条
// cnt[] 存储以某节点为结尾的字符串个数（同时起标记作用）
// idx 表示当前要插入的节点是第几个，每创建一个节点值+1
int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str)
{
    int p = 0; //指针p，指向当前节点
    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 n;
    cin >> n;
    while (n --)
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}

---

二、最大异对

1. 题目描述

在给定的 $N$ 个整数 $A1，A2……AN$ 中选出两个进行 $xor$（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_1～A_N$。

输出格式

输出一个整数表示答案。

数据范围

$1≤N≤10^5$,
$0≤A_i<2^{31}$

输入样例：

3
1 2 3

输出样例：

3

---

2. 思路分析

异或： 如果a、b两个值不相同，则异或结果为1；如果a、b两个值相同，异或结果为0。

1. 将一个整数转化为一个32位的二进制数，也就是长度为32位的二进制字符串；
2. 从最高位开始检索，每次找与该位相反的数字，才能让异或最大，如果没有想反的数字，则选择相同的数字。
3. 返回最大的异或数。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

//M代表一个数字串二进制可以到多长
const int N = 100010, M = 3100010;

int n;
int a[N], son[M][2], idx;

void insert(int x)
{
    int p = 0; //根节点
    for (int i = 30; i >= 0; i --) 
    {
        int u = x >> i & 1; //x >> i:取二进制数x的第i位; x >> i & 1:二进制数x的第i位是0还是1
        if (!son[p][u]) son[p][u] = ++idx; //不存在该子节点，创建该子节点
        p = son[p][u]; //p指针指向子节点
    }
}

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i --) //从最大数开始找
    {
        int u = x >> i & 1;
        //如果当前层有对应的不相同的数
        if (son[p][!u])
        {
            res = res * 2 + 1; // 更新res的值，每次把旧值乘以2（这一步相当于左移一位）再加上当前值
            p = son[p][!u]; //p指针就指向不同数的地址
        }
        //如果当前层没有对应的不相同的数，则p指针指向相同的数的地址
        //刚开始找0的时候是一样的所以+0    到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
        // else
        // {
        //     res = res * 2 + 0; //对res的值没有改变，省略
        //     p = son[p][u];
        // }
        else p = son[p][u];
    }
    return res;
}

int main()
{
    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])); //查找a[i]最大的异或值
    cout << res << endl;
    
    return 0;
}

---

第三章 并查集

一、合并集合

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，都要输出一个结果，如果 aa 和 bb 在同一集合内，则输出 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

---

2. 思路分析

并查集是一种树形的数据结构。

并查集支持的两个操作：

• 合并： 将两个子集合并成一个集合。
• 查找： 确定某个元素在哪个集合。

带路径压缩的查找：
根节点是集合的代表，查找就是找到元素所在集合的根。

1. 如果父节点等于自己，则找到了根并返回；
2. 如果还没有找到根，则继续递归查找；
3. 在返回的路上，顺带修改各节点的父节点为根。

合并：
把一个集合的根指向另一个集合的根。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int p[N];

// 返回x的祖先节点 + 路径压缩
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;
    
    while (m --)
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        //合并：把一个集合的根指向另一个集合的根
        if (*op == 'M') p[find(a)] = find(b); 
        else
        {
            //若两个数的父节点一样，则在同一个集合
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

---

二、连通块中点的数量

1. 题目描述

给定一个包含 n 个点（编号为 $1∼n$）的无向图，初始时图中没有边。

现在要进行 m 个操作，操作共有三种：

1. C a b，在点 aa 和点 bb 之间连一条边，a 和 b 可能相等；
2. Q1 a b，询问点 aa 和点 bb 是否在同一个连通块中，a 和 b 可能相等；
3. Q2 a，询问点 aa 所在连通块中点的数量；

输入格式

第一行输入整数 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

---

2. 思路分析

1. 初始化：先设置每个节点的根节点为自己，刚开始是每个集合中点的数量为1；
2. 合并集合： 把一个集合的根指向另一个集合的根，并且把该集合中点的数量加入另一个集合中；
3. 查询：即判断两个集合的父节点是否一样。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N], cnt[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        p[i] = i;
        cnt[i] = 1;
    }
    
    while (m --)
    {
        string op;
        int a, b;
        cin >> op;
        
        if (op == "C")
        {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b)
            {
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if (op == "Q1")
        {
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }
    return 0;
}

---

三、食物链

待完善......

---

第四章 堆

一、堆排序

1. 题目描述

输入一个长度为 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

---

2. 思路分析

如何手写一个堆？

1. 插入一个数：heap[ ++ size] = x; up(size);
2. 求集合中的最小值： heap[1];
3. 删除最小值：heap[1] = heap[size]; size -- ;down(1);
4. 删除任意一个元素：heap[k] = heap[size]; size -- ;up(k); down(k);
5. 修改任意一个元素：heap[k] = x; up(k); down(k);

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
//h[i]表示第i个结点存储的值，i从1开始，2 * i是左子节点，2 * i + 1是右子节点
//cnt 既表示堆里存储的元素个数，又表示最后一个结点的下标
int h[N], cnt;

void down(int u)
{
    int t = u; //t存储三个结点中存在的最小的结点的下标，初始化为当前结点u
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; //左子节点存在并且小于当前结点，更新t的下标
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1; //右子节点存在并且小于当前结点，更新t的下标
    if (u != t) //如果t==u意味着不用变动，u就是三个结点中拥有最小值的结点下标，否则交换数值
    {
        swap(h[u], h[t]); 
        down(t); //交换数值后，t这个结点存储原本u的值，u存储存储t的值（三个数中的最小值）。u不用调整了，但t情况不明，可能需要调整。直到它比左右子节点都小。
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    cnt = n; //初始化cnt，表示堆中有多少个元素

    //把堆初始化成小根堆，从二叉树的倒数第二行开始，把数字大的下沉
    for (int i = n/2; i; i --) down(i);
    
    while (m --)
    {
        cout << h[1] << ' '; //输出堆顶（最小值）
        h[1] = h[cnt --]; ////删除堆顶（用最后一个数覆盖第一个数），并且长度减1
        down(1); //让覆盖好的值继续往下走
    }
    return 0;
}

---

二、模拟堆

1. 题目描述

维护一个集合，初始时集合为空，支持如下几种操作：

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

---

2. 思路分析

相关思路在以下的代码注释中。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int h[N]; //堆
int ph[N];//ph[k] = x:表示第k个插入的元素在树中存放的位置x
int hp[N];//hp[x] = k:表示树中位置x存放的是第k个插入的元素
int cnt;  //记录堆中当前数据的多少

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u *2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u /= 2;
    }
}

int main()
{
    int n, m = 0; //m是记录插入的数的个数，m是对应hp中应该存的值
    cin >> n;
    while (n --)
    {
        string op;
        int k, x;
        cin >> op;
        //插入一个数 x
        if (op == "I")
        {
            cin >> x;
            cnt ++;
            m ++;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        //输出当前集合中的最小值
        else if (op == "PM") cout << h[1] << endl;
        //删除当前集合中的最小值
        else if (op == "DM")
        {
            heap_swap(1, cnt);
            cnt --;
            down(1);
        }
        //删除第 k 个插入的数
        else if (op == "D")
        {
            cin >> k;
            k = ph[k]; //这里一定要用k=ph[k]保存第k个插入点的下标
            heap_swap(k, cnt); //因为在此处heap_swap操作后ph[k]的值已经发生
            cnt --;
            up(k); //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            down(k);
        }
        //修改第 k 个插入的数，将其变为 x
        else
        {
            cin >> k >> x;
            h[ph[k]] = x; //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个，所以可直接传入ph[k]作为参数
            up(ph[k]);
            down(ph[k]);
        }
    }
    return 0;
}

---

第五章 哈希表

一、模拟散列表

1. 题目描述

维护一个集合，支持如下几种操作：

1. I x，插入一个数 x；
2. Q x，询问数 x 是否在集合中出现过；

现在要进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果 xx 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

$1≤N≤10^5$
$−109≤x≤10^9$

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

---

2. 思路分析

散列表，也叫哈希表，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

开放寻址法：

• 如果要插入元素的映射位置没有元素，那么直接将该元素放在当前位置；
• 如果要插入元素的映射位置已经有了元素，那么就以此往后找，如果到了数组末尾还没有找到一个空的位置，就返回数组的头接着找；
• 为了防止整个数组都找了一遍还没有找到一个空的位置，数组大小通常要开数据范围的2~3倍。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 200003; //大于数据范围的第一个质数 
const int null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
    //t表示x映射到哈希表中的位置
    //+N再%N可以避免出现负数
    int t = (x % N + N) % N;
    //冲突情况:当前位置不为空，并且不为x
    while (h[t] != null && h[t] != x)
    {
        t ++;
        if (t == N) t = 0; //如果到了末尾就从头开始
    } //while一定会结束，因为我们的数组范围是开了2~3倍的，所以整个数组不会被完全使用，因此while不会无限循环
    
    //如果x存在哈希表中，返回的t是下标；如果x不在哈希表中，返回的t是x在哈希表中要存储的位置
    return t; 
}

int main()
{
    //把哈希表的值设置成一个不可能被映射到的数，以此来判断该位置有没有被使用
    memset(h, 0x3f, sizeof h);
    
    int n;
    cin >> n;
    while (n --)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

---

二、字符串哈希

1. 题目描述

给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 $l1,r1,l2,r2$，请你判断 $[l1,r1]$ 和 $[l2,r2]$ 这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数 n 和 m，表示字符串长度和询问次数。

第二行包含一个长度为 n 的字符串，字符串中只包含大小写英文字母和数字。

接下来 m 行，每行包含四个整数 $l1,r1,l2,r2$，表示一次询问所涉及的两个区间。

注意，字符串的位置从 1 开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

$1≤n,m≤10^5$

输入样例：

8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

Yes
No
Yes

---

2. 思路分析

字符串哈希，全称是字符串前缀哈希法，把 字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。
对形如 $X_1X_2X_3⋯X_{n−1}X_n$ 的字符串,采用字符的ascii 码乘上 P 的次方来计算哈希值。

映射公式： $(X_1×P^{n−1}+X_2×P^{n−2}+⋯+X_{n−1}×P^1+X_n×P^0) mod Q$

注意点：

• 任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA…都映射成0的话那就无法进行比较字符串是否相同了；
• 冲突问题：听过巧妙设置P(131 或 13331)，Q( $2^{64}$)的值，一般情况下可以避免发生冲突；
• 由于需要模 $2^{64}$，则可以直接用 unsigned long long来存储，它可以溢出，溢出时相当于模了一个 $2^{64}$；

问题是比较不同区间的子串是否相同，就转化为对应的哈希值是否相同。
求一个字符串的哈希值就相当于求前缀和，求一个字符串的子串哈希值就相当于求部分和。

前缀和公式 $h[i+1]=h[i]×P+s[i]$ $i∈[0,n−1]$ h为前缀和数组，s为字符串数组。
区间和公式 $h[l,r]=h[r]−h[l−1]×P*{r−l+1}$

区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，乘上 $P^2$ 把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

// unsigned long long 数据类型的范围是[0,2^64-1]
// 用 unsigned long long来存储h\，它可以溢出，溢出时就相当于模了一个2^64
typedef unsigned long long ULL;

//P取131或者13331，mod取2^64，在99.99%的情况下不会发生冲突
const int N = 100010, P = 131;

int n, m;
char str[N];
//h[i]表示前i个字符的hash值
ULL h[N], p[N];

//求[l, r]区间中字符串的哈希值
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main()
{
    cin >> n >> m;
    scanf("%s", str + 1);
    
    p[0] = 1; //p的0次方等于1
    
    for (int i = 1; i <= n; i ++)
    {
        h[i] = h[i - 1] * P + str[i]; //前缀和求以i结尾的整个字符串的哈希值
        p[i] = p[i - 1] * P;
    }
    
    while (m --)
    {
        
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        
        //如果两个区间的哈希值相同，则字符串相同；否则不同
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }
    return 0;
}

---

创作不易，如果有帮助到你，请给文章==点个赞和收藏==，让更多的人看到！！！
==关注博主==不迷路，内容持续更新中。# 第一章 KMP

一、KMP字符串

1. 题目描述

给定一个字符串 $S$，以及一个模式串 $P$，所有字符串中只包含大小写英文字母以及阿拉伯数字。

模式串 $P$ 在字符串 $S$ 中多次作为子串出现。

求出模式串 $P$ 在字符串 $S$ 中所有出现的位置的起始下标。

输入格式

第一行输入整数 $N$，表示字符串 $P$ 的长度。

第二行输入字符串 $P$。

第三行输入整数 $M$，表示字符串 $S$ 的长度。

第四行输入字符串 $S$。

输出格式

共一行，输出所有出现位置的起始下标（下标从 0 开始计数），整数之间用空格隔开。

数据范围

$1≤N≤10^5$
$1≤M≤10^6$

输入样例：

3
aba
5
ababa

输出样例：

0 2

---

2. 思路分析

求前缀数组，即 $next$ 数组，每一个子串都有一个固定的 $next$ 数组，它记录着字符串匹配过程中失配情况下可以向后多跳几个字符，其实也就是子串的前缀和后缀相同的最长长度。

如果给定的模式串是：“ABCDABD”，从左至右遍历整个模式串，其各个子串的前缀后缀分别如下表格所示：

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10, M = 1e6 + 10;

int n, m;
int ne[N]; //保存next数组
char s[M], p[N];

int main()
{
    cin >> n >> p + 1 >> m >> s + 1; //下标从1开始
    
    //求next数组
    //j表示匹配成功的长度，i表示p数组中下标，因为p数组的下标是从1开始的，只有1个时，j一定是0，所以i从2开始
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        //匹配不成功，则换到next数组
        while (j && p[i] != p[j + 1]) j = ne[j];
        //匹配成功的话，则j加1
        if (p[i] == p[j + 1]) j ++;
        //对应其下标
        ne[i] = j;
    }
    
    //j表示匹配成功的长度，因为刚开始还未开始匹配，所以长度是0
    for (int i = 1, j = 0; i <= m; i ++ )
    {
        //如果匹配不成功，则切换j到next数组中的值
        while (j && s[i] != p[j + 1]) j = ne[j];
        //匹配成功，则j加1，继续后面的匹配
        if (s[i] == p[j + 1]) j ++;
        if (j == n)
        {
            //因为题目中下标从0开始所以是i - n，如果是从1开始则是i - n + 1
            printf("%d ", i - n);
            //继续切换j到next数组中值，继续匹配是否还能与后面的匹配成功
            j = ne[j];
        }
    }
    return 0;
}

---

第二章 字典树（Tire）

一、Tire字符串统计

1. 题目描述

维护一个字符串集合，支持两种操作：

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

---

2. 思路分析

Trie树中有个二维数组 son[N][26]，表示当前结点的儿子，如果没有的话，可以等于++idx。Trie树本质上是一颗多叉树，对于字母而言最多有26个子结点。所以这个数组包含了两条信息。

建字典树：
儿子数组 son[p][u] 存储节点 p 沿着 u 这条边走到的子节点。边为 26 个小写字母（a ~ z）对应的映射值 0 ~ 25，每个节点最多可以有26个分叉。
比如：son[1][0]=2表示1结点的一个值为a的子结点为结点2; 如果son[1][0] = 0，则意味着没有值为a子结点。这里的son[N][26]相当于链表中的ne[N]。

计数数组cnt[p] 存储以节点 p 结尾的单词的插入次数。

节点编号 idx 用来给节点编号。

1. 空 Tire 仅有一个根节点，编号为0；
2. 从根节点开始插，枚举字符串的每个字符，如果有儿子，则 p 指针走到儿子；如果没有儿子，则先创建儿子，p 指针再走到儿子；
3. 在单词结束点记录插入次数。

---

3. 代码实现

//Tire树快速存储字符集合和快速查询字符集合
#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

// son[p][26]存储子节点的位置，分支最多26条
// cnt[] 存储以某节点为结尾的字符串个数（同时起标记作用）
// idx 表示当前要插入的节点是第几个，每创建一个节点值+1
int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str)
{
    int p = 0; //指针p，指向当前节点
    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 n;
    cin >> n;
    while (n --)
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }
    return 0;
}

---

二、最大异对

1. 题目描述

在给定的 $N$ 个整数 $A1，A2……AN$ 中选出两个进行 $xor$（异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 $N$。

第二行输入 $N$ 个整数 $A_1～A_N$。

输出格式

输出一个整数表示答案。

数据范围

$1≤N≤10^5$,
$0≤A_i<2^{31}$

输入样例：

3
1 2 3

输出样例：

3

---

2. 思路分析

异或： 如果a、b两个值不相同，则异或结果为1；如果a、b两个值相同，异或结果为0。

1. 将一个整数转化为一个32位的二进制数，也就是长度为32位的二进制字符串；
2. 从最高位开始检索，每次找与该位相反的数字，才能让异或最大，如果没有想反的数字，则选择相同的数字。
3. 返回最大的异或数。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

//M代表一个数字串二进制可以到多长
const int N = 100010, M = 3100010;

int n;
int a[N], son[M][2], idx;

void insert(int x)
{
    int p = 0; //根节点
    for (int i = 30; i >= 0; i --) 
    {
        int u = x >> i & 1; //x >> i:取二进制数x的第i位; x >> i & 1:二进制数x的第i位是0还是1
        if (!son[p][u]) son[p][u] = ++idx; //不存在该子节点，创建该子节点
        p = son[p][u]; //p指针指向子节点
    }
}

int search(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i --) //从最大数开始找
    {
        int u = x >> i & 1;
        //如果当前层有对应的不相同的数
        if (son[p][!u])
        {
            res = res * 2 + 1; // 更新res的值，每次把旧值乘以2（这一步相当于左移一位）再加上当前值
            p = son[p][!u]; //p指针就指向不同数的地址
        }
        //如果当前层没有对应的不相同的数，则p指针指向相同的数的地址
        //刚开始找0的时候是一样的所以+0    到了0和1的时候原来0右移一位,判断当前位是同还是异,同+0,异+1
        // else
        // {
        //     res = res * 2 + 0; //对res的值没有改变，省略
        //     p = son[p][u];
        // }
        else p = son[p][u];
    }
    return res;
}

int main()
{
    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])); //查找a[i]最大的异或值
    cout << res << endl;
    
    return 0;
}

---

第三章 并查集

一、合并集合

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，都要输出一个结果，如果 aa 和 bb 在同一集合内，则输出 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

---

2. 思路分析

并查集是一种树形的数据结构。

并查集支持的两个操作：

• 合并： 将两个子集合并成一个集合。
• 查找： 确定某个元素在哪个集合。

带路径压缩的查找：
根节点是集合的代表，查找就是找到元素所在集合的根。

1. 如果父节点等于自己，则找到了根并返回；
2. 如果还没有找到根，则继续递归查找；
3. 在返回的路上，顺带修改各节点的父节点为根。

合并：
把一个集合的根指向另一个集合的根。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int p[N];

// 返回x的祖先节点 + 路径压缩
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;
    
    while (m --)
    {
        char op[2];
        int a, b;
        scanf("%s%d%d", op, &a, &b);
        //合并：把一个集合的根指向另一个集合的根
        if (*op == 'M') p[find(a)] = find(b); 
        else
        {
            //若两个数的父节点一样，则在同一个集合
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

---

二、连通块中点的数量

1. 题目描述

给定一个包含 n 个点（编号为 $1∼n$）的无向图，初始时图中没有边。

现在要进行 m 个操作，操作共有三种：

1. C a b，在点 aa 和点 bb 之间连一条边，a 和 b 可能相等；
2. Q1 a b，询问点 aa 和点 bb 是否在同一个连通块中，a 和 b 可能相等；
3. Q2 a，询问点 aa 所在连通块中点的数量；

输入格式

第一行输入整数 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

---

2. 思路分析

1. 初始化：先设置每个节点的根节点为自己，刚开始是每个集合中点的数量为1；
2. 合并集合： 把一个集合的根指向另一个集合的根，并且把该集合中点的数量加入另一个集合中；
3. 查询：即判断两个集合的父节点是否一样。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
int p[N], cnt[N];

int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++)
    {
        p[i] = i;
        cnt[i] = 1;
    }
    
    while (m --)
    {
        string op;
        int a, b;
        cin >> op;
        
        if (op == "C")
        {
            cin >> a >> b;
            a = find(a), b = find(b);
            if (a != b)
            {
                p[a] = b;
                cnt[b] += cnt[a];
            }
        }
        else if (op == "Q1")
        {
            cin >> a >> b;
            if (find(a) == find(b)) puts("Yes");
            else puts("No");
        }
        else
        {
            cin >> a;
            cout << cnt[find(a)] << endl;
        }
    }
    return 0;
}

---

三、食物链

待完善......

---

第四章 堆

一、堆排序

1. 题目描述

输入一个长度为 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

---

2. 思路分析

如何手写一个堆？

1. 插入一个数：heap[ ++ size] = x; up(size);
2. 求集合中的最小值： heap[1];
3. 删除最小值：heap[1] = heap[size]; size -- ;down(1);
4. 删除任意一个元素：heap[k] = heap[size]; size -- ;up(k); down(k);
5. 修改任意一个元素：heap[k] = x; up(k); down(k);

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 1e5 + 10;

int n, m;
//h[i]表示第i个结点存储的值，i从1开始，2 * i是左子节点，2 * i + 1是右子节点
//cnt 既表示堆里存储的元素个数，又表示最后一个结点的下标
int h[N], cnt;

void down(int u)
{
    int t = u; //t存储三个结点中存在的最小的结点的下标，初始化为当前结点u
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2; //左子节点存在并且小于当前结点，更新t的下标
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1; //右子节点存在并且小于当前结点，更新t的下标
    if (u != t) //如果t==u意味着不用变动，u就是三个结点中拥有最小值的结点下标，否则交换数值
    {
        swap(h[u], h[t]); 
        down(t); //交换数值后，t这个结点存储原本u的值，u存储存储t的值（三个数中的最小值）。u不用调整了，但t情况不明，可能需要调整。直到它比左右子节点都小。
    }
}

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++) cin >> h[i];
    cnt = n; //初始化cnt，表示堆中有多少个元素

    //把堆初始化成小根堆，从二叉树的倒数第二行开始，把数字大的下沉
    for (int i = n/2; i; i --) down(i);
    
    while (m --)
    {
        cout << h[1] << ' '; //输出堆顶（最小值）
        h[1] = h[cnt --]; ////删除堆顶（用最后一个数覆盖第一个数），并且长度减1
        down(1); //让覆盖好的值继续往下走
    }
    return 0;
}

---

二、模拟堆

1. 题目描述

维护一个集合，初始时集合为空，支持如下几种操作：

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

---

2. 思路分析

相关思路在以下的代码注释中。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

int h[N]; //堆
int ph[N];//ph[k] = x:表示第k个插入的元素在树中存放的位置x
int hp[N];//hp[x] = k:表示树中位置x存放的是第k个插入的元素
int cnt;  //记录堆中当前数据的多少

void heap_swap(int a, int b)
{
    swap(ph[hp[a]], ph[hp[b]]);
    swap(hp[a], hp[b]);
    swap(h[a], h[b]);
}

void down(int u)
{
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u *2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u /= 2;
    }
}

int main()
{
    int n, m = 0; //m是记录插入的数的个数，m是对应hp中应该存的值
    cin >> n;
    while (n --)
    {
        string op;
        int k, x;
        cin >> op;
        //插入一个数 x
        if (op == "I")
        {
            cin >> x;
            cnt ++;
            m ++;
            ph[m] = cnt, hp[cnt] = m;
            h[cnt] = x;
            up(cnt);
        }
        //输出当前集合中的最小值
        else if (op == "PM") cout << h[1] << endl;
        //删除当前集合中的最小值
        else if (op == "DM")
        {
            heap_swap(1, cnt);
            cnt --;
            down(1);
        }
        //删除第 k 个插入的数
        else if (op == "D")
        {
            cin >> k;
            k = ph[k]; //这里一定要用k=ph[k]保存第k个插入点的下标
            heap_swap(k, cnt); //因为在此处heap_swap操作后ph[k]的值已经发生
            cnt --;
            up(k); //如果在up,down操作中仍然使用ph[k]作为参数就会发生错误
            down(k);
        }
        //修改第 k 个插入的数，将其变为 x
        else
        {
            cin >> k >> x;
            h[ph[k]] = x; //此处由于未涉及heap_swap操作且下面的up、down操作只会发生一个，所以可直接传入ph[k]作为参数
            up(ph[k]);
            down(ph[k]);
        }
    }
    return 0;
}

---

第五章 哈希表

一、模拟散列表

1. 题目描述

维护一个集合，支持如下几种操作：

1. I x，插入一个数 x；
2. Q x，询问数 x 是否在集合中出现过；

现在要进行 N 次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 N，表示操作数量。

接下来 N 行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果 xx 在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

$1≤N≤10^5$
$−109≤x≤10^9$

输入样例：

5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

Yes
No

---

2. 思路分析

散列表，也叫哈希表，是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。

开放寻址法：

• 如果要插入元素的映射位置没有元素，那么直接将该元素放在当前位置；
• 如果要插入元素的映射位置已经有了元素，那么就以此往后找，如果到了数组末尾还没有找到一个空的位置，就返回数组的头接着找；
• 为了防止整个数组都找了一遍还没有找到一个空的位置，数组大小通常要开数据范围的2~3倍。

---

3. 代码实现

#include <bits/stdc++.h>

using namespace std;

//开放寻址法一般开 数据范围的 2~3倍, 这样大概率就没有冲突了
const int N = 200003; //大于数据范围的第一个质数 
const int null = 0x3f3f3f3f;

int h[N];

int find(int x)
{
    //t表示x映射到哈希表中的位置
    //+N再%N可以避免出现负数
    int t = (x % N + N) % N;
    //冲突情况:当前位置不为空，并且不为x
    while (h[t] != null && h[t] != x)
    {
        t ++;
        if (t == N) t = 0; //如果到了末尾就从头开始
    } //while一定会结束，因为我们的数组范围是开了2~3倍的，所以整个数组不会被完全使用，因此while不会无限循环
    
    //如果x存在哈希表中，返回的t是下标；如果x不在哈希表中，返回的t是x在哈希表中要存储的位置
    return t; 
}

int main()
{
    //把哈希表的值设置成一个不可能被映射到的数，以此来判断该位置有没有被使用
    memset(h, 0x3f, sizeof h);
    
    int n;
    cin >> n;
    while (n --)
    {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') h[find(x)] = x;
        else
        {
            if (h[find(x)] == null) puts("No");
            else puts("Yes");
        }
    }
    return 0;
}

---

创作不易，如果有帮助到你，请给文章==点个赞和收藏==，让更多的人看到！！！
==关注博主==不迷路，内容持续更新中。