2. 基础数据结构初识

2.1 链表

---

2.1.1 单链表

概念：

• 链表是一种物理存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。
  • 链表由一系列结点组成，每个结点分为存储数据元素的数据域和存储下一个结点地址的指针域。

操作思想

• 插入：新建一个结点，将前一个结点的指针指向新结点。

• 删除：将待删除结点的前一个结点的指针指向该结点的后一个结点。

模板

/*
*  可使用数组、结构体等模拟链表。
*  使用malloc和new创建动态链表较慢，而使用结构体模拟实现较繁琐，故常采用静态数组模拟链表。
*/

const int N = 1e6 + 10; // 根据需要开辟链表大小

int e[N], ne[N], head = -1, idx = 0; // e[N]存储值，ne[N]存储下一个结点下标，head为头结点下标，idx为当前可用结点下标

// 在头部插入x
void head_add(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

// 在下标为k的结点后面插入x
void add(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

// 删除下标为k的结点后面的结点
void remove(int k) {
    ne[k] = ne[ne[k]];
}

---

例题 826.单链表

原题链接

描述

实现一个单链表，链表初始为空，支持三种操作：

1. 向链表头插入一个数。
2. 删除第 k 个插入的数后面的数。
3. 在第 k 个插入的数后插入一个数。

现在要对该链表进行 M 次操作，进行完所有操作后，从头到尾输出整个链表。

注意：题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式 第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

1. H x，表示向链表头插入一个数 x。
2. D k，表示删除第 k 个插入的数后面的数（当 k 为 0 时，表示删除头结点）。
3. I k x，表示在第 k 个插入的数后面插入一个数 x（此操作中 k 均大于 0）。

输出格式 共一行，将整个链表从头到尾输出。

数据范围 1≤M≤100000，所有操作保证合法。

输入样例：

10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6
H 8

输出样例：

6 4 6 5

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int e[N], ne[N], head = -1, idx = 0;

void head_add(int x) {  // 在头部插入 x
    e[idx] = x;
    ne[idx] = head;
    head = idx++;
}

void add(int k, int x) {  // 在下标 k 后面插入 x
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx++;
}

void remove(int k) {  // 删除下标为 k 的结点后面的结点
    ne[k] = ne[ne[k]];
}

int main() {
    int m;
    cin >> m;  // 读入操作次数

    while (m--) {
        string s;
        cin >> s;  // 读入操作

        if (s == "H") {  // 头部插入
            int x;
            cin >> x;
            head_add(x);
        } else if (s == "D") {  // 删除操作
            int k;
            cin >> k;
            if (k == 0) {
                head = ne[head];
            } else {
                remove(k - 1);  // idx 从 0 开始，下标为 k-1
            }
        } else if (s == "I") {  // 插入操作
            int k, x;
            cin >> k >> x;
            add(k - 1, x);
        }
    }

    for (int i = head; i != -1; i = ne[i]) {  // 遍历输出
        cout << e[i] << " ";
    }

    return 0;
}

---

2.1.2 双链表

概念：

• 在单链表的基础上，取消单一头结点，改为左、右两个端点。每个结点的指针域存储其左边结点的指针和右边结点的指针。

操作思想：

• 插入：思想同单链表，新建结点后，依次更改左右结点的左右指针的指向。
• 删除：思想同单链表，将删除结点的左右结点的左右指针改向，跳过该节点。

模板

const int N = 1e6 + 10;  // 根据需要开辟链表大小

int e[N], r[N], l[N], idx;  // e[N] 存储值，r[N] 存储右结点，l[N] 存储左结点，idx 用于计数

void init() {  // 初始化链表
    r[0] = 1;  // 初始化左端点右边为右端点
    l[1] = 0;  // 初始化右端点左边为左端点
    idx = 2;   // 已经用掉了左端点和右端点，下标从2开始
}

void add(int k, int x) {  // 在下标k右边插入x
    e[idx] = x;       // 存储新节点的值
    l[idx] = k;       // 新节点的左边指针为k
    r[idx] = r[k];    // 新节点的右边指针为k节点的右指针r[k]
    l[r[k]] = idx;    // 修改新节点右边节点的左指针为新节点下标idx
    r[k] = idx++;     // 修改新节点左边节点的右指针为新节点下标idx
}

// 调用时，若在第k个数的右边插入x则为 add(k+1, x)，

void remove(int k) {
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main() {
    r[0] = 1, l[1] = 0;  // 初始化链表

    int m;
    cin >> m;  // 读入操作次数

    while (m--) {
        string s;
        cin >> s;  // 读入操作

        if (s == "L") {  // 最左端插入x
            int x;
            cin >> x;
            add(0, x);  // 最左端的端点下标为0
        } else if (s == "R") {  // 最右端插入x
            int x;
            cin >> x;
            add(l[1], x);  // 最右端的端点下标为1的左边，即l[1]
        } else if (s == "D") {  // 删除操作
            int k;
            cin >> k;
            remove(k + 1);  // idx从2开始，下标为k+1
        } else if (s == "IL") {  // 在第k个数左边插入x
            int k, x;
            cin >> k >> x;
            add(l[k + 1], x);  // 即在第k个数左边的数的右边插入x
        } else if (s == "IR") {  // 在第k个数右边插入x
            int k, x;
            cin >> k >> x;
            add(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) {  // 遍历输出
        cout << e[i] << " ";
    }

    return 0;
}

---

2.2 栈

---

2.2.1 模拟栈

---

概念：

• 栈是一种先进后出的数据结构。
  • 只允许对栈顶元素操作，不允许遍历。

操作思想：

• 利用静态数组模拟栈。
  • 实现进栈，出栈等操作。

模板：

const int N = 1e6 + 10;

int stk[N], tt = 0;  // stk[N]用于模拟栈，类型可自定义，tt表示栈顶下标

void push(int x) {  // 栈顶插入x
    stk[++tt] = x;
}

int top() {  // 返回栈顶元素
    return stk[tt];
}

void pop() {  // 弹出栈顶元素
    tt--;
}

bool empty() {  // 判断是否为空
    return tt == 0;  // 若为空则返回true
}

---

例题 828. 模拟栈

原题链接

描述

实现一个栈，栈初始为空，支持四种操作：

1. push x – 向栈顶插入一个数 x；
2. pop – 从栈顶弹出一个数；
3. empty – 判断栈是否为空；
4. query – 查询栈顶元素。

现在要对栈进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式
第一行包含整数 M，表示操作次数。
接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。
其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围
1 ≤ M ≤ 100000, 1 ≤ x ≤ 10⁹，所有操作保证合法。

输入样例：

10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例：

5
5
YES
4
NO

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int stk[N], tt = 0;

void add(int x) {
    stk[++tt] = x;
}

void pop() {
    tt--;
}

bool empty() {  // 判断是否为空
    return tt == 0;  // 若为空则返回 true
}

int top() {
    return stk[tt];
}

int main() {
    int n;
    cin >> n;

    while (n--) {
        string s;
        cin >> s;
        if (s == "push") {
            int x;
            cin >> x;
            add(x);
        } else if (s == "pop") {
            pop();
        } else if (s == "empty") {
            if (empty()) {
                cout << "YES" << endl;
            } else {
                cout << "NO" << endl;
            }
        } else if (s == "query") {
            cout << top() << endl;
        }
    }

    return 0;
}

---

2.2.2 单调栈

---

概念

栈中的元素满足某种单调性质。

应用

• 常见模型：找出每个数左边离它最近的比它大/小的数。

---

例题 830. 单调栈

原题链接

描述

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入格式
第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

输出格式
共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围
1≤N≤10⁵
1≤数列中元素≤10⁹

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int stk[N], tt = 0;

int main() {
    int n;
    cin >> n;
    while (n--) {
        int x;
        cin >> x;
        while (tt > 0 && x <= stk[tt]) tt--;  // 当栈不为空时，判断 x 与栈顶元素关系，若构成逆序，则删除栈顶元素
        if (tt > 0) cout << stk[tt] << " ";
        else cout << -1 << " ";
        stk[++tt] = x;
    }

    return 0;
}

---

2.3 队列

---

2.3.1 模拟队列

---

概念

• 是一种先进先出的数据结构，它有两个出口。
  • 队列允许从尾端添加元素，从头端移除元素。
  • 队列中只有队头和队尾才可以被外界使用，故队列不允许遍历。

操作思想

• 利用静态数组模拟队列，实现入队、出队等操作。

模板

const int N = 1e6 + 10;

int que[N], hh = 0, tt = -1;  // que[N] 用于模拟队列，类型可自定义，hh 为队头，tt 为队尾

void add(int x) {  // 队尾插入 x
    que[++tt] = x;
}

int top() {  // 返回队头元素
    return que[hh];
}

int back() {  // 返回队尾元素
    return que[tt];
}

void pop() {  // 弹出队头元素
    hh++;
}

bool empty() {  // 判断是否为空
    return tt < hh;  // 若为空则返回 true
}

---

例题 829. 模拟队列

原题链接

描述

实现一个队列，队列初始为空，支持四种操作：

1. push x – 向队尾插入一个数 x；
2. pop – 从队头弹出一个数；
3. empty – 判断队列是否为空；
4. query – 查询队头元素。

现在要对队列进行 M 个操作，其中的每个操作 3 和操作 4 都要输出相应的结果。

输入格式
第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式
对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。

数据范围
1 ≤ M ≤ 100000, 1 ≤ x ≤ 10^9，所有操作保证合法。

输入样例：

10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例：

NO
6
YES
4

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int que[N], hh = 0, tt = -1; // hh 表示队头，tt 表示队尾

void add(int x) {
    que[++tt] = x;
}

void pop() {
    hh++;
}

bool empty() {
    return tt < hh;
}

int top() {
    return que[hh];
}

int main() {
    int m;
    cin >> m;

    while (m--) {
        string s;
        cin >> s;
        if (s == "push") {
            int x;
            cin >> x;
            add(x);
        } else if (s == "pop") {
            pop();
        } else if (s == "empty") {
            if (empty())
                cout << "YES" << endl;
            else
                cout << "NO" << endl;
        } else if (s == "query") {
            cout << top() << endl;
        }
    }

    return 0;
}

---

2.3.2 单调队列

---

概念

• 队列中的元素满足某种单调性质

应用

• 常见模型：找出滑动窗口中的最大值/最小值

---

例题 154. 滑动窗口

原题链接

描述
给定一个大小为 n ≤ 10^6 的数组。

有一个大小为 k 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 k 个数字。

每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]，k 为 3。

窗口位置	最小值	最大值
[1 3 -1] -3 5 3 6 7	-1	3
1 [3 -1 -3] 5 3 6 7	-3	3
1 3 [-1 -3 5] 3 6 7	-3	5
1 3 -1 [-3 5 3] 6 7	-3	5
1 3 -1 -3 [5 3 6] 7	3	6
1 3 -1 -3 5 [3 6 7]	3	7

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 n 和 k，分别代表数组长度和滑动窗口的长度。

第二行有 n 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两行。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

输入样例：

8 3
1 3 -1 -3 5 3 6 7

输出样例：

-1 -3 -3 -3 3 3
3 3 5 5 6 7

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int a[N], q[N], hh, tt;

int main()
{
    int n, m;
    cin >> n >> m;

    for (int i = 0; i < n; i++) scanf("%d", &a[i]); // 读入数组元素

    // 计算每个窗口的最小值
    hh = 0, tt = -1; // 初始化单调队列，存储数组下标
    for (int i = 0; i < n; i++)
    {
        // 判断队头是否已滑出窗口
        if (hh <= tt && i - m + 1 > q[hh]) hh++;
        // 维护队列的单调性（递增），确保队头为最小值
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        // 将当前元素的下标入队
        q[++tt] = i;
        // 当窗口形成后，输出队头（最小值）
        if (i >= m - 1) printf("%d ", a[q[hh]]);
    }
    cout << endl;

    // 计算每个窗口的最大值
    hh = 0, tt = -1; // 重新初始化单调队列
    for (int i = 0; i < n; i++)
    {
        // 判断队头是否已滑出窗口
        if (hh <= tt && i - m + 1 > q[hh]) hh++;
        // 维护队列的单调性（递减），确保队头为最大值
        while (hh <= tt && a[q[tt]] <= a[i]) tt--;
        // 将当前元素的下标入队
        q[++tt] = i;
        // 当窗口形成后，输出队头（最大值）
        if (i >= m - 1) printf("%d ", a[q[hh]]);
    }

    return 0;
}

---

2.4 堆

---

概念

• 本质为一棵完全二叉树。
  • 以小根堆为例，其每个结点的值均小于等于左右子节点，即根节点为整棵树的最小值。

操作思想

• 存储方式：用一维数组存储，那么若根节点的下标是 i，则左儿子是 2 * i，右儿子是 2 * i + 1。

// 对无序的一维数组进行建堆（小根堆）
for(int i = n / 2; i >= 1; i--) down(i); // n 表示数组大小，利用 down 操作调整堆

• 调整：若某一节点的值发生改变，则需要判断其与父节点和左右两个子节点的大小关系，再进行上移或下移操作，递归处理直至满足堆的性质。

• 以小根堆为例：若某一节点的值增大，则需要将其向下移动，直到不能下移为止。

• 删除和修改元素：将最后插入的元素覆盖（替换）需要修改的元素，之后从修改元素的位置重新对堆进行调整。

---

2.4.1 堆排序

---

思想

• 将数据以堆的形式存储。
  • 通过堆的上移或下移操作对堆中的数据进行排序。
  • 不考虑对堆中的数据进行动态修改。

模板

// 以小根堆为例

const int N = 1e6 + 10; // 堆的最大容量

int h[N]; // h 数组存储堆中的元素
int idx;  // idx 表示堆中当前元素的个数（即堆的大小）

void down(int u) { // 下移操作，u 表示当前节点的下标
    int t = u;     // t 用于记录当前最小节点的下标
    int p = u * 2; // p 表示左儿子节点的下标，p + 1 表示右儿子节点的下标
    if (p <= idx && h[p] < h[t]) t = p;         // 若左儿子存在且小于当前节点，更新 t
    if (p + 1 <= idx && h[p + 1] < h[t]) t = p + 1; // 若右儿子存在且小于当前节点，更新 t
    if (u != t) { // 若最小节点不是当前节点，则交换并递归下移
        swap(h[t], h[u]);
        down(t);
    }
}

void up(int u) {   // 上移操作，u 表示当前节点的下标
    int t = u / 2; // t 表示父节点的下标
    if (t >= 1 && h[u] < h[t]) { // 若父节点存在且当前节点小于父节点，则交换并递归上移
        swap(h[u], h[t]);
        up(t);
    }
}

---

例题 838. 堆排序

原题链接

描述

输入一个长度为 n 的整数数列，从小到大输出前 m 小的数。

输入格式
第一行包含整数 n 和 m。
第二行包含 n 个整数，表示整数数列。

输出格式
共一行，包含 m 个整数，表示整数数列中前 m 小的数。

数据范围
1 ≤ m ≤ n ≤ 10⁵，1 ≤ 数列中元素 ≤ 10⁹

输入样例：

5 3
4 5 1 3 2

输出样例：

1 2 3

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;

int h[N];
int idx;

void down(int u) {
    int p = u * 2;
    int t = u;

    if (p <= idx && h[p] < h[t]) t = p;
    if (p + 1 <= idx && h[p + 1] < h[t]) t = p + 1;
    if (u != t) {
        swap(h[t], h[u]);
        down(t);
    }
}

int main() {
    int n, m;
    cin >> n >> m;

    // 读取数据并建堆
    for (int i = 1; i <= n; i++) cin >> h[i];
    idx = n;
    for (int i = n / 2; i >= 1; i--) down(i);

    // 输出前 m 小的数
    for (int i = 1; i <= m; i++) {
        cout << h[1] << " ";
        h[1] = h[idx--]; // 用最后一个元素覆盖堆顶，并减小堆的大小
        down(1);         // 调整堆
    }

    return 0;
}

---

2.4.2 可操作的堆

---

支持的操作

• 插入一个数
• 求集合中的最小值
• 删除最小值
• 删除任意一个元素
• 修改任意一个元素

模板 (注释解析版)

// 以小根堆为例

const int N = 1e6 + 10;  // 堆的大小

int idx, m;  // idx 表示当前的结点在数组中的下标，m 表示插入的第 m 个数

int h[N], ph[N], hp[N];
// h[N] 为堆
// ph[N] 存储第 m 个数在 h[N] 中的下标 (即 ph[m] = idx)
// hp[N] 存储在 h[N] 中下标为 idx 的数是第 m 个插入的数 (即 hp[idx] = m)
// 由于我们操作第 m 个元素时需要知道它在堆中的位置，故需要 ph 和 hp 的映射关系来确定。

void h_swap(int a, int b) {  // 完成交换操作
    swap(ph[hp[a]], ph[hp[b]]);
    // 通过 hp[a] 找到下标 a 对应的是第几个插入的数 (设为 m_i)，则 ph[hp[a]] 可得到其在 h 中的下标。
    // 通过 hp[b] 找到下标 b 对应的是第几个插入的数 (设为 m_j)，则 ph[hp[b]] 可得到其在 h 中的下标。
    // 交换这两个数的下标映射关系。

    swap(hp[a], hp[b]);
    // 交换两个位置对应的插入序数的映射关系。

    swap(h[a], h[b]);
    // 交换堆数组中的值。
}

void down(int u) {  // 完成下移操作，u 表示父结点
    int t = u;      // t 用于记录最小值节点的下标
    int p = u * 2;  // p 表示左儿子节点的下标，p+1 表示右儿子

    if (p <= idx && h[p] < h[t]) t = p;
    // 如果左儿子存在且小于当前记录的最小值 (t)，则更新 t 为左儿子下标。

    if (p + 1 <= idx && h[p + 1] < h[t]) t = p + 1;
    // 如果右儿子存在且小于当前记录的最小值 (t)，则更新 t 为右儿子下标。

    if (t != u) {  // 如果最小值不是父节点本身，则需要下移
        h_swap(t, u);  // 交换父节点与最小值子节点
        down(t);       // 递归处理被交换下去的节点，直到满足堆性质
    }
}

void up(int u) {  // 完成上移操作，u 表示子结点
    int t = u >> 1;  // t 表示 u 的父结点的下标
    if (t && h[u] < h[t]) {  //当t>0并且子结点的值小于父结点的值，说明u要上移
        h_swap(t, u);  //交换
        up(t);  //递归处理，直到不能上移
    }
}

模板(简注释)

// 以小根堆为例
const int N = 1e6 + 10;  // 堆的大小
int idx, m;  // idx表示当前的结点在数组中的下标，m表示插入的第m个数
int h[N], ph[N], hp[N];
void h_swap(int a, int b) {
    swap(ph[hp[a]], ph[hp[b]]);  // 交换idx的映射关系
    swap(hp[a], hp[b]);  // 交换m的映射关系
    swap(h[a], h[b]);    // 交换值
}
void down(int u) {
    int t = u;
    int p = u * 2;  // p表示左儿子节点的下标，p+1表示右儿子
    if (p <= idx && h[p] < h[t]) t = p;
    if (p + 1 <= idx && h[p + 1] < h[t]) t = p + 1;
    if (t != u) {
        h_swap(t, u);
        down(t);  // 递归处理，直到不能下移
    }
}
void up(int u) {
    int t = u >> 1;
    if (t && h[u] < h[t]) {
        h_swap(t, u);
        up(t);  // 递归处理，直到不能上移
    }
}

---

例题 839. 模拟堆

原题链接

描述

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

I x，插入一个数 x； PM，输出当前集合中的最小值； DM，删除当前集合中的最小值（数据保证此时的最小值唯一）； D k，删除第 k 个插入的数； C k x，修改第 k 个插入的数，将其变为 x； 现在要进行 N 次操作，对于每个输出指令 PM，输出当前集合的最小值。

输入格式
第一行包含整数 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 <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 10;  // 堆的大小
int idx, m;  // idx表示当前的结点在数组中的下标，m表示插入的第m个数
int h[N], ph[N], hp[N];

void h_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;
    int p = u * 2;  // p 表示左儿子节点下标，p+1 表示右儿子
    if (p <= idx && h[p] < h[t]) t = p;
    if (p + 1 <= idx && h[p + 1] < h[t]) t = p + 1;
    if (t != u) {
        h_swap(t, u);
        down(t);  // 递归下沉，直到满足堆性质
    }
}

void up(int u) {
    int t = u >> 1;
    if (t && h[u] < h[t]) {
        h_swap(t, u);
        up(t);  // 递归上浮，直到满足堆性质
    }
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        string op;
        int k, x;
        cin >> op;
        if (op == "I") {
            cin >> x;
            idx++, m++;
            ph[m] = idx, hp[idx] = m;  // 记录映射关系
            h[idx] = x;                // 在堆末尾插入 x
            up(idx);                   // 上浮调整
        } else if (op == "PM") {
            cout << h[1] << endl;      // 输出堆顶最小值
        } else if (op == "DM") {
            h_swap(1, idx);            // 将堆尾元素移至堆顶
            idx--;
            down(1);                   // 下沉调整
        } else if (op == "D") {
            cin >> k;
            k = ph[k];                 // 找到第 k 个插入元素的堆中位置
            h_swap(k, idx);            // 将堆尾元素移至该位置
            idx--;
            down(k);                   // 下沉调整
            up(k);                     // 上浮调整（只会执行其一）
        } else {
            cin >> k >> x;
            k = ph[k], h[k] = x;       // 找到第 k 个插入元素并修改其值
            down(k);                   // 下沉调整
            up(k);                     // 上浮调整（只会执行其一）
        }
    }
    return 0;
}

---

2.5 哈希表

---

概念

对于处理复杂且大量的数据，我们可以将其映射到一个便于操作的区间内。例如，将范围在 -1e9 到 1e9 的数映射到 0 到 1e5 的范围内，以便于进行插入、查询、删除等操作。

---

2.5.1 模拟散列表存储（拉链法）

操作思想

• 选取质数 N = 1e6 + 3 作为哈希表的大小（模数）。通常，使用质数可以减少冲突。
  • 对于每个数据，将其哈希值 k 作为数组下标来存储。
  • 如果两个不同的数据计算出相同的哈希值 k，则在该位置创建一个链表节点来存储数据，以此解决冲突。

模板代码

const int N = 1e6 + 3; // 哈希表大小（取质数）

int h[N], e[N], ne[N]; // h[N]: 链表头数组，初始化为-1; e[N]: 存储实际值; ne[N]: 存储下一个节点的索引
int idx; // 当前可用的节点索引

void init() { // 初始化哈希表
    for (int i = 0; i < N; i++) h[i] = -1;
}

void insert(int x) { // 插入操作
    int k = (x % N + N) % N; // 计算哈希值，确保结果为非负数
    e[idx] = x;              // 存储数据
    ne[idx] = h[k];          // 新节点的next指向原来的头节点
    h[k] = idx++;            // 更新头节点为当前节点
}

bool find(int x) { // 查询操作
    int k = (x % N + N) % N; // 计算哈希值
    for (int i = h[k]; i != -1; i = ne[i]) { // 遍历链表
        if (e[i] == x) return true;          // 找到数据
    }
    return false; // 未找到数据
}

---

例题 840. 模拟散列表

原题链接

题目描述

维护一个集合，支持以下操作：

• I x：插入一个数 x。
• Q x：询问数 x 是否在集合中出现过。

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

输入格式 第一行包含一个整数 N，表示操作数量。 接下来 N 行，每行包含一个操作指令，格式为 I x 或 Q x。

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

数据范围

• 1 ≤ N ≤ 10^5
• -10^9 ≤ x ≤ 10^9

输出样例

Yes
No

参考代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e6 + 3;

int h[N], e[N], ne[N];
int idx;

void init() {
    for (int i = 0; i < N; i++) h[i] = -1;
}

void insert(int x) {
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool find(int x) {
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i]) {
        if (e[i] == x) return true;
    }
    return false;
}

int main() {
    init(); // 记得初始化哈希表
    int n;
    scanf("%d", &n);
    while (n--) {
        char op[2];
        int x;
        scanf("%s%d", op, &x);
        if (*op == 'I') {
            insert(x);
        } else {
            puts(find(x) ? "Yes" : "No");
        }
    }
    return 0;
}

---

2.5.2 字符串前缀哈希

---

操作思想

• 把字符串变成一个P进制数字，实现不同的字符串映射到不同的数字。
  • 对形如 X1 X2 X3…Xn−1 Xn 的字符串，采用字符的ASCII码乘上 P 的次方来计算哈希值。
  • 映射处理为该哈希值对Q进行取模：(X1 * P^(n-1) + X2 * P^(n-2) + … + Xn−1 * P^1 + Xn * P^0) % Q。

注意点

• 任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A, AA, AAA皆为0。
  • 冲突问题：P = (131 或 13331) , Q = 2^64，一般情况下不产生冲突。
  • 对于Q取模，我们用unsigned long long自然溢出来解决。

模板

typedef unsigned long long ULL;

const ULL N = 1e6 + 3, P = 131;

ULL h[N], p[N]; // h[k]存储字符串前k个字符的哈希值, p[k]存储 P^k mod 2^64

string s;
cin >> s;  //读入字符串s

// 初始化前i个字符的哈希值
p[0] = 1;
for (int i = 1; i <= s.size(); i++) {
    h[i] = h[i - 1] * P + s[i - 1];  //递推计算前缀哈希值
    p[i] = p[i - 1] * P;  //存储每一位的权值
}

// 计算子串str[l~r]的哈希值
ULL find(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];  //将h[l-1]的高位与h[r]的最高位置的权值相对齐
}

---

例题 841. 字符串哈希

(原题链接：<https://www.acwing.com/problem/content/841/>)

描述

给定一个长度为 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

代码

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;

const int N = 1e6 + 3, P = 131;

ULL h[N], p[N];

ULL find(int l, int r) {
    return h[r] - h[l - 1] * p[r - l + 1];
}

int main() { 
    int n, m;
    cin >> n >> m;
    string s;
    cin >> s;

    p[0] = 1;
    for (int i = 0; i < s.size(); i++) {
        p[i + 1] = p[i] * P;
        h[i + 1] = h[i] * P + s[i];
    }

    while (m--) {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        if (find(l1, r1) == find(l2, r2)) cout << "Yes" << endl;
        else cout << "No" << endl;
    }

    return 0;
}

---

2.6 串（待补全）

---

2.6.1 KMP

---

2.6.2 字典树

---

2.7 并查集（待补全）