2. 数据结构（I）
2.1 链表
2.1.1 单链表
题目：
实现一个单链表，实现以下 \(3\) 种操作：
H x向链表头插入一个数 \(x\)；D x删除第 \(x\) 个插入的数（若 \(x=0\)，表示删除头结点）；I k x在第 \(k\) 个插入的数后插入一个数 \(x\)（保证 \(k>0\)）。
给你 \(m\) 次操作，输出最终链表。\(1\le m\le 10^5\)。
思路：
我们定义，\(\texttt{head}\) 指向头结点，数组 \(e\) 存储每个点的值，数组 \(ne\) 存储每个点的后继，\(idx\) 表示当前节点编号。初始时，\(\texttt{head}=-1,idx=0\)。
图2-1
如图 \(\texttt{2-1}\) 展示了一个链表。其中，\(\texttt{head}\) 指针指向头结点。然后我们来思考如何实现 \(3\) 种操作。
图2-2
如图 \(\texttt{2-2}\) 展示了操作 H x 的方式。将 \(e_{idx}\) 设为 \(x\)，\(ne_{idx}\) 设为 \(\texttt{head}\)，然后让 \(\texttt{head}\) 指向 \(idx\)，最后 \(idx:=idx+1\)。
图2-3
如图 \(\texttt{2-3}\) 展示了删除在 \(x\ne 0\) 时的删除操作 D x 的方式，即将 \(ne_{x-1}:=ne_{ne_{x-1}}\) 即可。
删除头结点也可以用类似的方法。
图2-4
如图 \(\texttt{2-4}\) 展示了操作 I k x 的方式。即先将 \(e_{idx}\) 设为 \(x\)，\(ne_{idx}=ne_k\)，\(ne_k=idx\)，最后 \(idx:=idx+1\)。
最后输出时，从头结点开始遍历，直到 \(ne_i=-1\) 标志着链表结束。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int m;
int e[N], ne[N], head, idx;
void add_head(int x) { //头插入(图2.2)
e[idx] = x, ne[idx] = head, head = idx, idx ++;
}
void add(int k, int x) { //中间插入(图2.4)
e[idx] = x, ne[idx] = ne[k], ne[k] = idx, idx ++;
}
void del_head() { //删除头结点
head = ne[head];
}
void del(int k) { //删除中间节点(图2.3)
ne[k] = ne[ne[k]];
}
int main() {
scanf("%d", &m);
head = -1, idx = 0; //初始化
while (m -- ) {
char op;
cin >> op;
if (op == 'H') { //头插入
int x;
scanf("%d", &x);
add_head(x);
} else if (op == 'D') { //删除节点
int x;
scanf("%d", &x);
if (x == 0) del_head();
else del(x-1); //注意删掉的是x-1而非x
} else { //中间插入
int k, x;
scanf("%d%d", &k, &x);
add(k-1, x);
}
}
for (int i = head; i != -1; i = ne[i]) printf("%d ", e[i]);
return 0;
}
2.1.2 双链表
题目：
实现一个双链表，实现以下 \(5\) 种操作：
L x向链表头插入一个数 \(x\)；R x向链表尾插入一个数 \(x\)；D x删除第 \(x\) 个插入的数；IL k x在第 \(k\) 个插入的数左侧插入一个数 \(x\)；IR k x在第 \(k\) 个插入的数右侧插入一个数 \(x\)。
给你 \(m\) 次操作，输出最终链表。\(1\le m\le 10^5\)。
思路：
我们定义，\(e\) 数组存储每个节点的值，\(l\) 数组存储每个节点的左侧节点，\(r\) 数组存储每个节点的右侧节点，\(idx\) 表示已使用的节点的编号。方便起见，不妨设 \(0\) 号节点为链表的头结点，\(1\) 号节点为链表的尾结点。那么显然有 \(r_0=1,l_1=0\)，初始时 \(idx=2\)。
仿照单链表，考虑插入操作 IR k x：
首先将第 \(idx\) 个节点赋值为 \(x\)。 然后更新 \(idx\) 的左右节点，即 \(l_{idx}=k,r_{idx}=r_{l_{idx}}\)。 再更新 \(r_{idx}\) 的左侧节点为 \(idx\)，\(l_{idx}\) 的右侧节点为 \(idx\)。
插入操作 IL k x 也可以视作在 \(l_k\) 右侧插入节点，即 IR l[k] x. L x 可以视作在 \(0\) 号节点右侧插入节点，即 IR 0 x；同理 R x 可视作在 \(1\) 号节点左侧插入节点，即 IR l[1] x.
最后考虑删除操作 D x. 显然 \(l_{r_x}:=l_x,r_{l_x}:=r_x\)。
最后从 \(r_0\) 节点开始遍历所有节点，直到遍历到 \(1\) 号节点标志着链表结束。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int m;
int e[N], l[N], r[N], idx;
//e数组存储每个节点的值,l数组存储每个节点左侧节点的编号,r节点存储每个节点右侧节点的编号
void add(int k, int x) {
e[idx] = x; //将idx号点的值设为x
l[idx] = k, r[idx] = r[k]; //更新idx的左右节点
l[r[k]] = idx, r[k] = idx; //更新idx的左节点的右节点和右节点的左节点
idx ++;
}
void del(int k) {
l[r[k]] = l[k];
r[l[k]] = r[k];
}
int main() {
scanf("%d", &m);
r[0] = 1, l[1] = 0, idx = 2; //0表示头结点,1表示尾结点
while (m -- ) {
string op;
cin >> op;
if (op == "L") {
int x;
scanf("%d", &x);
add(0, x); //在头节点插入
} else if (op == "R") {
int x;
scanf("%d", &x);
add(l[1], x); //在尾结点插入
} else if (op == "D") {
int x;
scanf("%d", &x);
del(x+1); //删除第x个插入的数
} else if (op == "IR") {
int k, x;
scanf("%d%d", &k, &x);
add(k+1, x); //在第k个插入的数右侧插入x
} else {
int k, x;
scanf("%d%d", &k, &x);
add(l[k+1], x); //在第k个插入的数左侧插入x,相当于在l[k]右侧插入x
}
}
for (int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);
return 0;
}
2.2 栈
2.2.1 模拟栈
题目：
实现一个栈，支持以下 \(4\) 种操作：
push x向栈顶插入一个数 \(x\)；pop从栈顶弹出一个元素；empty判断栈是否为空；query查询栈顶元素。
给你 \(m\) 次操作。对于每次 empty 或 query 操作，输出对应结果。\(1\le m\le 10^5\)。
思路：
栈是一种先进后出的数据结构。
我们可以维护一个头指针 \(tt\)，指向栈顶的下一个位置（初始时 \(tt=1\)）；同时维护 \(q\) 数组表示栈。
对于每次 push 操作，将 \(x\) 的值赋给 \(q_{tt}\) 即可，然后 \(tt:=tt+1\)。
对于每次 pop 操作，将 \(tt\) 减少 \(1\) 即可。
对于每次 empty 操作，若 \(tt=1\) 说明栈空，否则栈不空。
对于每次 query 操作，输出 \(q_{tt-1}\) 即可。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 100010;
int m;
int tt = 1; //尾指针
int q[N]; //栈
int main() {
scanf("%d", &m);
while (m -- ) {
string op;
cin >> op;
if (op == "push") {
int x;
scanf("%d", &x);
q[tt ++] = x; //向栈顶插入元素
}
else if (op == "pop") tt --; //弹出栈顶元素
else if (op == "empty") { //判断栈是否为空
if (tt == 1) puts("YES");
else puts("NO");
}
else printf("%d\n", q[tt-1]); //输出栈顶元素
}
return 0;
}
题目：给你一个表达式，其中的符号只包含 +，-，*，/ 和左右括号，计算它的值。表达式的长度不超过 \(10^5\)。
思路：
开两个栈，分别存储运算数和运算符。然后扫描整个表达式：
- 若当前字符为数字，则提取出整个数，加入运算数栈中。
- 若当前字符为
(，直接加入运算符栈中。 - 若当前字符为
)，计算括号内表达式的值，将其结果加入运算数栈中。 - 若当前字符为四则运算符，将运算符栈顶的运算符与当前字符比较，若当前字符的优先级较高，则直接加入运算符栈中；否则计算之前表达式的值，再将当前字符入栈。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <unordered_map>
using namespace std;
stack<int> nums;
stack<char> op;
void eval() { //计算中缀表达式的值
int b = nums.top(); nums.pop();
char oper = op.top(); op.pop();
int a = nums.top(); nums.pop();
int c;
if (oper == '+') c = a + b;
else if (oper == '-') c = a - b;
else if (oper == '*') c = a * b;
else c = a / b;
nums.push(c);
}
int main() {
string s;
cin >> s;
unordered_map<char, int> pr{{'+', 1}, {'-', 1}, {'*', 2}, {'/', 2}}; //每个符号的运算优先级
for (int i = 0; i < s.size(); ++i) {
char c = s[i];
if (isdigit(c)) {
int x = 0; //提取出操作数x
while (isdigit(s[i]) && i < s.size()) {
x = x * 10 + s[i] - '0';
i ++;
}
i --;
nums.push(x);
}
else if (c == '(') op.push(c);
else if (c == ')') { //如果是右括号,从右向左计算出整个括号的值
while (op.top() != '(' && op.size()) eval();
op.pop();
}
else { //如果是运算符,那么按运算顺序计算
while (op.size() && op.top() != '(' && pr[op.top()] >= pr[c]) eval();
op.push(c);
}
}
while (op.size()) eval(); //求出最终表达式的值
cout << nums.top() << endl;
return 0;
}
2.2.2 单调栈
题目：给你一个包含 \(n\) 个元素的数组 \(a\)，输出每个数左边比它小的第一个数，如果没有则输出 \(-1\)。 \(1\le n\le 10^5\)。
思路：
首先，我们知道一个结论：若 \(a_i>a_j\) 且 \(i<j\)，那么 \(a_i\) 对 \(a_j\) 以后的答案没有影响。证明：对于 \(a_k\;(k>j)\)，若 \(a_i<a_k\)，则 \(a_j\) 必定比 \(a_i\) 更优；若 \(a_i\ge a_k\) 则 \(a_i\) 不可能为答案。
结合上述结论，我们可以维护一个单调栈 \(\texttt{nums}\)。 对于每个元素 \(a_i\)，若 \(\texttt{nums}\) 则输出 \(-1\)。 否则从栈顶开始遍历每个元素，若栈顶元素大于 \(a_i\) 则将其弹出，直到栈顶元素小于 \(a_i\) （输出此时的栈顶元素）或栈为空（输出 \(-1\)）。最后将 \(a_i\) 压入栈即可。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
using namespace std;
int n;
stack<int> nums; //单调栈
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
int x;
scanf("%d", &x);
if (!nums.size()) printf("-1 "); //栈为空
else {
while (nums.size() && nums.top() >= x) nums.pop(); //找到第一个<x的元素
if (!nums.size()) printf("-1 ");
else printf("%d ", nums.top());
}
nums.push(x); //将x加入栈
}
return 0;
}
2.3 队列
2.3.1 模拟队列
题目：
实现一个队列，支持以下 \(4\) 种操作：
push x向队尾插入一个数 \(x\)；pop从队头弹出一个元素；empty判断队列是否为空；query查询队头元素。
给你 \(m\) 次操作。对于每次 empty 或 query 操作，输出对应结果。\(1\le m\le 10^5\)。
思路：
维护一个数组 \(q\) 和两个指针 \(hh\) 和 \(tt\)，分别指向队头和队尾。初始时 \(hh=tt=0\)。
对于 push x 操作，令 \(q_{tt}=x,tt:=tt+1\) 即可；对于 pop 操作，\(hh:=hh+1\)即可；对于 empty 操作，若 \(hh=tt\) 说明队列为空，否则说明队列不空；对于 query 操作，输出 \(q_{hh}\) 即可。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int m;
int hh, tt; //hh指向队头,tt指向队尾
int q[N]; //模拟队列
int main() {
scanf("%d", &m);
while (m -- ) {
string op;
cin >> op;
if (op == "push") {
int x;
scanf("%d", &x);
q[tt ++] = x; //队尾插入
}
else if (op == "pop") hh ++; //弹出队头
else if (op == "empty") { //判断是否为空
if (hh == tt) puts("YES");
else puts("NO");
}
else printf("%d\n", q[hh]); //询问队头
}
return 0;
}
2.3.2 单调队列
题目：给定一个长度为 \(n\) 的数组和一个长度为 \(k\) 的滑动窗口。滑动窗口从数组的最左侧移动到最右侧，你需要求出每次滑动窗口内的最小值和最大值。\(1\le k\le n\le 10^6\)。
思路：
维护一个单调队列 \(q\)（其中存储的是原数组的下标），初始时，\(hh=0,tt=-1\)。 这里以最小值为例，遍历整个数组，对于 \(a_i\)，若：
- 若队头 \(q_{hh}\le i-k\)，说明此时队头已超出窗口范围，弹出队头；
- 弹出队尾，直到 \(a_i>a_{q_{tt}}\)；
- 将 \(i\) 加入队列；
- 输出队头，即滑动窗口内的最小值。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int n, k, hh, tt;
int a[N], q[N]; //q存储的是原数组下标
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
hh = 0, tt = -1; //初始化队头队尾
for (int i = 1; i <= n; ++i) {
if (hh <= tt && q[hh] <= i-k) hh ++; //如果队头超出了滑动窗口的范围则将其弹出
while (hh <= tt && a[q[tt]] >= a[i]) tt --; //弹出队尾直到ai能够加入队列
q[++ tt] = i; //将t加入队列
if (i >= k) printf("%d ", a[q[hh]]); //输出队头(最小值)
}
puts("");
hh = 0, tt = -1; //与求最小值基本一致
for (int i = 1; i <= n; ++i) {
if (hh <= tt && q[hh] <= i-k) hh ++;
while (hh <= tt && a[q[tt]] <= a[i]) tt --;
q[++ tt] = i;
if (i >= k) printf("%d ", a[q[hh]]);
}
return 0;
}`
2.4 KMP 字符串算法
题目：给定一个长度为 \(m\) 的匹配串 \(S\) 和一个长度为 \(n\) 的模式串 \(P\)，求出 \(P\) 在 \(S\) 中所有出现位置的起始下标。\(1\le n\le 10^5,1\le m\le 10^6\)。
思路：
约定：本题中字符串的下标均从 \(1\) 开始。
首先定义 \(ne\) 数组：\(ne_{i}\) 表示 \(P[1\cdots i]\) 的最长公共前后缀的长度，且 \(ne_i<i\)。 特别地，\(ne_1=0\)。
然后我们来思考如何求出 \(ne_i\)。
图2-5
如图 \(\texttt{2-5}\) 展示了 \(ne\) 数组的计算方式。设 \(ne_{i-1}=j\)，若 \(P_{j+1}=P_i\)，根据 \(ne\) 数组的定义，有 \(P[1\cdots j]=P[i-j\cdots i-1]\)， 那么 \(ne_{i}=j+1\)；否则再尝试将 \(ne_j\) 与 \(i\) 进行匹配，直到无法匹配为止。
得到 \(ne\) 数组后，就可以进行 \(\texttt{KMP}\) 字符串匹配。
图2-6
如图 \(\texttt{2.6}\) 展示了 \(\texttt{KMP}\) 字符串匹配的方式。假设 \(S[i-j\cdots i-1]\) 和 \(P[1\cdots j]\) 已经匹配，若 \(S_i=P_{j+1}\) 则继续匹配；否则 \(j=ne_j\)，继续尝试匹配。若全部匹配成功，输出 \(i-n\) 即可。
时间复杂度 \(O(n+m)\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10, M = 1e6+10;
int n, m;
char p[N], s[M]; //模式串和匹配串
int ne[N]; //ne[i]存储p中第i个字符的最长公共前后缀长度
int main() {
cin >> n >> p+1 >> m >> s+1;
ne[1] = 0;
for (int i = 2, j = 0; i <= n; ++i) { //求出ne数组
while (j && p[i] != p[j+1]) j = ne[j];
if (p[i] == p[j+1]) j ++;
ne[i] = j;
}
for (int i = 1, j = 0; i <= m; ++i) { //kmp 字符串匹配
while (j && s[i] != p[j+1]) j = ne[j];
if (s[i] == p[j+1]) j ++;
if (j == n) {
printf("%d ", i-n);
j = ne[j];
}
}
return 0;
}
2.5 Trie 树
2.5.1 字典 Trie
题目：
维护一个字符串集合，支持两种操作：
I s插入一个字符串 \(s\)；Q s询问字符串 \(s\) 出现的次数。
给你 \(n\) 次操作。\(1\le n\le 2\times 10^4,1\le \text{len}(s)\le 10^5\) 且 \(s\) 中只包含小写字母（\(\text{len}(s)\) 表示 \(s\) 的长度）。
思路：
维护一棵 \(\texttt{Trie}\) 树（字典树）。
如果现在有 \(8\) 个字符串：\(\texttt{abcd,aacd,aabc,aabc,acd,bb,bbc,cdab}\)，那么它们所构成的 \(\texttt{Trie}\) 树如图 \(\texttt{2.7}\)：
图2-7
其中，\(idx\) 表示每个节点的编号，\(cnt_i\) 表示以第 \(i\) 个节点为结尾的字符串的数量。另外我们还需要维护一个数组 \(son\)，\(son_{i,j}\) 存储 \(i\) 号节点的第 \(j\) 个儿子的编号。
对于每次插入操作，从根节点开始遍历，若某个节点不存在则将其加入 \(\texttt{Trie}\) 树。对于每次查找操作，从根节点开始遍历，若某个节点不存在则直接返回 \(0\)。
时间复杂度 \(O(n\log n)\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n;
int son[N][26], cnt[N], idx; //son存储节点编号,cnt存储每个节点的数量
//0号节点既是根节点,也是空节点
void insert(string s) { //插入一个字符串s
int p = 0; //从根节点开始遍历
for (int i = 0; i < s.size(); ++i) {
int u = s[i] - 'a';
if (!son[p][u]) son[p][u] = ++ idx; //如果该节点不存在,则插入新节点
p = son[p][u];
}
cnt[p] ++;
}
int query(string s) { //查询s出现的次数
int p = 0;
for (int i = 0; i < s.size(); ++i) {
int u = s[i] - 'a';
if (!son[p][u]) return 0; //如果该节点不存在,直接返回0
p = son[p][u];
}
return cnt[p];
}
int main() {
scanf("%d", &n);
while (n -- ) {
char op; string s;
cin >> op >> s;
if (op == 'I') insert(s);
else cout << query(s) << endl;
}
return 0;
}
2.5.2 01 Trie
题目：给你 \(n\) 个整数 \(a_1,a_2,a_3,\cdots,a_n\)，找出一个数对 \((i,j)\)，使得 \(a_i\oplus a_j\) 最大。\(1\le n\le 10^5,0\le a_i\le 2^{31}\)。
思路;
异或运算 \(\oplus\) 相当于不进位的加法。我们可以构建一棵由 \(0\) 和 \(1\) 构成的 \(\texttt{Trie}\) 树，对于每个数 \(a_i\)，遍历 \(\texttt{01 Trie}\) 树找到与其异或的最大值即可。
例如，对于数组 \(a=[2,3,4,5,6]\)，由将其全部由二进制表示并插入 \(\texttt{01 Trie}\) 树，可得：
图2-8
以数 \(4\) 为例，演示通过 \(\texttt{01 Trie}\) 找到与 \(4\) 异或后的最大值：
图2-9
如图 \(\texttt{2.9}\)，\(4\) 异或后的最大值为 \(7\)。 那么如果找不到某一个数怎么办呢？以数 \(6\) 为例，演示通过 \(\texttt{01 Trie}\) 找到与 \(6\) 异或后的最大值：
图2-10
如图 \(\texttt{2-10}\)，\(6\) 异或后的最大结果为 \(5\)。
通过 \(\texttt{01 Trie}\)，可以将暴力 \(O(n^2)\) 的复杂度降至约 \(O(10^5\times 31)=O(3\times 10^6)\)。
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10, M = 3e6+10;
int n, a[N];
int son[M][2], idx; //son存储子节点
void insert(int x) { //将一个数x插入01Trie
int p = 0;
for (int i = 30; i >= 0; --i) {
int s = x >> i & 1;
if (!son[p][s]) son[p][s] = ++ idx; //如果子节点不存在,则创建新节点
p = son[p][s];
}
}
int query(int x) { //查询x的最大异或结果
int p = 0, res = 0;
for (int i = 30; i >= 0; --i) {
int s = x >> i & 1; //存储x的二进制表示的倒数第i+1位的数
if (son[p][!s]) res += 1 << i, p = son[p][!s];
else p = son[p][s];
}
return res;
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
insert(a[i]);
}
int maxl = 0;
for (int i = 1; i <= n; ++i) maxl = max(maxl, query(a[i]));
printf("%d\n", maxl);
return 0;
}
2.6 并查集
题目：
初始时一共有 \(n\) 个数 \(1\sim n\)，每个数都在各自的集合中。给你 \(m\) 次操作：
M a b表示将数 \(a\) 所在的集合和数 \(b\) 所在的集合合并；Q a b表示询问数 \(a\) 和数 \(b\) 是否在一个集合中。
\(1\le n,m\le 10^5\)。
思路：
并查集的思想是将每个集合视作一棵树，那么所有集合就可以视作一个森林。定义一个数组 \(p\)，存储每个数的父亲。初始时，所有节点的父亲都是自己，即 \(p_i=i\)。 另外我们定义一个函数 \(find(x)\)，表示寻找 \(x\) 的祖宗节点。
对于 M 操作，我们可以令 \(p_{find(a)}=find(b)\)，即将 \(a\) 的祖宗的父亲设为 \(b\) 的祖宗；对于 Q 操作，若 \(find(a)=find(b)\) ，即 \(a\) 的祖先和 \(b\) 的祖先相同，则说明数 \(a\) 和数 \(b\) 在同一个集合中。
在并查集的 \(find(x)\) 函数中，我们可以使用“路径压缩”的方式来加快速度。即将 \(x\) 的祖宗设为 \(x\) 的父亲，同时将查找路径上的所有点的父亲都设为 \(x\) 的祖宗。
时间复杂度 \(O(n\log n)\)。 若增加“按秩合并”优化，可使时间复杂度进一步降低至 \(O(n\alpha(n))\)，其中 \(\alpha(n)\) 为反阿克曼函数。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, m;
int p[N];
int find(int x) { //查找x的祖先
if (p[x] != x) p[x] = find(p[x]); //路径压缩
return p[x];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) p[i] = i;
char op; int a, b;
while (m -- ) {
cin >> op >> a >> b;
if (op == 'M') p[find(a)] = find(b);
else (find(a) == find(b)) ? puts("Yes") : puts("No");
}
return 0;
}
题目：
初始时，给你一个包含 \(n\) 个点的图（无边）和 \(m\) 次操作：
C a b表示在 \(a\) 和 \(b\) 之间连一条无向边；Q1 a b表示询问 \(a\) 和 \(b\) 是否位于一个连通块内；Q2 a表示询问 \(a\) 所在的连通块的大小。
\(1\le n,m\le 10^5\)。
思路：
除了维护一个 \(p\) 数组存储每个节点的父亲节点，我们还需要维护一个 \(s\) 数组来存储每个连通块的大小。注意，\(s_i\) 当且仅当 \(i\) 为祖宗节点时才有意义，表示以 \(i\) 为祖宗节点的连通块的大小。
合并时，若 \(a\ne b\)，先将两个连通块的大小相加，即 \(s_{find(b)}:=s_{find(b)}+s_{find(a)}\)，然后再 \(p_{find(a)}:=find(b)\)。 其他与并查集完全相同。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, m;
int p[N], s[N]; //s存储每个集合内的连通块数量(只在下标为祖宗节点时有意义)
int find(int x) { //并查集
if (p[x] != x) p[x] = find(p[x]);
return p[x];
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) p[i] = i, s[i] = 1;
while (m -- ) {
string op;
cin >> op;
if (op == "C") { //合并集合
int a, b;
cin >> a >> b;
if (find(a) != find(b)) s[find(b)] += s[find(a)], p[find(a)] = find(b); //要先加上数量再合并
//注意,只需要当a,b在不同联通块时才能进行合并,否则会导致一个连通块内点的数量翻倍
} else if (op == "Q1") { //查询是否位于同一个连通块内
int a, b;
cin >> a >> b;
(find(a) == find(b)) ? puts("Yes") : puts("No");
} else { //查询连通块内点的数量
int a;
cin >> a;
printf("%d\n", s[find(a)]);
}
}
return 0;
}
题目：
有 \(3\) 种动物 \(A,B,C\)，\(A\) 吃 \(B\)，\(B\) 吃 \(C\)，\(C\) 吃 \(A\)。有 \(N\) 种动物，从 \(1\sim N\) 编号，每个动物都是 \(A,B,C\) 中的一种。
有人用 \(2\) 种说法对这 \(N\) 种动物进行描述：
1 X Y表示 \(X\) 和 \(Y\) 是同类。2 X Y表示 \(X\) 吃 \(Y\)。
此人对 \(N\) 个动物一句接一句地说了 \(K\) 句话，其中有真话也有假话。
当一句话满足下列三个条件之一时，这句话就是假话，否则就是真话：
- 当前的话与前面的某些真话冲突，就是假话；
- 当前的话中 \(X>N\) 或 \(Y>N\)，就是假话；
- 当前的话表示 \(X\) 吃 \(X\)，就是假话。
根据给定的 \(N\) 和 \(K\) 句话，输出假话的总数。\(1\le N\le 5\cdot 10^4.1\le K\le 10^5\)。
思路：
我们可以使用“带边权并查集”，令 \(d_i\) 表示 \(i\) 号节点到父节点的距离。
那么我们可以根据 \(d_i\) 除以 \(3\) 的余数将动物分为 \(3\) 类：
- \(d_i \equiv 0\pmod 3\)
- \(d_i\equiv 1\pmod 3\)
- \(d_i\equiv 2\pmod 3\)
对于 1 X Y（\(X,Y\) 为同类），可以看出，若 \(x\) 号节点和 \(y\) 号节点在同一棵树上，且 \(d_x-d_y\equiv 0\pmod 3\)，说明 \(x,y\) 为同一种动物，即这句话是真话；若 \(x\) 号节点和 \(y\) 号节点不在同一棵树上，说明这两种动物之前还没有产生联系，则这句话为真话，设 \(px=find(x),py=find(y)\)，可以令 \(p_{px}=py,d_{px}=d_y-d_x\)。
对于 2 X Y（\(X\) 吃 \(Y\)），可以看出，若 \(x\) 号节点和 \(y\) 号节点在同一棵树上，且 \(d_x-d_y+1\equiv 0\pmod 3\)，说明 \(x\) 吃 \(y\)，即这句话是真话；若 \(x\) 号节点和 \(y\) 号节点不在同一棵树上，说明这两种动物之前还没有产生联系，则这句话为真话，设 \(px=find(x),py=find(y)\)，可以令 \(p_{px}=py,d_{px}=d_y-d_x-1\)。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 50010;
int n, k, cnt;
int p[N], d[N]; //带边权并查集
int find(int x) {
if (p[x] != x) {
int tmp = find(p[x]); //递归更新p[x]到根节点的距离(路径压缩后,p[x]的父亲节点即为其祖宗节点)
d[x] += d[p[x]]; //x到根节点(路径压缩后的根节点)的距离=x到p[x]的距离(即d[x])+p[x]到其父节点(即根节点)的距离
p[x] = tmp; //路径压缩
}
return p[x];
}
int main() {
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; ++i) p[i] = i; //初始时,每个点的父亲是自己,到自己的距离为0
int op, x, y;
while (k -- ) {
scanf("%d%d%d", &op, &x, &y);
if (x > n || y > n) {cnt ++; continue;} //x>n,y>n是假话
int px = find(x), py = find(y);
if (op == 1) {
if (px == py) { //在同一棵树上
//(d[x]-d[y]) % 3 = 0说明是真话,否则是假话
if ((d[x]-d[y]) % 3)
cnt ++;
} else { //不在同一棵树上,说明x,y之前没有联系,视作真话
d[px] = d[y] - d[x];
p[px] = py;
}
} else {
if (px == py) {
if ((d[x]-d[y]+1) % 3)
cnt ++;
} else {
d[px] = d[y] - d[x] - 1;
p[px] = py;
}
}
}
printf("%d\n", cnt);
return 0;
}
2.7 堆
题目：
给你一个长度为 \(n\) 的数组 \(a\)，输出前 \(m\) 小的数。\(1\le m\le n\le 10^5,1\le a_i\le 10^9\)。
思路：
堆可以看作是一个完全二叉树，所以我们可以用存储二叉树的方式来存储它，若下标为 \(n\) 的点为一个父亲节点，则其左儿子的下标为 \(2n\)，右儿子的下标为 \(2n+1\)。在本题中我们使用的是小根堆，对于每一个父亲节点 \(u\)，它存储的值小于等于它的左儿子或右儿子，即\(a_u\le\min(a_{2u},a_{2u+1})\)。
下图（\(\texttt{2-11}\)）展示了一个小根堆：
图2-11
堆有两个个关键的操作——down 操作和 up 操作，时间复杂度均为 \(O(\log n)\)。 对于一个左右子树均为堆的非叶子节点 \(u\) ，down(u) 意味着将 \(u\) 下传至堆中合适的位置，使其满足堆的性质。对于一个节点 \(u\)，up(u) 意味着将 \(u\) 上传至堆中合适的位置，使其满足堆的性质。在本题中我们只需要用到 down 操作。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, m;
int a[N], s;
void down(int u) { //时间复杂度O(log n)
int t = u;
//u*2和u*2+1分别是u的左儿子和右儿子
if (u*2 <= s && a[u*2] < a[t])
t = u*2;
if (u*2+1 <= s && a[u*2+1] < a[t])
t = u*2+1; //若a[u]>min(a[2u],a[2u+1]),则在左儿子和右儿子中取较小值与a[u]交换
if (t != u) {
swap(a[t], a[u]);
down(t);
}
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
s = n;
for (int i = n/2; i > 0; --i) down(i);
//从n/2开始倒序建堆，是因为n/2+1,...,n均为叶子结点,不需要down操作
for (int i = 1; i <= m; ++i) {
printf("%d ", a[1]);
a[1] = a[s], s --; //每次取出堆头后将堆头删去,用最后一个元素替代它
down(1); //下传堆头元素
}
return 0;
}
题目：
维护一个集合，初始时集合为空，支持如下几种操作：
I x，插入一个数 \(x\)；PM，输出当前集合中的最小值；DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；D k，删除第 \(k\) 个插入的数；C k x，修改第 \(k\) 个插入的数，将其变为 \(x\)；
现在要进行 \(N\) 次操作，对于所有 PM 操作，输出当前集合的最小值。\(1\le N\le 10^5,-10^9\le x\le 10^9\)。
思路：
本题中的 \(5\) 个操作均可以用堆的 down 和 up 操作来实现。下面为 up 操作的实现方式：
void up(int u) {
while (u / 2 > 0 && h[u] < h[u/2]) {
//如果u存在父节点且u节点上的值比其父节点上的值要小.则交换这两个点
swap(u, u/2);
u /= 2;
}
}
本题的难点在于如何实现后两个操作。我们可以仿照链表的存储方式，用变量 \(m\) 来存储当前插入节点的编号。另外我们维护两个数组 \(ph\) 和 \(hp\)，\(ph_i\) 表示堆中 \(i\) 号节点所对应的插入编号，\(hp_i\) 表示插入编号 \(i\) 在堆中所对应的节点序号。与上一道例题一样，我们还需要一个变量 \(s\) 来存储堆的大小，一个数组 \(h\) 来存储堆中的元素。
由于增加了数组 \(ph\) 和 \(hp\)，堆中元素的交换变的更加复杂。所以我们可以写一个函数 heap_swap 来处理堆中两个编号为 \(a,b\) 的元素的交换。
void heap_swap(int a, int b) { //将堆中编号为a,b的两个点互换
swap(ph[hp[a]], ph[hp[b]]); //交换节点编号
swap(hp[a], hp[b]); //交换插入编号
swap(h[a], h[b]);
}
down 操作和 up 操作中的 swap 也需要替换成 heap_swap.
void down(int u) {
int t = u;
if (u*2 <= s && h[u*2] < h[t]) t = u*2;
if (u*2+1 <= s && h[u*2+1] < h[t]) t = u*2+1;
if (t != u) {
heap_swap(t, u);
down(t);
}
}
void up(int u) {
while (u / 2 > 0 && h[u] < h[u/2]) {
heap_swap(u, u/2);
u /= 2;
}
}
有了这三个核心操作，我们就可以完成题目所给的要求了。
-
I x：插入一个数 \(x\)。 堆的大小 \(s\) 和插入序号 \(m\) 都需要增加 \(1\)；此时 \(ph_s=m,hp_m=s,h_s=x\)。 然后再将 \(s\) 号节点up操作即可。 -
PM：输出堆中的最小元素。由小根堆的性质，直接输出 \(h_1\) 即可。 -
DM：删除堆中的最小元素。将 \(1\) 号节点和 \(s\) 号节点交换，\(s\) 再减去 \(1\)（删除一个元素，大小减少 \(1\)）， 再将 \(1\) 号节点down操作即可。 -
D k：删除插入序号为 \(k\) 的节点。插入序号为 \(k\) 的节点在堆中的序号为 \(ph_k\)，仿照DM操作，将 \(s\) 号节点和 \(ph_k\) 号节点交换，\(s\) 减去 \(1\)，再将 \(ph_k\) 号节点分别down和up操作一次即可。 -
C k x：将插入序号为 \(k\) 的节点的值更改为 \(x\)。 仿照D k操作，将 \(h_{ph_k}\) 设为 \(x\)，再将ph_k号节点分别down和up操作一次即可。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int n, m, s;
int h[N], ph[N], hp[N];
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 <= s && h[u*2] < h[t]) t = u*2;
if (u*2+1 <= s && h[u*2+1] < h[t]) t = u*2+1;
if (t != u) {
heap_swap(t, u);
down(t);
}
}
void up(int u) {
while (u / 2 > 0 && h[u] < h[u/2]) {
heap_swap(u, u/2);
u /= 2;
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
while (n -- ) {
string op;
cin >> op;
if (op == "I") {
int x; cin >> x;
s ++, m ++;
ph[m] = s, hp[s] = m;
h[s] = x; up(s);
} else if (op == "PM") {
cout << h[1] << endl;
} else if (op == "DM") {
heap_swap(1, s);
s --;
down(1);
} else if (op == "D") {
int k; cin >> k;
k = ph[k];
heap_swap(k, s);
s --;
down(k), up(k);
} else {
int k, x; cin >> k >> x;
k = ph[k];
h[k] = x;
down(k), up(k);
}
}
return 0;
}
2.8 哈希表
2.8.1 普通哈希
题目：
维护一个集合，支持以下两种操作：
I x插入一个数 \(x\)；Q x询问 \(x\) 是否在集合中出现过。
给定 \(n\) 次操作，对于每次 Q x 操作输出对应结果 Yes 或 No.
\(1\le N\le 10^5,-10^9\le x\le 10^9\)。
思路：
哈希有两种实现方式：拉链法和开放寻址法。其本质都是通过一个哈希函数 \(f(x)\) 来实现将较大范围的数（或负数）映射到一个较小的区间 \([0,k)\) 内，以实现快速查找。但由于不同的数可能映射到一个相同的值，所以我们需要一些方法来进行处理。
拉链法：对于区间 \([0,k)\) 中的每一个数，开一个链表存储其映射到的数（即邻接表），每次遍历查找即可。
开放寻址法：若当前 \(f(x)\) 的位置上已经存了一个数，则向后（若到了尾部则跳到 \(0\)）不断查找第一个没有存数的点并将其插入。
代码：
拉链法：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e5+10;
const int p = 100003;
int n;
int h[N], e[N], ne[N], idx;
int f(int x) {
return (long long)x * x % p;
}
void add(int a, int b) {
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void insert(int x) {
int x_ = f(x);
add(x_, x);
}
bool check(int x) {
int x_ = f(x);
for (int i = h[x_]; i != -1; i = ne[i]) {
int j = e[i];
if (j == x) return 1;
}
return 0;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
memset(h, -1, sizeof h);
char op; int x;
while (n -- ) {
cin >> op >> x;
if (op == 'I') insert(x);
else {
if (check(x)) puts("Yes");
else puts("No");
}
}
return 0;
}
开放寻址法：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1e6+10;
const int p = 999987;
int n;
int h[N];
int f(int x) {
return (x % p + p) % p;
}
int find(int x) {
int x_ = f(x);
while (h[x_] != 0x3f3f3f3f && h[x_] != x) {
x_ ++;
if (x_ > p) x_ = 0;
}
return x_;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
memset(h, 0x3f, sizeof h);
char op; int x;
while (n -- ) {
cin >> op >> x;
if (op == 'I') h[find(x)] = x;
else {
if (h[find(x)] != 0x3f3f3f3f) puts("Yes");
else puts("No");
}
}
return 0;
}
2.8.2 字符串哈希
题目：给定一个长度为 \(n\) 的字符串 \(s\) 和 \(m\) 次询问，每次询问给定两个区间 \([l_1, r_1],[l_2,r_2]\)，判断这两个区间所包含的子串是否完全相同。
\(s\) 中只包含大小写字母及数字，且位置从 \(1\) 开始编号，\(1\le n,m\le 10^5\)。
思路：
对于字符串，我们有一种常用的哈希方式。将该字符串视作一个 \(p\) 进制数，将其转换为十进制后对 \(q\) 取模。通常取 \(p=131\) 或 \(13331\)，\(q=2^{64}\)（可直接通过 unsigned long long 的溢出取模）。
我们可以先计算 \(s\) 中所有前缀字符串的的哈希值。定义 \(h_i\) 表示 \(s\) 中 \([1,s]\) 之间字符的哈希值。显然 \(h_0=0\)，那么 \(h_i=h_{i-1}\times p+s_i\)。
接下来，我们可以通过 \(h\) 求出每个子串的哈希值。对于区间 \([l,r]\)，其包含的子串的哈希值为 \(h_r-h_{l-1}\times p^{r-l+1}\)，其中 \(p\) 的幂次可以预处理。
代码：
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned long long ull;
const int N = 1e5+10;
const int P = 13331;
int n, m;
char s[N];
ull h[N], p[N];
ull get_hash(int l, int r) {
return (h[r] - h[l-1] * p[r-l+1]);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> s+1;
h[0] = 0, p[0] = 1;
for (int i = 1; i <= n; ++i) {
h[i] = h[i-1] * P + (s[i] - 'A' + 1);
p[i] = p[i-1] * P;
}
int l1, r1, l2, r2;
while (m -- ) {
cin >> l1 >> r1 >> l2 >> r2;
ull h1 = get_hash(l1, r1), h2 = get_hash(l2, r2);
if (h1 == h2) puts("Yes");
else puts("No");
}
return 0;
}
原文地址：http://www.cnblogs.com/Jasper08/p/16907618.html
