数据结构

链表

单链表的操作

  • 初始化
  • 插入
  • 删除
    时间复杂度：O(1)

单链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const int N=100010;

int head,e[N],ne[N],idx;
//初始化
void init(){
    head=-1;
    idx=0;
}
//在链表头部添加节点
void add_to_head(int x){
    e[idx]=x,ne[idx]=head,head=idx++;
}
//在位置k添加节点x
void add(int k,int x){
    e[idx]=x,ne[idx]=ne[k],ne[k]=idx++;
}
//删除位置k的节点
void remove(int k){
    ne[k]=ne[ne[k]];
}

双链表

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<iostream>

using namespace std;

const int N = 1e5 + 10;

int m;
int e[N], l[N], r[N];
int idx;


//! 初始化
void init()
{
    l[1] = 0, r[0] = 1;//* 初始化 第一个点的右边是 1   第二个点的左边是 0
    idx = 2;//! idx 此时已经用掉两个点了
}

//* 在第 K 个点右边插入一个 X
void add(int k, int x)
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k]; //todo 这边的 k 不加 1 ， 输入的时候 k+1 就好
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}//! 当然在 K 的左边插入一个数 可以再写一个 ， 也可以直接调用我们这个函数，在 k 的左边插入一个 数 等价于在 l[k] 的右边插入一个数 add(l[k],x)

