基础数据结构合辑

单调栈/单调队列#

单调栈#

单调栈Monotone Stack，顾名思义，是一种栈状结构，且栈内元素单调。它既满足栈的“先进后出F I L O”性质，也符合元素从栈顶到栈底呈单调排列（或者从栈底到栈顶）。根据单调性的不同，大致可以分为“单调递增栈”和“单调递减栈”。若无特殊说明，单调栈的递增/递减判断顺序是从栈顶到栈底。

在单调栈构建过程中，有如下要求：

当前待插入元素与栈顶元素满足全栈的单调关系，则直接插入顶端。
反之，弹出栈顶元素直到满足第一点，此时直接插入。

例如一个单调递增栈的实现：

1
stack<int> stk;
2

3
void insert(int x) {
4
    while (!stk.empty() && stk.top() > x) stk.pop();
5
    stk.push(x);
6
}

~~没错就这么短~~

依据单调栈的这些性质，人们探索出了一种能在 $\mathcal O(n)$ 时间复杂度内求解下一大元素N G E问题（或者下一小元素）的算法。

我们新建一个数组用来记录下一大元素的下标，数组 nge[i] 即表示原序列中下标 $i$ 的元素的下一大元素的下标。让单调栈存储元素下标，当每次待插入的元素大于栈顶下标对应的元素时，则记录当前栈顶到 nge 中，并弹出栈顶。如此一来便处理得到了一个完整的 nge 数组

P5788 [模板] 单调栈

1
#include <bits/stdc++.h>
2

3
#define N 3000010
4
using namespace std;
5

6
typedef long long ll;
7

8
stack<int> stk;
9
ll arr[N];
10
int nge[N];
11
int n;
12

13
void NGE() {
14
    for (int i = 1; i <= n; i++) {
15
        while (!stk.empty() && arr[i] > arr[stk.top()]) {
16
            nge[stk.top()] = i;
17
            stk.pop();
18
        }
19
        stk.push(i);
20
    }
21
}
22

23
int main() {
24
    cin >> n;
25
    for (int i = 1; i <= n; i++) cin >> arr[i];
26
    NGE();
27
    for (int i = 1; i <= n; i++) cout << nge[i] << ' ';
28
    return 0;
29
}

单调队列#

单调队列Monotone Queue其实和单调栈非常相似——给队列规定一个定长，让它在一段序列上滑动，当队首元素符合单调性则推入，否则就弹出队首直到满足单调性为止，同时，队列随着每次的滑动会自然抛除末尾的某个值。这样一来，单调队列就可以解决区间内最值的问题。

首先，我们依据单调栈里面的单调性检验，弹出队头不符合单调性的值。接着，把当前的值插入队头。如果队头元素的下标与队尾元素下标的差值超过了队列长度，则自然淘汰掉。反之输出队尾元素，它储存了当前区间的最值。

P1886 滑动窗口 /[模板] 单调队列

1
#include <bits/stdc++.h>
2

3
#define N 1000010
4
using namespace std;
5

6
typedef long long ll;
7

8
struct Node {
9
    int idx;
10
    ll v;
11
} nodes[N];
12

13
deque<Node> q;
14

15
int main() {
16
    ios::sync_with_stdio(false);
17
    cin.tie(nullptr);
18
    cout.tie(nullptr);
19

20
    int n, k;
21
    cin >> n >> k;
22
    for (int i = 1; i <= n; i++) {
23
        cin >> nodes[i].v;
24
        nodes[i].idx = i;
25
    }
26
    for (int i = 1; i <= n; i++) {
27
        while (!q.empty() && nodes[i].v < q.front().v) q.pop_front();
28
        q.push_front(nodes[i]);
29
        if (i - q.back().idx == k) q.pop_back();
30
        if (i >= k) cout << q.back().v << ' ';
31
    }
32
    cout << endl;
33
    q.clear();
34
    for (int i = 1; i <= n; i++) {
35
        while (!q.empty() && nodes[i].v > q.front().v) q.pop_front();
36
        q.push_front(nodes[i]);
37
        if (i - q.back().idx == k) q.pop_back();
38
        if (i >= k) cout << q.back().v << ' ';
39
    }
40
    return 0;
41
}

ST 表#

ST 表Sparse Table是一种能在 $\mathcal O(n\log n)$ 时间内预处理， $\mathcal O(1)$ 回答区间最值查询（不支持修改，若要修改请移步线段树）的一种数据结构。借用了动态规划的思想，兼以步长 ${2^j-1}$ 的倍增。

对于一段静态序列（不变），为了求某段子列的最大值，先把这个子列分成两个更小的子序列。假设 $f(i,j)$ 表示在区间 $[i,i+2^j-1]$ 内的最大值，对于单个点，即 $f(i,0)$ 时，显然有 $f(i,0)=a_i$ （最大值就是自己）。否则，最大值即是左区间最大值和右区间最大值更大的那一个。

P3865 [模板] ST 表

1
#include <bits/stdc++.h>
2

3
#define N 100010
4
using namespace std;
5

6
int a[N];
7
int logn[N];
8
int f[N][22];
9
int n;
10

11
void init() {
12
    for (int i = 1; i <= n; i++) f[i][0] = a[i];
13
    for (int j = 1; j <= logn[n]; j++) {
14
        for (int i = 1; i + (1 << j) - 1 <= n; i++) {
15
            f[i][j] = max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
16
        }
17
    }
18
}
19

20
void initLog() {
21
    logn[1] = 0;
22
    logn[2] = 1;
23
    for (int i = 3; i <= n + 100; i++) logn[i] = logn[i >> 1] + 1;
24
}
25

