基础数据结构
栈，队列，链表，Trie，堆，哈希表
基础数据结构
Base is not easy.
并不复杂的基础数据结构可以在各种地方灵活应用，所以从某种程度来说，这部分的应用是很难的。
本菜狗苦基础算法和基础数据结构久矣，这个总结还是非常有必要的。
栈
栈的基础知识就不再总结了，大家都会。下面总结一下栈这种数据结构的高级玩法。
维护更多信息的栈
典型的形如边维护栈边维护栈中元素的最值，这种有查询历史信息意味，且看起来和栈的状态息息相关的，一般要另开一个栈，和原来的栈同步工作，以维护我们想要的信息。当然，也不一定非得用栈，有时候查询的信息并不一定是“从栈顶到栈底”的信息，这个时候可能得用数组等可以访问中间元素的容器去维护那些额外的信息。
对顶栈
我不仅能操作，还能撤销，还能撤销我的撤销。像这种操作，可以使用“对顶栈”去建模，两个栈互相传递数据，就可以实现左右横跳。在这个基础上使用上一个标题中提到的技巧，就可以维护反复横跳的状态下的更多信息。
出栈序列（卡特兰数）
这个问题抽象出来就是数学中的卡特兰数，由于其应用场合多得离谱且好多看起来一点关系都没有，所以我会把它放到数学专题或者具体数学读书笔记中进行专门整理。
upd：离散数学昨天（2021/5/11）似乎刚讲了卡特兰数，然而我翘了，这就去数学部分补上这部分知识点。
单调栈
这可能是我在系统补基础之前，制裁我次数最多的一个数据结构。
单调栈的原理就是每次压栈之前，都维护栈中元素的单调性，使得压栈之后从栈顶到栈底的元素要么单调递增要么单调递减，具体咋样由题目决定。
通过单调栈，我们可以求出每个位置的元素的左边（或者右边）第一个比它大（小）的数的位置。这个就是单调栈最最常用的地方了。
我们一般是往单调栈中压入位置，维护的是这些位置的数的单调性。
给一个求最左边第一个比自己小的数的位置的模板：
int h[N], q[N], tt = 0, l[N];
h[0] = -INF;
for (int i = 1; i <= n; i++) {
l[i] = 0;
while (h[q[tt]] >= h[i]) {
tt--;
}
l[i] = q[tt];
q[++tt] = i;
}
这个玩意本身不难，但是考察的相关题目不简单，主要是题目的包装比较多，模型一层包着一层，比如3516. 最大面积 - AcWing题库。如果没有见识过一定的模型，只是知道单调栈模板的话，基本不太可能做出来这个问题。要想做这个问题，先要知道单调栈的一个比较裸的应用，求直方图中的最大矩形，然后，推广到求网格图中的最大的全都是1的矩形，最后加上一点点trick来解决这个带单点修改的网格图中的最大全1矩形问题。
表达式计算
把中缀表达式转化成后缀表达式，进而求出表达式的结果，也是栈的一个重要的应用。
中缀转后缀的基本思路是：
- 遇到数字，就算出来整个数，丢到后缀表达式的后面
- 遇到符号
- 如果是左括号，入栈
- 如果是右括号，不断出栈并把出栈元素放到后缀表达式后面，直到栈空或者遇到左括号，然后把左括号弹了
- 如果是运算符，在栈空或者遇到括号之前，需要把所有的优先级大于等于本运算符的算符弹出并放到后缀表达式后面。特别的，对于减号，要判断是负号还是减号。
后缀表达式计算思路：
建立一个数栈，遇到数就放进去，遇到运算符，就取出来两个数（注意顺序），计算完之后压栈回去。最后剩下的那个元素就是答案了。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef struct {
int type;
int value;
char op;
} Node;
char s[N + 1];
Node infix[N];
stack<char> op_stack;
stack<int> ans;
int idx = 0;
int main() {
cin >> s;
for (int i = 0; s[i] != '\0'; i++) {
if (isdigit(s[i])) {
int val = 0;
while (s[i] != '\0' && isdigit(s[i])) {
val = 10 * val + s[i] - '0';
i++;
}
i--;
infix[idx].type = 0;
infix[idx++].value = val;
} else {
if (s[i] == '(') {
op_stack.push(s[i]);
} else if (s[i] == ')') {
while (!op_stack.empty() && op_stack.top() != '(') {
char now = op_stack.top();
op_stack.pop();
infix[idx].type = 1;
infix[idx++].op = now;
}
if (!op_stack.empty()) {
op_stack.pop();
}
} else if (s[i] == '+' || s[i] == '-') {
if (s[i] == '-') {
// 处理负数而不是减号的情况
if (i == 0) {
infix[idx].type = 0;
infix[idx++].value = 0;
} else {
if (!(isdigit(s[i - 1]) || s[i - 1] == ')')) {
infix[idx].type = 0;
infix[idx++].value = 0;
}
}
}
while (!op_stack.empty()) {
char now = op_stack.top();
if (now == '+' || now == '-' || now == '*' || now == '/' || now == '^') {
infix[idx].type = 1;
infix[idx++].op = now;
op_stack.pop();
} else {
break;
}
}
op_stack.push(s[i]);
} else if (s[i] == '*' || s[i] == '/') {
while (!op_stack.empty()) {
char now = op_stack.top();
if (now == '*' || now == '/' || now == '^') {
infix[idx].type = 1;
infix[idx++].op = now;
op_stack.pop();
} else {
break;
}
}
op_stack.push(s[i]);
} else if (s[i] == '^') {
while (!op_stack.empty()) {
char now = op_stack.top();
if (now == '^') {
infix[idx].type = 1;
infix[idx++].op = now;
op_stack.pop();
} else {
break;
}
}
op_stack.push(s[i]);
} else {
puts("fuck");
break;
}
}
}
while (!op_stack.empty()) {
if (op_stack.top() == '(' || op_stack.top() == ')') {
op_stack.pop();
continue;
}
infix[idx].type = 1;
infix[idx++].op = op_stack.top();
op_stack.pop();
}
for (int i = 0; i < idx; i++) {
if (infix[i].type == 0) {
ans.push(infix[i].value);
} else {
int v2 = ans.top();
ans.pop();
int v1 = ans.top();
ans.pop();
if (infix[i].op == '+') {
ans.push(v1 + v2);
} else if (infix[i].op == '-') {
ans.push(v1 - v2);
} else if (infix[i].op == '*') {
ans.push(v1 * v2);
} else if (infix[i].op == '/') {
ans.push(v1 / v2);
} else {
ans.push(pow(v1, v2));
}
}
}
cout << ans.top() << endl;
return 0;
}
表达式计算还有递归下降法：
首先，对于左递归的文法，先把递归转成迭代。
每一个解析函数只解析属于自己这部分的东西，如果解析到不是这部分的内容，则下标需要回退或者只有发现是这部分的内容才移动下标继续解析。
递归下降需要考虑会不会越界。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int idx, len;
char s[N];
int parse_expr();
int parse_term();
int parse_factor();
int parse_expr() {
int res = parse_term();
while (idx < len) {
char op = s[idx];
if (op == '+') {
idx++;
res += parse_term();
} else if (op == '-') {
idx++;
res -= parse_term();
} else {
break;
}
}
return res;
}
int parse_term() {
int res = parse_factor();
while (idx < len) {
char op = s[idx];
if (op == '*') {
idx++;
res *= parse_factor();
} else if (op == '/') {
idx++;
res /= parse_factor();
} else if (op == '^') {
idx++;
res = pow(res, parse_factor());
} else {
break;
}
}
return res;
}
int parse_factor() {
int res = 0;
if (s[idx] == '(') {
idx++;
res = parse_expr();
idx++;
} else {
while (idx < len && s[idx] >= '0' && s[idx] <= '9') {
res = 10 * res + s[idx++] - '0';
}
}
return res;
}
int main() {
cin >> s;
len = strlen(s);
cout << parse_expr() << endl;
return 0;
}
另外还有中缀表达式直接求值的算法：
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;
char expr[N], n;
int calc(int l, int r) {
int pos1 = -1, pos2 = -1, pos3 = -1, cnt = 0;
for (int i = l; i <= r; i++) {
if (expr[i] == '(') {
cnt++;
} else if (expr[i] == ')') {
cnt--;
} else {
if (cnt == 0 && (expr[i] == '+' || expr[i] == '-')) {
pos1 = i;
} else if (cnt == 0 && (expr[i] == '*' || expr[i] == '/')) {
pos2 = i;
} else if (cnt == 0 && expr[i] == '^') {
pos3 = i;
}
}
}
if (pos1 != -1) {
if (expr[pos1] == '+') {
return calc(l, pos1 - 1) + calc(pos1 + 1, r);
} else {
return calc(l, pos1 - 1) - calc(pos1 + 1, r);
}
} else if (pos2 != -1) {
if (expr[pos2] == '*') {
return calc(l, pos2 - 1) * calc(pos2 + 1, r);
} else {
return calc(l, pos2 - 1) / calc(pos2 + 1, r);
}
} else if (pos3 != -1) {
int val1 = calc(l, pos3 - 1);
int val2 = calc(pos3 + 1, r);
return (int) pow(val1, val2);
} else {
if (expr[l] == '(' && expr[r] == ')') {
return calc(l + 1, r - 1);
} else if (expr[l] == '(') {
return calc(l + 1, r);
} else if (expr[r] == ')') {
return calc(l, r - 1);
} else {
int flag = 1;
int val = 0;
for (int i = l; i <= r; i++) {
if (expr[i] == '-') {
flag *= -1;
} else {
val = 10 * val + expr[i] - '0';
}
}
return val * flag;
}
}
}
int main() {
scanf("%s", expr);
n = strlen(expr);
printf("%d\n", calc(0, n - 1));
return 0;
}
括号序列匹配
栈也常常用来进行括号序列的匹配，很多与括号序列相关的计数问题可以按照匹配关系进行组合计数/dp计数，这时就需要先使用栈预处理出匹配情况（有时候只需要用一个变量来处理即可）。
一个合法括号序列的性质：
- 左右括号数量相同
- 任何一个前缀中左括号数量不少于右括号数量
- 去掉一对括号，得到的仍然是合法括号序列
由于单纯的进行括号序列的检查和匹配过于简单，所以就不介绍了。
有一个有趣的问题：给一个括号序列，要你尽可能少的添加括号，使之变得合法。求有多少本质不同的添加结果（即添加完成之后这个括号序列和其他添加结果至少有一个位置不一样）。括号序列
首先，不难统计出原括号序列到底有多少个括号没有匹配好，那么我们最终至少要添加的括号数量就是这么多了。
之后添加括号的话，就是在原括号序列的每个空里插括号了。我们不能保证每个空里面只能添加一个括号，也不能保证每个空里面添加的是相同类型的括号。但是由于合法括号序列的第三个性质，我们知道每个空里面新添加的括号的排布一定是
))...)((...(，否则我们就加入了可以配对的括号，那么删去这一对括号原括号序列的合法性不会变化，且会变得更短。所以同一个空里面插入的左右括号不会互相影响，所以我们可以分别去考虑左右括号的补全方案数，然后做乘法得到最终方案数。假设我们现在要做添加左括号的方案数，那么我们考虑在每个右括号上画一条竖线，把整个括号序列用这些竖线分成好几段，那么每段中显然都是左括号或者没有括号，每段的括号添加的方案数，其实就只和这一段的左括号数量有关系。考虑
dp[i][j]表示原括号序列的前i个括号并考虑新加的括号之后，左括号比右括号多j个的加左括号的方案数，那么可以发现：
- 如果第
i个为左括号，那么dp[i][j] = dp[i - 1][j - 1]- 如果第
i个为右括号，那么dp[i][j] = dp[i - 1][j + 1] + dp[i - 1][j] + ... + dp[i - 1][0]，右边各项的意思分别是在第i和第i - 1个括号之间不加括号、加一个左括号... 加j + 1个左括号。这里可以使用完全背包的trick优化，变成dp[i][j] = dp[i][j - 1] + dp[i - 1][j + 1]统计加右括号的方案的话，直接做需要从右往左扫描，比较反人类，所以可以翻转字符串，然后反转左右括号，再做一遍左括号的匹配。
#include <bits/stdc++.h> using namespace std; typedef long long LL; const int N = 5010; const int MOD = 1e9 + 7; LL dp[N][N], n; char s[N]; LL solve() { memset(dp, 0, sizeof dp); dp[0][0] = 1; for (int i = 1; i <= n; i++) { if (s[i] == '(') { for (int j = 1; j <= n; j++) { dp[i][j] = dp[i - 1][j - 1] % MOD; } } else { dp[i][0] = (dp[i - 1][0] + dp[i - 1][1]) % MOD; for (int j = 1; j <= n; j++) { dp[i][j] = (dp[i - 1][j + 1] + dp[i][j - 1]) % MOD; } } } for (int i = 0; i <= n; i++) { if (dp[n][i]) { return dp[n][i]; } } return -1; } int main() { cin >> (s + 1); n = strlen(s + 1); LL l = solve(); reverse(s + 1, s + n + 1); for (int i = 1; i <= n; i++) { if (s[i] == ')') { s[i] = '('; } else { s[i] = ')'; } } LL r = solve(); cout << l * r % MOD << endl; return 0; }
队列
普通队列
先入先出的一种数据结构。基本操作过于简单，就不说了。
循环队列
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int q[N], hh, tt, m;
int main() {
string op;
cin >> m;
int x;
while (m--) {
cin >> op;
if (op == "push") {
cin >> x;
q[tt++] = x;
if (tt == N) {
tt = 0;
}
} else if (op == "pop") {
hh++;
} else if (op == "empty") {
if (hh == tt) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
} else if (op == "query") {
cout << q[hh] << endl;
}
}
return 0;
}
单调队列
单调队列中存储的元素是某个数组a[]中的元素的下标。
单调队列维护的单调性是：从队头到队尾，对应的在序列a[]中的元素的值单调递增/递减。
双端队列
链表
本部分主要介绍如何使用数组模拟单链表与双链表。
TODO
Trie 字典树
早就学过但是一直没咋用过，所以掌握很垃圾。2021.5.10每日一题当天专门系统整理了下面的内容。
字典树是一个多叉树，又名Trie树，常用于处理字符串相关问题。传统的Trie有26个叉，分别代表字符a到z，而算法竞赛中使用Trie时一个很常用的用法就是01Trie，即只有表示0和1的两个儿子，且常用于贪心地处理异或问题。
Trie在竞赛中常用的存储方式的思路类似二叉树，其每个结点拥有记录指向其所有儿子的指针，除此之外其每个结点会标明以从根到自己的路径上的所有边组成的串是否是一个完整的串及其出现次数。当然，为了避免动态分配内存，一般在竞赛中我们使用内存池的方式去实现这个数据结构。这里需要注意，由于每个字符串中的每个字符都可能是之前树中没有的，且树中的边只能表达一个字符的信息，所以树中的结点个数最多是输入的总字符数而不是输入的字符串数。
以Trie字符串统计为例子，本题要求写一个数据结构，能够支持快速插入一个字符串，以及快速统计某个字符串出现的次数。使用字典树可以这样去实现：
#include <bits/stdc++.h>
using namespace std;
const int N = 2e4 + 9;
const int SIZE = 1e5 + 9;
int trie[SIZE][30], idx, cnt[SIZE], root;
bool ed[SIZE];
int n;
// 根节点和空结点用0表示
void insert(char str[]) {
int p = root;
for (int i = 0; str[i] != '\0'; i++) {
int ch = str[i] - 'a'; //算出来该走哪条边
if (trie[p][ch] == 0) { // 下个结点不存在就从内存池中分配一个
trie[p][ch] = ++idx;
}
p = trie[p][ch];
}
cnt[p]++;
}
int query(char str[]) {
int p = root;
for (int i = 0; str[i] != '\0'; i++) {
int ch = str[i] - 'a';
if (trie[p][ch] == 0) {
trie[p][ch] = ++idx;
}
p = trie[p][ch];
}
return cnt[p];
}
int main() {
char op[2], str[SIZE];
scanf("%d", &n);
int root = ++idx;
for (int i = 1; i <= n; i++) {
scanf("%s %s", op, str);
if (op[0] == 'I') {
insert(str);
} else {
printf("%d\n", query(str));
}
}
return 0;
}
这份代码中拥有几个值得探讨的细节：
- 本题中，我们使用了
cnt数组，来表示从根走到该结点的字符串曾经被插入的个数。可以注意到，我们只在最后一位增加了次数，原因就是防止出现前缀匹配的情况。比如空树中插入字符串abc，查询ab字符串的次数，虽然ab没有被插入过，但是它是之前插入的字符串的前缀，所以如果我们在插入时把路径上所有经过的结点的cnt值都增加的话，那么会出现上面的错误。类似地，如果中间结点不是终点但统计了次数，删除字符串时，可能也会出现插入了abc但是删除ab串却可以成功执行的错误情况。 - 实现
Trie树时，我们把1号结点当作初始根节点，并且以trie[i][j]存储的值为0来表示树上不能走这条边，所以idx应该使用前置加法。之所以使用1作为根，其原因会在可持久化数据结构中说明。
下面再专门介绍一下01Trie:
01Trie，常用来解决数的异或问题，且常用到贪心的思想去在树上走想要的路径（异或问题的贪心也不一定非得用到这个数据结构，有时候就是单纯统计每位1出现的奇偶）。这里常用的贪心一般是从高位到低位的贪心，为了保证正确性，一般我们要在前面补上前导0以保证对齐。
贪心地异或时，我们的思路是，先算一下当前自己的二进制位，然后看看这个位取反表示的那条边能不能走到合法结点，如果能走到，则下一位异或完就是1，结果res = 2 * res + 1。如果位取反表示的那条边不能走到合法结点，就只能走该位表示的边了，res = 2 * res。对于其他更复杂的路径信息，可能我们需要用path[N]数组才能记录下来，这个根据题意的不同而不同。
做异或问题的时候，01Trie面临一个很大的问题：如何删除结点。如果要硬上普通字典树的模板代码的话，会出现下面一个问题：直到贪心地走到叶子结点，我才发现这个串已经不合法了。为了解决这个问题，我们可以利用好所有数字二进制位数相同的性质，对路径上所有的结点都统计出现次数。由于每个数都是对齐存储的，所以我们完全不用担心上面提到的前缀的问题。这样我们可以每走一步就判断一下是不是能贪心的走，不能则走另一条路。只要树不是空的，那么一定就可以走到叶子，得到一个合法的答案。
仅仅使用上一段提到的技巧会引入新的问题：如何正确的判断某个结点是否是存在的。如果仍然判断trie[i][j]是否为0的话，考虑插入一个数之后把它删除，其虽然不存在了，但是trie[i][j]也已经不是0了。为了解决这个问题，我们应该通过cnt[trie[i][j]]来判断某个结点是否有效。
做异或问题时还容易遇到一些其他的细节问题，比如如果要求区间异或的一些东西，我们可能会想到把区间异或转化为前缀异或。做前缀的话，首先要在树中插入s[0]，否则在查询的时候01Trie不能正常工作。
并查集
并查集是一种树形数据结构。
普通并查集
普通并查集支持快速维护一系列集合之间的合并操作与查询是否在同一个集合中的操作。普通并查集之所以快，是因为有路径压缩（各个子节点直接连到根节点上，很短很好写）与按秩合并（让小的集合合并到大的集合中，需要额外维护集合大小）两种优化。
确实没什么好说的。
带权并查集
带权并查集中，每个结点除了维护fa[x]以外，还要维护一个和fa[x]之间相连的边的权值d[x]。
这个d[x]的意义随题目要求的不同而不同。一个典型的例子是在保证原顺序合并的情况下维护x到fa[x]的距离。
通常，在调用find操作之后，fa[x]都会变成最终的根，所以d[x]也应该在find的过程中被更新成x到新的 fa[x]（即最终的根）的距离，且我们还可能要维护集合的大小sz[x]。而我们使用d[x]的值的时候，一般也是在调用完find之后（毕竟只是记录随便一个fa[x]的也没啥使用价值）。
通过使用**find之后的d[x]**（即x到根的d[x]），可以高效维护同一个集合中的任意两个元素之间的”关系“。
带权并查集维护的本质上是一个相对关系。
拿一个例题来看吧：奇偶游戏
题目大意是有一个长度为n的01序列，m条已知信息，每条信息回答了这个序列的[l, r]中存在的1的个数是奇数还是偶数。这些信息可能会互相矛盾，故需要我们找出第一次出现矛盾的那条信息。
分析一下题目，使用前缀和的思想，将区间信息转化成前缀s[l - 1]和s[r]之间的关系，显然，[l, r]中有奇数个1，则s[l - 1]和s[r]奇偶性不同，否则则相同。并且容易发现，只要满足奇偶关系不出矛盾，就能构造出一个合法的原序列；奇偶关系出现问题则信息一定自相矛盾。所以判定信息是否自相矛盾只要判定奇偶关系是否自相矛盾即可。
注意到，如果知道s[i]和s[j]的关系，以及s[j]和s[k]的关系，假如关系具有传递性，那么我们可以直接推导出s[i]和s[k]之间的关系，所以我们可以维护若干个集合，维护集合中每个元素和其集合代表元之间的关系（同奇偶或不同）。这样在给出位于同一个集合中的两个元素的关系的时候，我们可以检查推导结果和给出的结果是否矛盾；若两个元素不在同一个集合中，说明根据前面的条件不足以完成推导，此时可以进行集合合并，在合并的时候需要注意合并时增加的那条边的边权是多少，这是通过我们当前这条给定的信息确定的。
在本题中，我们可以这样处理：
-
我们规定，
d[x]表示x和fa[x]的关系。在本题中存在两种关系：同奇偶性或者不同，其中同奇偶性可以用0表示，不同可以用1表示。 -
如果给出的当前信息说明
l - 1和r奇偶相同- 如果
l - 1和r当前在同一个集合中，先让l - 1和r都指向根，并维护途中遇到的d[x]，然后检查d[l - 1]和d[r]，如果d[l - 1] ^ d[r] == 0，则无矛盾，否则有矛盾 - 如果
l - 1和r不在同一个集合中，说明目前无法推导出二者的关系，所以合并两个集合。由于l - 1和r奇偶性相同，所以我们希望d[x] ^ d[y] ^ new relation == 0，解得new relation = d[x] ^ d[y]，所以合并的时候加入的新的边权为d[x] ^ d[y]
- 如果
-
如果给出的当前信息说明
l - 1和r奇偶不同，类比相同的情况，不难发现应该怎么维护。
本题数据范围较大，所以还需要离散化，偷懒可以使用哈希表在线离散化。
#include <bits/stdc++.h>
using namespace std;
const int N = 10010;
typedef pair<int, int> PII;
int d[N], fa[N], n, m, idx;
unordered_map<int, int> h;
// 在线离散化
int get(int x) {
if (!h.count(x)) {
h[x] = ++idx;
}
return h[x];
}
int find(int x) {
if (fa[x] != x) {
int root = find(fa[x]);
// 调用了find(fa[x])之后，fa[fa[x]]已经是最终的根了
// d[fa[x]]此时就是从fa[x]到最终的根的关系
// 这个时候使用d[fa[x]]更新d[x]，就可以让d[x]也表示x到最终的根的关系
d[x] ^= d[fa[x]];
fa[x] = root;
}
return fa[x];
}
int main() {
cin >> n >> m;
for (int i = 0; i <= 2 * m; i++) {
fa[i] = i;
}
int a, b, res = 0;
string opt;
for (int i = 1; i <= m; i++) {
cin >> a >> b >> opt;
int x = get(a - 1), y = get(b);
if (opt == "even") {
// 必须先让x和y的父亲都变成根，不然使用的d[x]和d[y]意义不大
int px = find(x), py = find(y);
if (px != py) {
fa[px] = py;
d[px] = d[x] ^ d[y];
res++;
} else {
if (d[x] ^ d[y] != 0) {
break;
} else {
res++;
}
}
} else {
int px = find(x), py = find(y);
if (px != py) {
fa[px] = py;
d[px] = 1 ^ d[x] ^ d[y];
res++;
} else {
if (d[x] ^ d[y] != 1) {
break;
} else {
res++;
}
}
}
}
cout << res << endl;
return 0;
}
带权并查集也可以解决更多更复杂的关系，比如食物链 。思考方式和奇偶游戏完全相同，只不过本题需要维护模3意义下的3种关系。
扩展域并查集
TODO，还没看懂啥意思。
二叉堆
二叉堆分为大根堆和小根堆两种，两种都是完全二叉树。
以大根堆为例子，大根堆满足：对于所有结点来说，其存储的值一定不小于其两个儿子结点存储的值。
二叉堆的传统操作有查询堆顶，插入一个数以及删除堆顶。一般的实现方法是使用数组模拟堆，插入删除都是在堆的“尾部”进行（不是的话则交换到尾部），然后通过向上或者向下调整来保持二叉堆的性质。
基本的堆操作已经在《基础技巧》一文记录过，所以下面介绍点不一样的。
支持修改和随机删除的堆
TODO 一般不用实现这个需求。
对顶堆
维护一个大顶堆和一个小顶堆，二者适时交换一些元素，这样可以实现动态维护中位数等操作。
STL priority_queue的使用
priority_queue 默认是大根堆。
常用的操作如下：
priority_queue<Type> q; 创建一个内部存储Type类型的堆，且是大根堆
q.empty() q.top() q.pop() q.push(element) 测试是否为空，看堆顶而不取，弹出堆顶，插入元素
bool operator<(const Type &a, const Type &b) {
// return something
} 重载运算符以实现小根堆，把‘<’的行为定义成‘>’的
插入相反数元素也可以实现小根堆，记得取出来之后取反就好了
对于已经定义了大小关系的Type，可以使用 priority_queue<Type, vector<Type>, greater<Type> > 来实现小根堆
哈希表
哈希表在算法竞赛中常用两种处理哈希冲突的方式：拉链法与线性探测法。
拉链法
对于拉链法，其思路就是把相同的哈希值的元素串成链表，这样看起来就像一个邻接表，所以我们可以照搬存图的那一套做法，使用静态邻接表存储哈希表，首先通过哈希函数计算出该挂到哪个结点上，然后再挂上去。在查找的时候，也是先算出来它在哪个结点挂着，然后遍历那条链表即可。图的建立和遍历的代码大家都已经写习惯了，所以一般情况下写拉链法更不容易写错，尤其是在很久没实现过哈希的时候。
拉链法的代码实现：
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int mod = 100003;
typedef struct {
int to, ne;
} Edge;
Edge edge[2 * N];
int h[N], head[N], cnt, n;
void add(int x, int y) {
edge[cnt].to = y;
edge[cnt].ne = head[x];
head[x] = cnt++;
}
bool query(int u, int x) {
for (int i = head[u]; i >= 0; i = edge[i].ne) {
int j = edge[i].to;
if (x == j) {
return true;
}
}
return false;
}
int main() {
cin >> n;
memset(head, -1, sizeof head);
string opt;
int x;
for (int i = 1; i <= n; i++) {
cin >> opt >> x;
if (opt == "I") {
int u = (x % mod + mod) % mod;
add(u, x);
} else {
int u = (x % mod + mod) % mod;
if (query(u, x)) {
puts("Yes");
} else {
puts("No");
}
}
}
return 0;
}
线性探测法
本方法的思路是，遇到冲突之后，顺延往后找空位，遇到第一个空位便放下。
在查询时，先在哈希值处查找，查找失败则往后顺延查找，直到遇到空位，说明没找到。
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
const int mod = 100003;
int h[N], n;
void add(int u, int x) {
if (h[u] == -1) {
h[u] = x;
} else if (h[u] == x) {
return;
} else {
for (int i = u; ; i++) {
if (i == N) i = 0;
if (h[i] == -1) {
h[i] = x;
return;
} else if (h[i] == x) {
return;
}
}
}
}
bool query(int u, int x) {
if (h[u] == x) return true;
for (int i = u; h[i] != -1; i++) {
if (i == N) i = 0;
if (h[i] == x) return true;
}
return false;
}
int main() {
cin >> n;
memset(h, -1, sizeof h);
string opt;
int x;
for (int i = 1; i <= n; i++) {
cin >> opt >> x;
if (opt == "I") {
int u = (x % mod + mod) % mod;
add(u, x);
} else {
int u = (x % mod + mod) % mod;
if (query(u, x)) {
puts("Yes");
} else {
puts("No");
}
}
}
return 0;
}
下面再介绍一下将比较一般化的信息转化成整数信息的字符串哈希。
字符串哈希
字符串哈希是将字符串转化为整数的一种思想。
常用的字符串哈希是P进制自然溢出字符串哈希。这个的原理是将字符串看成一个P进制数，然后每个字符映射到一个正整数上。一般地，取P = 131或者13331，这个时候产生哈希冲突的概率非常低，可以认为无冲突。
由于ASCII码总共也就255个，所以取P = 13331，且取所有的字符映射到的整数为其ASCII码 + 1，可以满足P进制数的要求。
在计算字符串的哈希值时，我们采用类似快读的处理方法，即假如串的哈希值为，则后面加上字符之后得到的串的哈希值为。
由于最后得到的哈希值可以看成是一个P进制数，所以只要预处理出字符串所有前缀的哈希值，那么可以快速求出字符串任意一个子串的哈希值，具体操作是：假设已知字符串的哈希值是，的哈希值为，加号代表拼接操作，那么的哈希值可以这样求：先把后面补P进制数0，直到位数和相同（即P进制意义下左移位），此时得到的哈希值是，那么就是T的哈希值了。
由于计算机存储数字的位数有限，所以哈希值一般是要对一个数取模的。如果我们取 ，那么如果我们使用unsigned long long存储哈希值的话，就不用显式进行取模了。
上面两个步骤加起来，就叫做P进制自然溢出字符串哈希。
代码实现如下：
#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const int N = 100010;
const ull P = 13331;
char s[N];
int n, m;
ull h[N];
ull get(int len) {
ull res = 0;
if (len == 1) {
// 必须保证正整数，不然对于a...a这种串会无法区分
res = s[1] + 1;
} else {
res = P * h[len - 1] + s[len] + 1;
}
return res;
}
void pre() {
for (int i = 1; i <= n; i++) {
h[i] = get(i);
}
}
ull quick_power(ull a, ull b) {
ull base = a, res = 1;
while (b) {
if (b & 1) {
res *= base;
}
base *= base;
b >>= 1;
}
return res;
}
int main() {
cin >> n >> m;
cin >> (s + 1);
pre();
int l1, r1, l2, r2;
for (int i = 1; i <= m; i++) {
cin >> l1 >> r1 >> l2 >> r2;
ull str1 = h[r1] - h[l1 - 1] * quick_power(P, r1 - l1 + 1);
ull str2 = h[r2] - h[l2 - 1] * quick_power(P, r2 - l2 + 1);
if (str1 == str2) {
puts("Yes");
} else {
puts("No");
}
}
return 0;
}
自然溢出可能会被卡，所以改变一下模数，使用比较大比较著名的质数作为模数，比如那位大人的生日19260817，998244353等。
字符串哈希的真正威力似乎在于在不写其他字符串算法的情况下骗部分分：
- 在字符串匹配时，可以直接预处理主串的所有前缀的哈希值，预处理模式串的哈希值，然后枚举主串中长度等于模式串的字符串，快速计算出哈希值，就基本可以判断这一段是不是等于模式串了。如果怕自然溢出被卡掉，可以尝试一下其他模数或者双哈希。
STL map和unordered_map的使用
其实也没有太多可以说的。
map 是基于红黑树实现的，unordered_map 则是基于 hash 实现的，二者提供的基本的增删改查函数都一样，所以只要把声明中的 map 和 unordered_map 换一下即可。不过 map 中有一些用到平衡树特性的函数，这些就不能给 unordered_map 使用了。
map 的遍历需要使用迭代器：
for (map<int, int>::iterator i = h.begin(); i != h.end(); i++) {
printf("%d ", i -> second); // i -> second是值，i -> first是键
}
清空 map 中的所有键值对：
map<int, int> a;
a.clear();
字符串
kmp字符串匹配
原理与代码模板
kmp算法的核心：每次失配的时候，模式串的某个子串和模板串的某个前缀是相等的。
考虑模式串 abcabd 和模板串 abd，下标从 0 开始算，那么可以注意到最开始会在 2 处发现不相等，即：
abcabd
abd
按理说下次应该这样匹配：
abcabd
abd
但是显然这个上来就会错，这样的原因是没有从上一次匹配失败中吸取教训。
如果要吸取教训，我们要如何吸取呐？注意到每次失配的时候，模式串的某个子串和模板串的某个前缀是相等的。而下次匹配的时候，为了最大化利用这个信息，我们需要知道这个前缀串自身的前缀和后缀最多能重合多少。下次匹配的时候，我们就把模板串往后移动到和他重合的最长后缀的位置即可最大化利用这个信息。
对于模板串的每个前缀串最多能和这个前缀串的多长的后缀串重合这个信息（特别的，不能是整个串等于整个串），可以预处理出来。
假设我们预处理出来了，那么我们每次就可以往后尽可能多且有效的跳，尽可能地去匹配成功，能够证明匹配复杂度是 的。
我们从下标 1 开始存储字符串，假设模式串 s 的长度为 m ，模板串 p 长度为 n，则匹配过程可以这样实现：
for (int i = 1, j = 0; i <= m; i++) {
while (j && s[i] != p[j + 1]) {
j = ne[j]; // 把整根模板串往右平移
}
if (s[i] == p[j + 1]) {
j++; // 匹配则看模板串和模式串的下一位，此处是后移模板串指针
}
if (j == n) {
// 匹配成功
j = ne[j];
}
}
解释：ne[i] 表示模板串 p 的以 i 结尾的非前缀子串 p[k ... i] 和 p 的前缀能够匹配的最长长度，或者说是 p[1 .. i] 的后缀（不包含整个串）和 p[1 .. i] 的前缀最大相等长度。
使用图解这段代码就是：
下面回到前面的一个问题，咋预处理前缀串的前后缀相等信息？一个朴素的方法是，枚举每个前缀串，然后对于每个前缀串，暴力枚举前后缀，看看是不是相等的，从长向短枚举，遇到的第一个相等的就是最长的重合的，这样假设模板串长度为 ，则复杂度是 ，在 比较大的时候就不好用了。
在求 ne[i] 的时候，我们完全可以使用前面计算出来的 ne[1...i - 1] 。具体思路是考虑 p 和自己的前缀做匹配：
for (int i = 2, j = 0; i <= n; i++) {
// 这一段和匹配时的意义一样
// i从2开始是因为要保证ne[1] = 0
while (j && p[i] != p[j + 1]) {
j = ne[j];
}
if (p[i] == p[j + 1]) {
j++;
}
// 如果发现匹配上了一个字符，说明ne[i] = j
// 否则，说明j = 0退出来的，所以ne[i] = 0
ne[i] = j;
}
对ne数组的深入理解与灵活运用
为了充分理解kmp算法的 ne[] 数组以及移动规则，可以做一下这个题目3823. 寻找字符串 - AcWing题库
本题考察对 ne[] 数组的理解。
在 kmp 算法中，ne[i] 表示对于串 s[1 ... i] 来说，其最长的和前缀相等的后缀的长度是 ne[i]。
所以如果本题没有必须要在非前后缀位置出现过的话，那么最长的就是 s[1 ... ne[n]]
但是本题有上述条件，所以就没法直接拿到答案了，要尝试一遍所有可能的前后缀。
考虑一下如何快速求出来相等的前后缀，这个其实是 kmp 算法中的内容。回忆 kmp 算法，当 s[i] != s[j + 1] 的时候，我们令 j = ne[j]，其意义便是往后移动一下字符串，直到现在的 j 的 ne[j] 和 i - 1对齐，这一步便是快速求出来 s[1 ... j] 的最长前后缀。所以枚举相等的前后缀，只需要不断往前找 ne就好了：
for (int i = ne[n]; i > 0; i = ne[i]) {
}
下面考虑怎么快速判断我们上面枚举的串在中间某个位置出现过。
因为是判断其是否在中间出现过，所以它不是后缀（这不废话嘛），假设这个后缀的长度为 len，我们想一下，假设在子串 s[1 .. k], 1 <= k < n中，ne[k] = len，那么就说明 s[1 ... k] 的最长前后缀长度是 len，所以 s[1 ... len] 等于 s[k - len + 1... k]，而 k < n，所以这就说明 s[k - len + 1 .. k] 就是在中间出现的情况。为了快速判断这一点，使用 hash 即可。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 9;
char s[N];
int T, ne[N], n;
bool st[N];
int main() {
scanf("%d", &T);
while (T--) {
scanf("%s", s + 1);
n = strlen(s + 1);
for (int i = 2, j = 0; i <= n; i++) {
while (j && s[i] != s[j + 1]) {
j = ne[j];
}
if (s[i] == s[j + 1]) {
j++;
}
ne[i] = j;
}
memset(st, 0, sizeof st);
for (int i = 1; i < n; i++) {
st[ne[i]] = true;
}
int res = 0;
for (int i = ne[n]; i > 0; i = ne[i]) {
if (st[i]) {
res = i;
break;
}
}
if (!res) {
printf("not exist\n");
} else {
for (int i = 1; i <= res; i++) {
printf("%c", s[i]);
}
puts("");
}
}
return 0;
}