//*删除第 k个 点
void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main(void)
{
    ios::sync_with_stdio(false);
    cin >> m;

    init();

    while(m--)
    {
        string op;
        cin >> op;
        int k, x;
        if(op=="R")
        {
            cin >> x;
            add(l[1], x); //!   0和 1 只是代表 头和尾  所以   最右边插入 只要在  指向 1的 那个点的右边插入就可以了
        }
        else if(op=="L")//! 同理  最左边插入就是 在指向 0的数的左边插入就可以了   也就是可以直接在 0的 有右边插入
        {
            cin >> x;
            add(0, x);
        }
        else if(op=="D")
        {
            cin >> k;
            remove(k + 1);
        }
        else if(op=="IL")
        {
            cin >> k >> x;
            add(l[k + 1], x);
        }
        else
        {
            cin >> k >> x;
            add(k + 1, x);
        }
    }
    for(int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';

    return 0;
}

栈（先进后出）

用数组模拟：

1
2
3
4
5
6
7
8
9
10
11
12
13
// tt表示栈顶
int stk[N], tt = 0;
// 向栈顶插入一个数
stk[ ++ tt] = x;
// 从栈顶弹出一个数
tt -- ;
// 栈顶的值
stk[tt];
// 判断栈是否为空，如果 tt > 0，则表示不为空
if (tt > 0)
{

}

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int N=100010;
int stk[N],tt;

int main(){
    int m;
    cin>>m;
    while(m--){
        string op;
        int x;
        cin>>op;
        if(op=="push"){
            cin>>x;
            stk[tt++]=x;
        }else if(op=="pop"){
            tt--;
        }else if(op=="query"){
            cout<<stk[tt-1]<<endl;
        }else{
            if(!tt)cout<<"YES"<<endl;
            else cout<<"NO"<<endl;
        }
    }
    return 0;
}

应用：表达式求值
表达式求值问题的核心思路：

  • 用两个栈来维护表达式，一个栈用来处理数，一个用来处理运算符
  • 当运算符入栈时和栈顶的运算符比较
    • 如果栈顶的运算符优先级低，新运算符入栈
    • 否则，先出栈并计算，新的运算符在入栈
  • 根据存在的运算符建立优先级表
  • 计算步骤：
    • 表达式字符串根据顺序入栈
    • 当判断到需要进行计算时，从数字栈顶取出两个数作为操作数
    • 根据运算符的运算法则进行计算，将结果入栈
      示例：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <stack>
#include <string>
#include <unordered_map>
using namespace std;

stack<int> num;
stack<char> op;

//优先级表
unordered_map<char, int> h{ {'+', 1}, {'-', 1}, {'*',2}, {'/', 2} };


void eval()//求值
{
    int a = num.top();//第二个操作数
    num.pop();

    int b = num.top();//第一个操作数
    num.pop();

    char p = op.top();//运算符
    op.pop();

    int r = 0;//结果

    //计算结果
    if (p == '+') r = b + a;
    if (p == '-') r = b - a;
    if (p == '*') r = b * a;
    if (p == '/') r = b / a;

    num.push(r);//结果入栈
}

int main()
{
    string s;//读入表达式
    cin >> s;

    for (int i = 0; i < s.size(); i++)
    {
        if (isdigit(s[i]))//数字入栈
        {
            int x = 0, j = i;//计算数字
            while (j < s.size() && isdigit(s[j]))
            {
                x = x * 10 + s[j] - '0';
                j++;
            }
            num.push(x);//数字入栈
            i = j - 1;
        }
        //左括号无优先级，直接入栈
        else if (s[i] == '(')//左括号入栈
        {
            op.push(s[i]);
        }
        //括号特殊，遇到左括号直接入栈，遇到右括号计算括号里面的
        else if (s[i] == ')')//右括号
        {
            while(op.top() != '(')//一直计算到左括号
                eval();
            op.pop();//左括号出栈
        }
        else
        {
            while (op.size() && h[op.top()] >= h[s[i]])//待入栈运算符优先级低，则先计算
                eval();
            op.push(s[i]);//操作符入栈
        }
    }
    while (op.size()) eval();//剩余的进行计算
    cout << num.top() << endl;//输出结果
    return 0;
}

单调栈

常见模型：找出每个数左边离它最近的比它大/小的数，当该元素可以入栈的时候，栈顶元素就是它左侧第一个比它小的元素。

1
2
3
4
5
6
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//找出每个数左边离它最近的比它大/小的数
stack<int> stk;
int main(){
    int n;
    cin >> n;
    stk.push(-1);
    for (int i = 0; i < n; i ++){
        int x;
        cin >> x;
        while (stk.size() && stk.top() >= x) stk.pop();
        cout << stk.top() << " ";
        stk.push(x);
    }
    return 0;
}

队列（先进后出）

就是一个特殊的数组。这个数组，最前面叫队头，最后面叫队尾。只允许在最后面添加元素，只允许在最前面删除元素。

普通队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// hh 表示队头，tt表示队尾
int q[N], hh = 0, tt = -1;

// 向队尾插入一个数
q[ ++ tt] = x;

// 从队头弹出一个数
hh ++ ;

// 队头的值
q[hh];

// 判断队列是否为空，如果 hh <= tt，则表示不为空
if (hh <= tt)
{

}

循环队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// hh 表示队头，tt表示队尾的后一个位置
int q[N], hh = 0, tt = 0;

// 向队尾插入一个数
q[tt ++ ] = x;
if (tt == N) tt = 0;

// 从队头弹出一个数
hh ++ ;
if (hh == N) hh = 0;

// 队头的值
q[hh];

// 判断队列是否为空，如果hh != tt，则表示不为空
if (hh != tt)
{

}

单调队列(滑动窗口)

什么是滑动窗口：滑动窗口是一种算法思想，就像在数据序列（可以是数组、字符串等 ）上放一个大小固定或可变的 “窗口”。这个窗口会在数据序列上按照一定规则滑动，在滑动过程中，通过计算窗口内数据满足的条件（比如求和、计数等），来高效解决诸如寻找满足特定条件的最短子数组、最大子数组和等问题
常见模型：找出滑动窗口中的最大值/最小值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
分析：如果当前的滑动窗口中有两个下标 i 和 j ，其中i在j的左侧（i<j），并且i对应的元素不大于j对应的元素（nums[i]≤nums[j]），则：

当滑动窗口向右移动时，只要 i 还在窗口中，那么 j 一定也还在窗口中。这是由于 i 在 j 的左侧所保证的。

因此，由于 nums[j] 的存在，nums[i] 一定不会是滑动窗口中的最大值了，我们可以将nums[i]永久地移除。
解题思路：因此我们可以使用一个队列存储所有还没有被移除的下标。在队列中，这些下标按照从小到大的顺序被存储，并且它们在数组nums中对应的值是严格单调递减的。

当滑动窗口向右移动时，我们需要把一个新的元素放入队列中。

为了保持队列的性质，我们会不断地将新的元素与队尾的元素相比较，如果新元素大于等于队尾元素，那么队尾的元素就可以被永久地移除，我们将其弹出队列。我们需要不断地进行此项操作，直到队列为空或者新的元素小于队尾的元素。

由于队列中下标对应的元素是严格单调递减的，因此此时队首下标对应的元素就是滑动窗口中的最大值。

窗口向右移动的时候。因此我们还需要不断从队首弹出元素保证队列中的所有元素都是窗口中的，因此当队头元素在窗口的左边的时候，弹出队头。

// 题解摘自于作者：Hasity
// 链接：https://www.acwing.com/solution/content/97229/

注意事项：

  1. 解决队首已经出窗口的问题;
  2. 解决队尾与当前元素 a[i]不满足单调性的问题;
  3. 将当前元素下标加入队尾;
  4. 如果满足条件则输出结果;
1
2
3
4
5
6
7
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;
    q[ ++ tt] = i;
}

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <cstring>
#include <algorithm>
#include <deque>
using namespace std;