26
int main() {
27
    ios::sync_with_stdio(false);
28
    cin.tie(nullptr);
29
    cout.tie(nullptr);
30

31
    int m;
32
    cin >> n >> m;
33
    for (int i = 1; i <= n; i++) cin >> a[i];
34
    initLog();
35
    init();
36
    while (m--) {
37
        int l, r;
38
        cin >> l >> r;
39
        int tmp = logn[r - l + 1];
40
        cout << max(f[l][tmp], f[r - (1 << tmp) + 1][tmp]) << endl;
41
    }
42
    return 0;
43
}

~~个人感觉理解难度有点大，建议先背下来~~

警示后人：不要用 endl，换成 \n 快了高达七倍不止！AC、TLE。

Note

在 C++ 中，数组的访问是行优先的。因此如果把 ST 表数组的第一维和第二维交换位置，那么程序的运行效率会变得更高

并查集#

并查集Disjoint Set Union，顾名思义，它是一种能完成数据合并、查询的集合数据结构。在路径压缩优化下，它能在平均 $\mathcal O(\alpha(n))$ 的时间复杂度内完成一次操作（由 $\texttt{Robert Tarjan}$ 证明，他也是 $\texttt{Splay}$ 的奠基人之一）。关于并查集时间复杂度的证明请看：并查集复杂度 - OI Wiki。

首先，我们需要一个数组来记录每个点的父节点。在查询时，我们采取从底部逐级向上递归搜索的方式，可以发现，我们在实际操作时并不会关心它到根节点路径上的其他非根节点，出于效率考虑，可以将沿途每个点的父节点都一次性设成全局父节点，而这一切都可以在递归查询的过程中完成。在合并时，无需将每个点都合并过去，只需要把某棵树的根节点并到另一棵树的根节点下面去就行了！

P3367 [模板] 并查集

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
int p[10010];
6

7
int find(int x) {
8
    if (p[x] != x) p[x] = find(p[x]);
9
    return p[x];
10
}
11

12
void merge(int x, int y) {
13
    p[find(x)] = find(y);
14
}
15

16
bool query(int x, int y) {
17
    return find(x) == find(y);
18
}
19

20
int main() {
21
    int n, m;
22
    cin >> n >> m;
23
    for (int i = 1; i <= n; i++) p[i] = i;
24
    for (int i = 1; i <= m; i++) {
25
        int z, x, y;
26
        cin >> z >> x >> y;
27
        if (z == 1) merge(x, y);
28
        else {
29
            if (query(x, y)) cout << "Y" << endl;
30
            else cout << "N" << endl;
31
        }
32
    }
33
    return 0;
34
}

关于带权并查集、种类并查集，请参阅这篇博客。

哈希/散列函数#

哈希Hash或者称“散列”，其运作原理是把一个数据映射到一个较小（但不能太小）的值域里进行比较。通常来说，我们希望哈希满足如下两个性质：

两个对象哈希值不同，则两个对象一定不同
哈希值相同，则两个对象不一定相同

人们把第二种情况中可能出现的“对象不同却哈希相同”的现象叫做“哈希碰撞Hash Clash”。

对于一个字符串 $s$ ，一般采取的是多项式散列的方法。首先把字符串的每一位挑出来，类比成一个数字位，然后采取形如 $\sum\limits_{i=0}^{|s|-1}s_i\times b^{|s|-i-1}\pmod m$ 的方法获取它的散列结果。举个例子，字符串 $\text{xyz}$ 会被散列成 $x+yb+zb^2$ 。一般来说，把 $m$ 设定成一个较大质数，发生碰撞的概率是很低的~~阳寿碰撞就没办法了，多交几次吧~~。

当然，你也可以使用碰撞率更低的 MD5，但是 C++ 并没有内置相关的库，你如果想用，那么就必须要完全背下来或者是现场复制。其实还不如自己选特殊值算。

按照上边的方法计算，复杂度是 $\mathcal O(n)$ 。如果加上询问，那就是 $\mathcal O(nm)$ 。在多次询问子串哈希时，观察到有如下式子：

\begin{cases} H=s_1b^{len-1}+s_2b^{len-2}+\dots+s_i \\h=s_lb^{len-l}+s_{l+1}b^{len-l-1}+\dots+s_rb^{len-r} \end{cases}

假设 $f(i,j)$ 代表原字符串区间 $[i,j]$ 内的子串的哈希值，那么 $f(i,j)=f(1,r)-f(1,l-1)\times b^{r-l+1}$ 。现在就可以最快用 $\mathcal O(m\log n)$ 的快速幂求解了。

P3370 [模板] 字符串哈希

1
#include <bits/stdc++.h>
2

3
using namespace std;
4

5
typedef long long ll;
6

7
const int MOD = 1000000007;
8
const int b = 2;
9
map<string, int> mp;
10

11
int qpow(int a, int b) {
12
    int res = 1;
13
    while (b) {
14
        if (a & 1) res = (ll) (res * a) % MOD;
15
        a = (ll) (a * a) % MOD;
16
        b >>= 1;
17
    }
18
    return res;
19
}
20

21
int hashStr(string s) {
22
    int res = 0;
23
    for (int i = 0; i < s.length(); i++) {
24
        res = (res + (s[i] - '0') * qpow(b, s.length() - i - 1)) % MOD;
25
    }
26
    return res;
27
}
28

29
int main() {
30
    ios::sync_with_stdio(false);
31
    cin.tie(nullptr);
32
    cout.tie(nullptr);
33

34
    int n;
35
    cin >> n;
36
    for (int i = 1; i <= n; i++) {
37
        string s;
38
        cin >> s;
39
        int h = hashStr(s);
40
        if (!mp.count(s)) mp[s] = h;
41
    }
42
    cout << mp.size() << endl;
43
    return 0;
44
}

音乐

JustPureH₂O

穷方圆平直之情，尽规矩准绳之用

音乐