370 lines
11 KiB
Markdown
370 lines
11 KiB
Markdown
# 数据结构
|
||
|
||
- [数据结构](#数据结构)
|
||
- [单调队列](#单调队列)
|
||
- [单调队列引入](#单调队列引入)
|
||
- [引入问题滑动窗口](#引入问题滑动窗口)
|
||
- [单调队列例题](#单调队列例题)
|
||
- [P1886 滑动窗口](#p1886-滑动窗口)
|
||
- [P1886代码](#p1886代码)
|
||
- [P1714 切蛋糕](#p1714-切蛋糕)
|
||
- [P1714题解](#p1714题解)
|
||
- [P1714代码](#p1714代码)
|
||
- [P1725 琪露诺](#p1725-琪露诺)
|
||
- [P1725题解](#p1725题解)
|
||
- [P1725代码](#p1725代码)
|
||
- [单调栈](#单调栈)
|
||
- [单调栈例题](#单调栈例题)
|
||
- [并查集](#并查集)
|
||
- [并查集查询](#并查集查询)
|
||
- [并查集合并](#并查集合并)
|
||
- [带权并查集](#带权并查集)
|
||
- [带权并查集例题](#带权并查集例题)
|
||
- [P2024 NOI2001食物链](#p2024-noi2001食物链)
|
||
- [P2024题解](#p2024题解)
|
||
- [可撤销并查集](#可撤销并查集)
|
||
- [并查集例题](#并查集例题)
|
||
- [并查集例题1](#并查集例题1)
|
||
- [并查集例题1题解](#并查集例题1题解)
|
||
- [并查集例题2](#并查集例题2)
|
||
- [并查集例题2题解](#并查集例题2题解)
|
||
- [并查集例题3](#并查集例题3)
|
||
- [并查集例题3题解](#并查集例题3题解)
|
||
- [堆](#堆)
|
||
- [线段树](#线段树)
|
||
- [树状数组](#树状数组)
|
||
- [Trie](#trie)
|
||
|
||
## 单调队列
|
||
|
||
### 单调队列引入
|
||
|
||
#### 引入问题滑动窗口
|
||
|
||
> 如果有人比你小还比你强，那你就没有任何用了 —— noip
|
||
|
||
有 $n$ 个 oier ，每个 oier 有成绩和考试，保证给定数据中 oier 的出生年份单调，求每 $k$ 个年份时这 $n$ 个 oier 的最大成绩。伪代码：
|
||
|
||
```cpp
|
||
deque<pair<int,int>> q; // 成绩，年份
|
||
while(!q.empty() && newgrade>q.back()) q.pop_back;
|
||
q.push_back(newgrade,newyear);
|
||
while(q.front().second要退役){
|
||
q.pop_front();
|
||
}
|
||
|
||
最大值q.front().first
|
||
```
|
||
|
||
时间复杂度 $O(n)$ （均摊复杂度，每个人都入队出队一次，可能某次while执行很久，可能某次很快）
|
||
|
||
注意：此处使用 `deque` 只是为了方便伪代码，现实中为了压低复杂度一般使用数组模拟。
|
||
|
||
从这段引入来看，单调队列可以在 $O(n)$ 的复杂度解决**固定区间长度的** [RMQ 问题](../1.基础算法/基础算法.md#rmq与st表)。
|
||
|
||
### 单调队列例题
|
||
|
||
#### P1886 滑动窗口
|
||
|
||
[题目链接](https://www.luogu.com.cn/problem/P1886)
|
||
|
||
求序列 $a$ 每 $k$ 个数的最大值以及最小值。
|
||
|
||
|窗口位置|最小值|最大值|
|
||
|---|---|---|
|
||
|[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|
|
||
|
||
#### P1886代码
|
||
|
||
模板题就不给题解了。
|
||
|
||
```cpp
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
int x;
|
||
struct sd
|
||
{
|
||
int num, val; // 存储编号和大小
|
||
};
|
||
deque<sd> que;
|
||
deque<sd> que1;
|
||
int add[3][1000005]; // 用以存储答案的----见代码
|
||
int main()
|
||
{
|
||
int n, m, k, cnt = 1;
|
||
cin >> n >> k;
|
||
sd rr;
|
||
for (int i = 1; i <= n; i++)
|
||
{
|
||
scanf("%d", &x); // 输入
|
||
rr.num = i;
|
||
rr.val = x; // 赋值
|
||
while (!que.empty() && x >= que.back().val)
|
||
que.pop_back(); // 单调队列的操作，以保证单调
|
||
while (!que1.empty() && x <= que1.back().val)
|
||
que1.pop_back();
|
||
que.push_back(rr); // 压入队列
|
||
que1.push_back(rr); // 同上
|
||
while (i - k >= que.front().num) // T掉不在范围内的
|
||
que.pop_front();
|
||
while (i - k >= que1.front().num)
|
||
que1.pop_front(); // 同上
|
||
if (i >= k)
|
||
{
|
||
add[0][cnt] = que.front().val;
|
||
add[1][cnt] = que1.front().val;
|
||
cnt++;
|
||
} // 存答案
|
||
}
|
||
for (int i = 1; i < cnt; i++)
|
||
printf("%d ", add[1][i]);
|
||
printf("\n");
|
||
for (int i = 1; i < cnt; i++)
|
||
printf("%d ", add[0][i]); // 输出
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
#### P1714 切蛋糕
|
||
|
||
[题目链接](https://www.luogu.com.cn/problem/P1714)
|
||
|
||
有一个长方形的蛋糕，被不同的色彩分成了 $N$ 个相同的小块，每个小块有着对应的幸运值。
|
||
|
||
小 Z 作为寿星，希望吃到的蛋糕的幸运值最大，但是他最多只能吃 $M (M \le N)$
|
||
|
||
你需要在这 $N$ 小块蛋糕中找出连续的几块，使得其上总幸运值最大。
|
||
|
||
形式化地，在数列 ${a_n}$ 中，找出一个长度小于 $M(M \le n)$ 的子段 $[l, r]$，最大化 $\sum^{r}_{i = l} {a_i}$
|
||
|
||
$1 \le n \le 5 \times 10^5$
|
||
|
||
##### P1714题解
|
||
|
||
考虑将区间和问题转换为前缀和的差。将前 $i$ 位的前缀和记作 $pre_i$，问题即转化为求两个位置 $l, r$，使得 $r - l + 1 \le m$ 并使得 $pre_r - pre_{l - 1}$ 最大。
|
||
|
||
但是，枚举两个点是 $O(n^2)$ 的，所以考虑枚举一个节点，另外一个节点使用数据结构来确认。这里我们枚举 $r$，问题就变为了求 $l \in [r, r - M + 1]$ 时 $pre_{l - 1}$ 的最小值，可以使用单调队列来维护。
|
||
|
||
##### P1714代码
|
||
|
||
```cpp
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
int ans = INT_MIN, n, m;
|
||
int pre[500005];
|
||
deque<int> q; // 存储下标
|
||
int main()
|
||
{
|
||
scanf("%d%d", &n, &m);
|
||
for (int i = 1, tmp; i <= n; i++)
|
||
{
|
||
scanf("%d", &tmp);
|
||
pre[i] = pre[i - 1] + tmp;
|
||
}
|
||
q.push_back(0);
|
||
for (int r = 1; r <= n; r++)
|
||
{
|
||
while (q.front() + m < r)
|
||
q.pop_front();
|
||
ans = max(ans, pre[r] - pre[q.front()]);
|
||
while (!q.empty() && pre[q.back()] >= pre[r])
|
||
q.pop_back();
|
||
q.push_back(r);
|
||
}
|
||
printf("%d\n", ans);
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
#### P1725 琪露诺
|
||
|
||
[题目链接](https://www.luogu.com.cn/problem/P1725)
|
||
|
||
给定长度为 $n + 1$ 的数组 $a$， $a_0 = 0$。从第 $0$ 项出发，对于当前位置 $i$，可以转移到 $j \in [i + L, i + R]$ 中的任意位置，并且获得 $a_j$ 的分数，求位置 $\ge n$ 时的最大得分。
|
||
|
||
##### P1725题解
|
||
|
||
考虑 dp，使用 $f_i$ 表示走到 $i$ 位置的最大得分。此时 $f_i$ 的转移便和 $\max \{f_j\} (j \in [i - R, i - L])$ 有关系。发现区间长度固定，故考虑使用单调队列。
|
||
|
||
##### P1725代码
|
||
|
||
```cpp
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
int N, L, R, A[200005], ans, f[200005];
|
||
int que[200005], ll = 1, rr = 1;
|
||
void insert(int i)
|
||
{
|
||
for (; f[i] >= f[que[rr]] && rr >= ll;)
|
||
rr--;
|
||
que[++rr] = i;
|
||
}
|
||
int query(int x)
|
||
{
|
||
for (; que[ll] + R < x;)
|
||
ll++;
|
||
return que[ll];
|
||
}
|
||
int main()
|
||
{
|
||
memset(f, 128, sizeof(f));
|
||
f[0] = 0, ans = INT_MIN;
|
||
scanf("%d%d%d", &N, &L, &R);
|
||
for (int i = 0; i <= N; i++)
|
||
scanf("%d", &A[i]);
|
||
for (int i = L; i <= N; i++)
|
||
{
|
||
insert(i - L);
|
||
int from = query(i);
|
||
f[i] = f[from] + A[i];
|
||
if (i + R > N)
|
||
ans = max(ans, f[i]);
|
||
}
|
||
printf("%d", ans);
|
||
return 0;
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 单调栈
|
||
|
||
### 单调栈例题
|
||
|
||
类似于单调队列，每次向单调栈中插入一个元素，就要 pop 掉栈顶小于这个元素的值，再插入。与单调队列不同的是，单调栈不支持从底部弹出。
|
||
|
||
---
|
||
|
||
## 并查集
|
||
|
||
### 并查集查询
|
||
|
||
对于给定的 $a$，沿着树向上移动知道根节点即可。在合并的过程中的每个节点都属于这个集合，所以将父亲节点直接设为根即可。
|
||
|
||
### 并查集合并
|
||
|
||
合并两个集合时，可以将一个集合的根节点设为另一个集合的根节点。为了防止退化，可以将节点较少或深度较小的一棵树连接到令一颗上，这种合并方法称作按秩合并。
|
||
|
||
## 带权并查集
|
||
|
||
我们可以在并查集的边上维护某种值，在路径压缩时产生运算。
|
||
|
||
### 带权并查集例题
|
||
|
||
#### P2024 NOI2001食物链
|
||
|
||
[题目链接](https://www.luogu.com.cn/problem/P2024)
|
||
|
||
动物王国中有三类动物 $A,B,C$，这三类动物的食物链构成了有趣的环形。$A$ 吃 $B$，$B$ 吃 $C$，$C$ 吃 $A$。
|
||
|
||
现有 $N$ 个动物，以 $1 \sim N$ 编号。每个动物都是 $A,B,C$ 中的一种，但是我们并不知道它到底是哪一种。
|
||
|
||
有人用两种说法对这 $N$ 个动物所构成的食物链关系进行描述：
|
||
|
||
- 第一种说法是 `1 X Y`，表示 $X$ 和 $Y$ 是同类。
|
||
- 第二种说法是`2 X Y`，表示 $X$ 吃 $Y$。
|
||
|
||
此人对 $N$ 个动物，用上述两种说法，一句接一句地说出 $K$ 句话，这 $K$ 句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
|
||
|
||
- 当前的话与前面的某些真的话冲突，就是假话；
|
||
- 当前的话中 $X$ 或 $Y$ 比 $N$ 大，就是假话；
|
||
- 当前的话表示 $X$ 吃 $X$，就是假话。
|
||
|
||
你的任务是根据给定的 $N$ 和 $K$ 句话，输出假话的总数。
|
||
|
||
##### P2024题解
|
||
|
||
考虑维护带权并查集，对每次给定的话进行查询与合并。
|
||
|
||
具体的，对于并查集中的每两个节点，使用 $0$ 表示互为同类， $1$ 表示父亲吃儿子， $2$ 表示儿子吃父亲。
|
||
|
||
对于每句话 `1/2 X Y`，查询 $X, Y$ 之间的关系，若无冲突便合并即可，注意路径压缩时的运算。
|
||
|
||
|
||
|
||
## 可撤销并查集
|
||
|
||
对于一开始相互独立的 $n$ 个点，维护以下两种操作共 $q$ 次：
|
||
|
||
1. 给定 $a, b$ 两个点，判断是否在同一个联通块中，如不在则在 $a, b$ 间连边。
|
||
2. 撤销最后的若干次操作 $1$
|
||
|
||
要求复杂度 $O(q \log n)$
|
||
|
||
考虑用栈记录最近操作 $fa_x \leftarrow y$ ，每次撤销弹出栈顶，并将 $fa_x \leftarrow x$
|
||
|
||
因为要保证可逆，所以不能路径压缩，只能启发式合并。
|
||
|
||
## 并查集例题
|
||
|
||
### 并查集例题1
|
||
|
||
有 $n$ 个点，初始时均为孤立点。
|
||
|
||
接下来有 $m$ 次连边操作，第 $i$ 次在 $a_i, b_i$ 之间连一条边。
|
||
|
||
接下来有 $q$ 次询问，每次询问两个点在第几次加边操作联通。
|
||
|
||
$1 \le n, m, q \le 10^5$
|
||
|
||
#### 并查集例题1题解
|
||
|
||
考虑对于每一次合并的 $a_i, b_i$，若两个点不联通，则在另外一颗树中连接 $a_i, b_i$，边权为 $i$。
|
||
|
||
每次查询就是在令一颗树中找到 $u, v$ 路径上边权最大值，可以使用树上倍增维护。
|
||
|
||
### 并查集例题2
|
||
|
||
有一个长度为 $n$ 的 $01$ 序列 $a_1, \dots, a_n$，一开始全是 $0$。接下来进行如下 $m$ 次操作：
|
||
|
||
- $a_x \leftarrow 1$
|
||
- 输出 $\min\{x \in [l,r], a_x = 0\}$
|
||
|
||
$1 \le n, m \le 10^6$
|
||
|
||
#### 并查集例题2题解
|
||
|
||
建立并查集，使得 $i$ 所在联通块的根节点为 $i$ 后面第一次出现 $0$ 的位置，初始 $f_i = i$
|
||
|
||
对于每一次 $a_x \leftarrow 1$，如果 $a_x$ 原先不为 $1$，则令 $f_x = f_{x - 1}$
|
||
|
||
每次查询输出 $x$ 的祖先。
|
||
|
||
### 并查集例题3
|
||
|
||
给定一颗 $n$ 个节点的树，接下来有 $m$ 次操作：
|
||
|
||
- 加一条 $a_i$ 到 $b_i$ 的边。
|
||
- 询问两个点之间是否存在至少两条**边不相交**的路径。
|
||
|
||
**边不相交：指的是两个路径没有公共边。**
|
||
|
||
$1 \le n, m \le 10^6$
|
||
|
||
#### 并查集例题3题解
|
||
|
||
前置知识：[强联通分量](../4.树上问题及图论/树上问题及图论.md#强联通分量)
|
||
|
||
---
|
||
|
||
## 堆
|
||
|
||
---
|
||
|
||
## 线段树
|
||
|
||
---
|
||
|
||
## 树状数组
|
||
|
||
---
|
||
|
||
## Trie
|
||
|
||
---
|