const int N = 1000010;
int a[N];
int main()
{
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i ++ ) cin >> a[i];//读入数据
    deque<int> q;
    for(int i = 1; i <= n; i++)
    {
        while(q.size() && q.back() > a[i]) //新进入窗口的值小于队尾元素，则队尾出队列
            q.pop_back();
        q.push_back(a[i]);//将新进入的元素入队
        if(i - k >= 1 && q.front() == a[i - k])//若队头是否滑出了窗口，队头出队
            q.pop_front();
        if(i >= k)//当窗口形成，输出队头对应的值
            cout << q.front() <<" ";
    }
    q.clear();
    cout << endl;

    //最大值亦然
    for(int i = 1; i <= n; i++)
    {
        while(q.size() && q.back() < a[i]) q.pop_back();
        q.push_back(a[i]);
        if(i - k >= 1 && a[i - k] == q.front()) q.pop_front();
        if(i >= k) cout << q.front() << " ";

    }
}


KMP 字符串匹配

作用：

  1. 字符串模式匹配：判断一个模式串（子串）是否存在于一个主串中，以及找到模式串在主串中所有出现的位置。
  2. 预处理模式串构建 “部分匹配表，能够在匹配过程中跳过一些不可能匹配的位置，从而将时间复杂度从 O (n*m)（n 为主串长度，m 为模式串长度）优化到 O (n+m)。
  3. 解决字符串相关问题：
  • 查找字符串中重复出现的子串
  • 判断一个字符串是否为另一个字符串的子串
  • 计算字符串的前缀函数，用于其他字符串算法中

核心思想:在每次失配时，不是把 p 串往后移一位，而是把 p 串往后移动至下一次可以和前面部分匹配的位置，这样就可以跳过大多数的失配步骤。而每次 p 串移动的步数就是通过查找 next[ ]数组确定的。

next 数组：对 next[ j ] ，是 p[ 1, j ]串中前缀和后缀相同的最大长度（部分匹配值），即 p[ 1, next[ j ] ] = p[ j - next[ j ] + 1, j ]。
KMP 的实现：求 next 数组和匹配字符串。
下标从 1 开始的 kmp 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// s[]是长文本，p[]是模式串，n是s的长度，m是p的长度
求模式串的Next数组：
for (int i = 2, j = 0; i <= m; i ++ )
{
    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 <= n; i ++ )
{
    while (j && s[i] != p[j + 1]) j = ne[j];
    if (s[i] == p[j + 1]) j ++ ;
    if (j == m)
    {
        j = ne[j];
        // 匹配成功后的逻辑
    }
}

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
const int N = 100010, M = 1000010;
int n, m;
int ne[N];
char s[M], p[N];
int main()
{
    cin >> n >> p + 1 >> m >> s + 1;
    for (int i = 2, j = 0; i <= n; i ++ )
    {
        while (j && p[i] != p[j + 1]) j = ne[j];
        if (p[i] == p[j + 1]) j ++ ;
        ne[i] = j;
    }//处理ne数组
    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)
        {
            printf("%d ", i - n);
            j = ne[j];
        }
    }//匹配算法
    return 0;
}

