11 KiB
数据结构
单调队列
单调队列引入
引入问题滑动窗口
如果有人比你小还比你强，那你就没有任何用了 —— noip
有 n 个 oier ，每个 oier 有成绩和考试，保证给定数据中 oier 的出生年份单调，求每 k 个年份时这 n 个 oier 的最大成绩。伪代码：
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 问题。
单调队列例题
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代码
模板题就不给题解了。
#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 切蛋糕
有一个长方形的蛋糕，被不同的色彩分成了 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代码
#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 琪露诺
给定长度为 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代码
#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食物链
动物王国中有三类动物 $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 次：
- 给定
a, b两个点，判断是否在同一个联通块中，如不在则在a, b间连边。 - 撤销最后的若干次操作
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题解
前置知识：强联通分量