下标从 0 开始的 kmp 算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
const int N = 1000010;

int n, m;
char s[N], p[N];
int ne[N];

int main()
{
    cin >> m >> p >> n >> s;
    ne[0] = -1;
    for (int i = 1, j = -1; i < m; i ++ )
    {
        while (j >= 0 && p[j + 1] != p[i]) j = ne[j];
        if (p[j + 1] == p[i]) j ++ ;
        ne[i] = j;
    }
    for (int i = 0, j = -1; i < n; i ++ )
    {
        while (j != -1 && s[i] != p[j + 1]) j = ne[j];
        if (s[i] == p[j + 1]) j ++ ;
        if (j == m - 1)
        {
            cout << i - j << ' ';
            j = ne[j];
        }
    }
    return 0;
}

二叉树的存储和遍历

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
const int N = 1e6 + 10;

// 二叉树的存储,l数组为左节点,r数组为右结点
int l[N], r[N];
// 存储节点的数据
char w[N];
// 节点的下标指针
int idx = 0;

// 先序创建
int pre_create(int n) {
    cin >> w[n];
    if (w[n] == '#') return -1;
    l[n] = pre_create(++idx);
    r[n] = pre_create(++idx);
    return n;
}

// 中序创建
int in_create(int n) {
    if (w[n] == '#') return -1;
    l[n] = in_create(++idx);
    cin >> w[n];
    r[n] = in_create(++idx);
    return n;
}

// 后序创建
int back_create(int n) {
    if (w[n] == '#') return -1;
    l[n] = back_create(++idx);
    r[n] = back_create(++idx);
    cin >> w[n];
    return n;
}

// 先序遍历
void pre_print(int n){
    if (w[n] != '#') cout << w[n] << ' ';
    if (l[n] > 0) pre_print(l[n]);
    if (r[n] > 0) pre_print(r[n]);
}

// 中序遍历
void in_print(int n){
    if (l[n] > 0) in_print(l[n]);
    if (w[n] != '#') cout << w[n] << ' ';
    if (r[n] > 0) in_print(r[n]);
}

// 后序遍历
void back_print(int n){
    if (l[n] > 0) back_print(l[n]);
    if (r[n] > 0) back_print(r[n]);
    if (w[n] != '#') cout << w[n] << ' ';
}

// 层序遍历
void bfs(int root){
    queue<int> que;
    que.push(root);
    while (!que.empty()) {
        int t = que.front();
        cout << w[t] << ' ';
        que.pop();
        if (l[t] > 0 && w[l[t]] != '#')
            que.push(l[t]);
        if (r[t] > 0 && w[r[t]] != '#')
            que.push(r[t]);
    }
}

Tire 树

又称字典树、前缀树
高效地存储和查找字符串集合的数据结构,Trie 树是一种多叉树的结构，每个节点保存一个字符，一条路径表示一个字符串。
作用：

  1. 字符串前缀匹配：高效查找具有相同前缀的所有字符串
  2. 字符串快速检索：判断一个字符串是否存在于集合中，时间复杂度为 O (k)（k 为字符串长度），比哈希表在处理大量字符串时更有优势。
  3. 词频统计：统计某个字符串在集合中出现的次数，只需在 Trie 树的节点中记录计数信息。
  4. 自动补全与拼写检查：在搜索引擎、输入法等场景中，根据输入的前缀提示可能的完整字符串，或检查输入的字符串是否存在拼写错误。
  5. 字符串排序：对一组字符串进行排序时，通过 Trie 树的遍历（如先序遍历）可直接得到字典序排列，时间复杂度为 O (nk)

Trie 树的核心特点是通过共享字符串的公共前缀来节省存储空间，同时利用前缀特性实现高效的字符串操作，特别适合处理大量字符串且存在共同前缀的场景。

Trie 树中有个二维数组 son[N][26]，表示当前结点的儿子，如果没有的话，可以等于++idx。Trie 树本质上是一颗多叉树，对于字母而言最多有 26 个子结点。所以这个数组包含了两条信息。比如：son[1][0]=2 表示 1 结点的一个值为 a 的子结点为结点 2;如果 son[1][0] = 0，则意味着没有值为 a 子结点。这里的 son[N][26]相当于链表中的 ne[N]。

示例：

核心函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量

// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}

// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
const int N = 100010;

int son[N][26], cnt[N], idx;
char str[N];

void insert(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++ idx;
        p = son[p][u];
    }
    cnt[p] ++ ;
}//插入

int query(char *str)
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}//查询

int main()
{
    int n;
    scanf("%d", &n);
    while (n -- )
    {
        char op[2];
        scanf("%s%s", op, str);
        if (*op == 'I') insert(str);
        else printf("%d\n", query(str));
    }

    return 0;
}

应用：最大异或对

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include<iostream>
#include<algorithm>
using namespace std;
int const N=100010,M=31*N;

int n;
int a[N];
int son[M][2],idx;
//M代表一个数字串二进制可以到多长

void insert(int x)
{
    int p=0;  //根节点
    for(int i=30;i>=0;i--)
    {
        int u=x>>i&1;   /////取X的第i位的二进制数是什么  x>>k&1(前面的模板)
        if(!son[p][u]) son[p][u]=++idx; ///如果插入中发现没有该子节点,开出这条路
        p=son[p][u]; //指针指向下一层
    }
}
int search(int x)
{
    int p=0;int res=0;
    for(int i=30;i>=0;i--)
    {
        // 从最大位开始找
        int u=x>>i&1;
        if(son[p][!u]) //如果当前层有对应的不相同的数
        {   //p指针就指到不同数的地址

          p=son[p][!u];
          res=res*2+1;
             //相当左移一位  然后如果找到对应位上不同的数res+1
        }
        else
        {
            p=son[p][u];
            res=res*2+0;
        }
    }
    return res;
}
int main(void)
{
    cin.tie(0);
    cin>>n;
    idx=0;
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
        insert(a[i]);
    }
    int res=0;
    for(int i=0;i<n;i++)
    {
        res=max(res,search(a[i]));  ///search(a[i])查找的是a[i]值的最大与或值
    }
    cout<<res<<endl;
}

并查集

开始时每个集合都是一个独立的集合,每个节点都指向自己的祖宗节点，当集合只有本身时，自身就指向自己。若想使得某两节点合并，那么只需要指向相同的祖宗就可以实现。
并查集的核心优势是通过路径压缩和按秩合并两种优化策略，使查询和合并操作的时间复杂度接近常数级适合处理大规模数据。
作用：

  1. 判断元素是否属于同一集合
  2. 合并多个集合
  3. 处理动态连通性问题
  4. 解决等价类问题：识别具有等价关系的元素集合（如在数学中判断多个元素间的等价关系，或在图像分割中标记连通区域）。
  5. 优化某些算法的实现：在 Kruskal 算法（最小生成树）、求无向图的连通分量等场景中，用于快速判断边是否会形成环。

朴素并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}

// 初始化，假定节点编号是1~n
for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合：
p[find(a)] = find(b);

维护 size 的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

    // 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    // 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

    // 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

维护到祖宗节点距离的并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int p[N], d[N];
   //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

   // 返回x的祖宗节点
   int find(int x)
   {
       if (p[x] != x)
       {
           int u = find(p[x]);
           d[x] += d[p[x]];
           p[x] = u;
       }
       return p[x];
   }

   // 初始化，假定节点编号是1~n
   for (int i = 1; i <= n; i ++ )
   {
       p[i] = i;
       d[i] = 0;
   }

   // 合并a和b所在的两个集合：
   p[find(a)] = find(b);
   d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const int N=100010;
int p[N],n,m;

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;
    while(m--){
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='M')p[find(a)]=find(b);
        else {
            if(find(a)==find(b))puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

堆（完全二叉树）

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值， 这种情况称为大顶堆，注意:没有要求结点的左孩子的值和右孩子的值的大小关系。

每个结点的值都小于或等于其左右孩子结点的值， 这种情况称为小顶堆。
作用：

  1. 堆是实现优先队列的最佳数据结构，能快速获取和删除最大 / 最小值（大顶堆取最大值，小顶堆取最小值），时间复杂度为 O (1)，插入和删除操作复杂度为 O (log n)。
  2. Top K 问题：在海量数据中快速找到前 K 个最大 / 最小元素
  3. 中位数查找：维护两个堆（一个大顶堆存较小一半元素，一个小顶堆存较大一半元素），能在 O (1) 时间内获取当前数据集的中位数，插入操作复杂度为 O (log n)。
  4. 堆排序：利用堆的特性进行排序，时间复杂度为 O (n log n)，是一种原地排序算法（仅需 O (1) 额外空间）。
  5. 任务调度：在操作系统中用于进程调度，根据优先级动态选择下一个要执行的任务。
    操作：
  6. 插入一个数，数据的插入都是插入到堆尾，然后再 up
  7. 求集合的最小或最大值
  8. 删除最小值
  9. 删除，修改任意一个元素，将该元素与堆尾元素进行交换，然后在该位置进行 up()或 down()操作，删除队尾元素

核心函数：down(x),up(x)向上或向下调整一个数
使用一维数组模拟堆：
根节点位于头部，设某个元素的坐标为 i，那么它的左儿子为 2i，右儿子为 2i+1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
// h[N]存储堆中的值, h[1]是堆顶，x的左儿子是2x, 右儿子是2x + 1
// ph[k]存储第k个插入的点在堆中的位置
// hp[k]存储堆中下标是k的点是第几个插入的
int h[N], ph[N], hp[N], size;

// 交换两个点，及其映射关系
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 <= size && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        heap_swap(u, t);
        down(t);
    }
}

void up(int u)
{
    while (u / 2 && h[u] < h[u / 2])
    {
        heap_swap(u, u / 2);
        u >>= 1;
    }
}

// O(n)建堆
for (int i = n / 2; i; i -- ) down(i);

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
const int N=100010;
int heap[N],cnt;

void down(int u){
    int t=u;
    if(u*2<=cnt&&heap[u*2]<=heap[t])t=u*2;
    if(u*2+1<=cnt&&heap[u*2+1]<=heap[t])t=u*2+1;
    if(t!=u){
        swap(heap[t],heap[u]);
        down(t);
    }
}//down操作

void up(int u){
    while(u/2&&heap[u/2]>heap[u]){
        swap(heap[u/2],heap[u]);
        u>>=1;
    }
}//up操作

int main(){
    int n,m;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)scanf("%d",&heap[i]);
    cnt=n;
    for(int i=n/2;i;i--)down(i);
    while(m--){
        printf("%d ",heap[1]);
        heap[1]=heap[cnt--];
        down(1);
    }
    return 0;
}

哈希 hash

哈希（Hash）是一种将任意长度的输入数据映射到固定长度输出的技术
作用：

  1. 快速查找与检索：通过哈希函数将键（Key）映射到哈希表的索引，实现 O (1) 平均时间复杂度的插入、删除和查找操作。
  2. 数据去重：对数据计算哈希值，通过比较哈希值快速判断数据是否重复
  3. 数据完整性校验：计算文件或消息的哈希值（如 MD5、SHA 系列），通过比对哈希值判断数据是否被篡改。

一般 hash（用数组模拟）

拉链法

alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int h[N], e[N], ne[N], idx;

// 向哈希表中插入一个数
void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx ++ ;
}

// 在哈希表中查询某个数是否存在
bool find(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i != -1; i = ne[i])
        if (e[i] == x)
            return true;

    return false;
}

开放寻址法
alt text

1
2
3
4
5
6
7
8
9
10
11
12
13
int h[N];

// 如果x在哈希表中，返回x的下标；如果x不在哈希表中，返回x应该插入的位置
int find(int x)
{
    int t = (x % N + N) % N;
    while (h[t] != null && h[t] != x)
    {
        t ++ ;
        if (t == N) t = 0;
    }
    return t;
}

字符串 hash

思想：

  1. 将字符串看成 P 进制的数,实现不同的字符串映射到不同的数字。（P 常取 131 或 13331，冲突概率低）
  2. 对 P 进制的数取模（1p^3+2p^2+3p^1+4p^0）mod Q（Q 取 2^64）

由上式可得：
使用 unsigned long long 来存储 h[],可实现自动取模

  1. 某个子串的哈希值：h[l,r]=h[R]-h[L]*p^(R-L+1)
  2. 前缀和公式：h[i+1]=h[i]*p+str[i];
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include<iostream>
#include<cstdio>
#include<string>
using namespace std;
typedef unsigned long long ULL;
const int N = 1e5+5,P = 131;//131 13331
ULL h[N],p[N];

// h[i]前i个字符的hash值
// 字符串变成一个p进制数字，体现了字符+顺序，需要确保不同的字符串对应不同的数字
// P = 131 或  13331 Q=2^64，在99%的情况下不会出现冲突
// 使用场景： 两个字符串的子串是否相同
ULL query(int l,int r){
    return h[r] - h[l-1]*p[r-l+1];
}
int main(){
    int n,m;
    cin>>n>>m;
    string x;
    cin>>x;

    //字符串从1开始编号，h[1]为前一个字符的哈希值
    p[0] = 1;
    h[0] = 0;
    for(int i=0;i<n;i++){
        p[i+1] = p[i]*P;
        h[i+1] = h[i]*P +x[i];      //前缀和求整个字符串的哈希值
    }

    while(m--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(query(l1,r1) == query(l2,r2)) printf("Yes\n");
        else printf("No\n");

    }
    return 0;
}


容器 STL

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
vector, 变长数组，倍增的思想
    size()  返回元素个数
    empty()  返回是否为空
    clear()  清空
    front()/back()
    push_back()/pop_back()
    begin()/end()
    []
    支持比较运算，按字典序

pair<int, int>
    first, 第一个元素
    second, 第二个元素
    支持比较运算，以first为第一关键字，以second为第二关键字（字典序）

string，字符串
    size()/length()  返回字符串长度
    empty()
    clear()
    substr(起始下标，(子串长度))  返回子串
    c_str()  返回字符串所在字符数组的起始地址

queue, 队列
    size()
    empty()
    push()  向队尾插入一个元素
    front()  返回队头元素
    back()  返回队尾元素
    pop()  弹出队头元素

priority_queue, 优先队列，默认是大根堆
    size()
    empty()
    push()  插入一个元素
    top()  返回堆顶元素
    pop()  弹出堆顶元素
    定义成小根堆的方式：priority_queue<int, vector<int>, greater<int>> q;

stack, 栈
    size()
    empty()
    push()  向栈顶插入一个元素
    top()  返回栈顶元素
    pop()  弹出栈顶元素

deque, 双端队列
    size()
    empty()
    clear()
    front()/back()
    push_back()/pop_back()
    push_front()/pop_front()
    begin()/end()
    []

set, map, multiset, multimap, 基于平衡二叉树（红黑树），动态维护有序序列
    size()
    empty()
    clear()
    begin()/end()
    ++, -- 返回前驱和后继，时间复杂度 O(logn)

    set/multiset
        insert()  插入一个数
        find()  查找一个数
        count()  返回某一个数的个数
        erase()
            (1) 输入是一个数x，删除所有x   O(k + logn)
            (2) 输入一个迭代器，删除这个迭代器
        lower_bound()/upper_bound()
            lower_bound(x)  返回大于等于x的最小的数的迭代器
            upper_bound(x)  返回大于x的最小的数的迭代器
    map/multimap
        insert()  插入的数是一个pair
        erase()  输入的参数是pair或者迭代器
        find()
        []  注意multimap不支持此操作。 时间复杂度是 O(logn)
        lower_bound()/upper_bound()

unordered_set, unordered_map, unordered_multiset, unordered_multimap, 哈希表
    和上面类似，增删改查的时间复杂度是 O(1)
    不支持 lower_bound()/upper_bound()， 迭代器的++，--

bitset, 圧位
    bitset<10000> s;
    ~, &, |, ^
    >>, <<
    ==, !=
    []

    count()  返回有多少个1

    any()  判断是否至少有一个1
    none()  判断是否全为0

    set()  把所有位置成1
    set(k, v)  将第k位变成v
    reset()  把所有位变成0
    flip()  等价于~
    flip(k) 把第k位取反