链表

单链表

题干

实现一个单链表，链表初始为空，支持三种操作：

  1. 向链表头插入一个数；
  2. 删除第 个插入的数后面的一个数；
  3. 在第 个插入的数后插入一个数。

现在要对该链表进行 次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第 个插入的数并不是指当前链表的第 个数。例如操作过程中一共插入了 个数，则按照插入的时间顺序，这 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 个插入的数。

输入格式

第一行包含整数 ，表示操作次数。
接下来 行，每行包含一个操作命令，操作命令可能为以下几种：

  1. H x，表示向链表头插入一个数 x。
  2. D k，表示删除第 个插入的数后面的数（当 为 0 时，表示删除头结点）。
  3. I k x，表示在第 个插入的数后面插入一个数 x（此操作中 均大于 0）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围


所有操作保证合法。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6

输出样例：

1
6 4 6 5

思路分析

使用数组模拟单链表，e[] 存储节点的值，ne[] 存储下一个节点的下标，head 存储头节点下标，idx 记录当前可用节点下标。
注意：e[] 和 ne[] 使用的下标都是 idx 的值；均从 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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;

int e[N], ne[N], idx = 1, head;

void add(int x)
{
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

void del(int k)
{
    if (k)
        ne[k] = ne[ne[k]];
    else
        head = ne[head];
}

void insert(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

int main()
{
    int m;
    cin >> m;
    while (m--)
    {
        char opt;
        int k, x;
        cin >> opt;
        if (opt == 'H')
        {
            cin >> x;
            add(x);
        }
        else if (opt == 'D')
        {
            cin >> k;
            del(k);
        }
        else
        {
            cin >> k >> x;
            insert(k, x);
        }
    }
    for (int i = head; i; i = ne[i])
    {
        cout << e[i] << ' ';
    }
}

双链表

题干

实现一个双链表，双链表初始为空，支持 种操作：

  1. 在最左侧插入一个数；
  2. 在最右侧插入一个数；
  3. 将第 个插入的数删除；
  4. 在第 个插入的数左侧插入一个数；
  5. 在第 个插入的数右侧插入一个数

现在要对该链表进行 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 个插入的数并不是指当前链表的第 个数。例如操作过程中一共插入了 个数，则按照插入的时间顺序，这 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 个插入的数。

输入格式

第一行包含整数 ，表示操作次数。

接下来 行，每行包含一个操作命令，操作命令可能为以下几种：

  1. L x，表示在链表的最左端插入数 。
  2. R x，表示在链表的最右端插入数 。
  3. D k，表示将第 个插入的数删除。
  4. IL k x，表示在第 个插入的数左侧插入一个数。
  5. IR k x，表示在第 个插入的数右侧插入一个数。

输出格式

共一行，将整个链表从左到右输出。

数据范围


所有操作保证合法。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

输出样例：

1
8 7 7 3 2 9

思路分析

双链表与单链表的不同之处在于能同时找到前驱和后继节点，因此用数组 l[] 和 r[] 分别存储前驱和后继节点的下标。
初始时，用 idx = 0 表示链表头节点，idx = R 表示链表尾节点，其中 R 是一个大于所有可能插入节点下标的数；初始化时将头节点的后继指向尾节点，尾节点的前驱指向头节点。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, L = 0, R = 1e5 + 5;

int e[N], l[N], r[N], idx = 1;

void init()
{
    r[0] = R;
    l[R] = 0;
}

void insert(int k, int x) // 在第k个插入的数右边插入一个数
{
    e[idx] = x;
    l[idx] = k;
    r[idx] = r[k];
    l[r[k]] = idx;
    r[k] = idx;
    idx++;
}

void del(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main()
{
    init();
    int m;
    cin >> m;
    while (m--)
    {
        string opt;
        int k, x;
        cin >> opt;
        if (opt == "L")
        {
            cin >> x;
            insert(0, x);
        }
        else if (opt == "R")
        {
            cin >> x;
            insert(l[R], x);
        }
        else if (opt == "IL")
        {
            cin >> k >> x;
            insert(l[k], x);
        }
        else if (opt == "IR")
        {
            cin >> k >> x;
            insert(k, x);
        }
        else
        {
            cin >> k;
            del(k);
        }
    }
    for (int i = r[0]; i != R; i = r[i])
        cout << e[i] << ' ';
}

栈

模拟栈

题干

实现一个栈，栈初始为空，支持四种操作：

  1. push x – 向栈顶插入一个数 ；
  2. pop – 从栈顶弹出一个数；
  3. empty – 判断栈是否为空；
  4. query – 查询栈顶元素。

现在要对栈进行 个操作，其中的每个操作 和操作 都要输出相应的结果。

输入格式

第一行包含整数 ，表示操作次数。
接下来 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示栈顶元素的值。

数据范围

,

所有操作保证合法，即不会在栈为空的情况下进行 pop 或 query 操作。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10
push 5
query
push 6
pop
query
pop
empty
push 4
query
empty

输出样例：

1
2
3
4
5
5
5
YES
4
NO

思路分析

使用数组模拟栈，stk[] 存储栈中元素，idx 记录栈顶元素下标，从 1 开始存。

  • idx-- 为弹出栈顶元素
  • stk[idx] 为取出栈顶元素
  • stk[++idx] 为插入栈顶元素
  • idx == 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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 9;

int stk[N];
int idx = 0;

void push(int x)
{
    stk[++idx] = x;
}

void pop()
{
    idx--;
}

void empty()
{
    if (idx == 0)
        cout << "YES" << '\n';
    else
        cout << "NO" << '\n';
}

void query()
{
    cout << stk[idx] << '\n';
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int m;
    cin >> m;
    while (m--)
    {
        string opt;
        int x;
        cin >> opt;
        if (opt == "push")
        {
            cin >> x;
            push(x);
        }
        else if (opt == "pop")
        {
            pop();
        }
        else if (opt == "empty")
        {
            empty();
        }
        else if (opt == "query")
        {
            query();
        }
    }
}

队列

模拟队列

题干

实现一个队列，队列初始为空，支持四种操作：

  1. push x – 向队尾插入一个数 ；
  2. pop – 从队头弹出一个数；
  3. empty – 判断队列是否为空；
  4. query – 查询队头元素。

现在要对队列进行 个操作，其中的每个操作 和操作 都要输出相应的结果。

输入格式

第一行包含整数 ，表示操作次数。
接下来 行，每行包含一个操作命令，操作命令为 push x，pop，empty，query 中的一种。

输出格式

对于每个 empty 和 query 操作都要输出一个查询结果，每个结果占一行。

其中，empty 操作的查询结果为 YES 或 NO，query 操作的查询结果为一个整数，表示队头元素的值。

数据范围

,
,
所有操作保证合法，即不会在队列为空的情况下进行 pop 或 query 操作。

输入样例：

1
2
3
4
5
6
7
8
9
10
11
10
push 6
empty
query
pop
empty
push 3
push 4
pop
query
push 6

输出样例：

1
2
3
4
NO
6
YES
4

思路分析

使用数组模拟队列，que[] 存储队列中元素，从 1 开始存；hh 记录队头下标，从 1 开始；tt 记录队尾下标，从 0 开始。

  • que[++tt] 为插入队尾元素
  • hh++ 为弹出队头元素
  • que[hh] 为取出队头元素
  • hh >= tt 判断队列是否为空
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
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5 + 9;

int que[N];
int hh = 1, tt = 0;

void push(int x)
{
    que[++tt] = x;
}

bool empty()
{
    if (hh > tt)
    {
        cout << "YES" << '\n';
        return true;
    }
    cout << "NO" << '\n';
    return false;
}

void pop()
{
    if (hh <= tt)
        hh++;
}

int query()
{
    cout << que[hh] << '\n';
    return que[hh];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int m;
    cin >> m;
    while (m--)
    {
        string opt;
        int x;
        cin >> opt;
        if (opt == "push")
        {
            cin >> x;
            push(x);
        }
        else if (opt == "pop")
        {
            pop();
        }
        else if (opt == "empty")
        {
            empty();
        }
        else if (opt == "query")
        {
            query();
        }
    }
}

单调栈/单调队列

单调栈

题干

给定一个长度为 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 。

输入格式

第一行包含整数 ，表示数列长度。

第二行包含 个整数，表示整数数列。

输出格式

共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围


数列中元素

输入样例：

1
2
5
3 4 2 7 5

输出样例：

1
-1 3 -1 2 2

思路分析

如果直接遍历会超时，考虑一个事情：例如数组第一位是 ，而第二位是 ，那么这个 永远不可能被选到；因此当 进来时，我们应该将 弹出，因为它不可能成为任何数字的选择结果。需要将顶部元素弹出，我们可以用栈来实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;

int stk[N], idx;

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        int x;
        cin >> x;
        while (x <= stk[idx])
            idx--;
        if (idx)
            cout << stk[idx] << ' ';
        else
            cout << -1 << ' ';
        stk[++idx] = x;
    }
}

单调队列

题干

给定一个大小为 的数组。

有一个大小为 的滑动窗口，它从数组的最左边移动到最右边。

你只能在窗口中看到 个数字。
每次滑动窗口向右移动一个位置。

以下是一个例子：

该数组为 [1 3 -1 -3 5 3 6 7]， 为 。

窗口位置 最小值 最大值
[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

你的任务是确定滑动窗口位于每个位置时，窗口中的最大值和最小值。

输入格式

输入包含两行。

第一行包含两个整数 和 ，分别代表数组长度和滑动窗口的长度。

第二行有 个整数，代表数组的具体数值。

同行数据之间用空格隔开。

输出格式

输出包含两个。

第一行输出，从左至右，每个位置滑动窗口中的最小值。

第二行输出，从左至右，每个位置滑动窗口中的最大值。

数据范围

,

输入样例：

1
2
8 3
1 3 -1 -3 5 3 6 7

输出样例：

1
2
-1 -3 -3 -3 3 3
3 3 5 5 6 7

思路分析

最大值和最小值可以分开来求，用类似上一题的思想：
当求最小值时，如果后面的元素更小，由于后面的元素能存活的时间更久且更小，因此后方元素在的时候前方元素永远不会被选到，直接将前方元素弹出即可；由于一个数前方不可能有比它大的数，因此直接取出此时的队头就是最小值。
由于要从前方弹出、后方进入，因此选择双端队列 deque。

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
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;

int a[N], dq[N], hh = 1, tt = 0;
// dq存的是下标

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n, k;
    cin >> n >> k;
    for (int i = 1; i <= n; i++)
        cin >> a[i];

    // 先求最小值
    for (int i = 1; i <= n; i++)
    {
        // 表示到 i-k+1 ~ i 的最小值
        while (hh <= tt && dq[hh] <= i - k)
            hh++;
        while (hh <= tt && a[i] <= a[dq[tt]])
            tt--;
        dq[++tt] = i;
        if (i >= k)
            cout << a[dq[hh]] << ' ';
    }

    cout << '\n';
    // 再求最大值，记得重置数组
    memset(dq, 0, sizeof dq);
    for (int i = 1; i <= n; i++)
    {
        while (hh <= tt && dq[hh] <= i - k)
            hh++;
        while (hh <= tt && a[i] >= a[dq[tt]])
            tt--;
        dq[++tt] = i;
        if (i >= k)
            cout << a[dq[hh]] << ' ';
    }
}

Trie树

Trie字符串统计

题干

维护一个字符串集合，支持两种操作：

  1. I x 向集合中插入一个字符串 ；
  2. Q x 询问一个字符串在集合中出现了多少次。

共有  个操作，所有输入的字符串总长度不超过 ，字符串仅包含小写英文字母。

输入格式

第一行包含整数 ，表示操作数。

接下来  行，每行包含一个操作指令，指令为 I x 或 Q x 中的一种。

输出格式

对于每个询问指令 Q x，都要输出一个整数作为结果，表示 x 在集合中出现的次数。

每个结果占一行。

数据范围

输入样例：

1
2
3
4
5
6
5
I abc
Q abc
Q ab
I ab
Q ab

输出样例：

1
2
3
1
0
1

思路分析

涉及纯字母、数字等字符种类不多的字符串可以使用Trie树。将一个字符串的每一个字符看成树的每一层，例如 abc 可以看作第一层有一个 a，a 有一个第二层的子节点 b，b 有一个第三层的子节点 c。为了可以确认是否存在某个字符串以及出现次数，加一个 cnt 数组记录字符串结束的结点。

用数组模拟Trie树，son[N][26] 的第一维表示某一个结点编号（每一个结点都有比单独编号，用 idx 记录），第二维表示它的儿子是哪一个字母，son[N][26] 的值表示其子结点编号。如果出现了以某个结点结束的字符串，就给此结点 cnt++。

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
#include <iostream>
using namespace std;
const int N = 1e5 + 10;

int son[N][26];
int cnt[N];
int idx, n;

void insert(string x)
{
	// 默认编号为0的点为树的根节点
    int p = 0;
    for (char ele : x)
    {
        int u = ele - 'a';
        // 如果结点p没有u的子节点，那么就新建一个结点
        if (!son[p][u])
            son[p][u] = ++idx;
        // 然后p变成子结点，进行下一个字符的循环
        p = son[p][u];
    }
    // p落在最后一个字符对应结点，字符串结束，cnt++
    cnt[p]++;
}

int query(string x)
{
    int p = 0;
    for (char ele : x)
    {
        int u = ele - 'a';
        // 如果p没有u的子结点，说明不存在查找的字符串，直接返回0
        if (!son[p][u])
            return 0;
        p = son[p][u];
    }
    // 走到最后一个字符时返回cnt
    return cnt[p];
}

int main()
{
    cin >> n;
    while (n --)
    {
        char opt;
        string x;
        cin >> opt >> x;
        if (opt == 'I')
            insert(x);
        else
            cout << query(x) << '\n';
    }
    return 0;
}

最大异或对

题干

在给定的  个整数 ， 中选出两个进行 （异或）运算，得到的结果最大是多少？

输入格式

第一行输入一个整数 。

第二行输入  个整数 ～。

输出格式

输出一个整数表示答案。

数据范围


输入样例：

1
2
3
1 2 3

输出样例：

1
3

思路分析

要求最大异或对，可以把数字的二进制位当作Trie树，对于每一个新插入的数，将它和前面数形成的Trie树比较，选出其与前面数的最大异或对。由于求的是最大结果，因此高位异或结果为1更重要，所以从树的第一层（除根节点）应该是第31位（范围 ），然后是第30位，依次到第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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 32 * 1e5;

int n, son[N][2];
int idx;

void insert(int x)
{
    int p = 0;
    for (int i = 30; i >= 0; i--)
    {
        int u = x >> i & 1;
        if (!son[p][u])
            son[p][u] = ++idx;
        p = son[p][u];
    }
}

int query(int x)
{
    int p = 0, res = 0;
    for (int i = 30; i >= 0; i--)
    {
        res <<= 1;
        int u = x >> i & 1;
        if (son[p][!u])
        {
            p = son[p][!u];
            res += 1;
        }
        else
            p = son[p][u];
    }
    return res;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    int ans = 0;
    while (n --)
    {
        int x;
        cin >> x;
        ans = max(ans, query(x));
        insert(x);
    }
    cout << ans;
}

并查集

合并集合

题干

一共有  个数，编号是 ，最开始每个数各自在一个集合中。

现在要进行  个操作，操作共有两种：

  1. M a b，将编号为  和  的两个数所在的集合合并，如果两个数已经在同一个集合中，则忽略这个操作；
  2. Q a b，询问编号为  和  的两个数是否在同一个集合中；

输入格式

第一行输入整数  和 。

接下来  行，每行包含一个操作指令，指令为 M a b 或 Q a b 中的一种。

输出格式

对于每个询问指令 Q a b，都要输出一个结果，如果  和  在同一集合内，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

输入样例：

1
2
3
4
5
6
4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4

输出样例：

1
2
3
Yes
No
Yes

思路分析

用一个数组 p[i] 记录结点i的父结点，初始时每一个结点的父结点都是自己。

当合并两个集合时，只需要将一个集合的祖宗节点接入到另一个集合上即可。如果使用

1
2
3
4
5
6
int find(int x) 
{
    if (p[x] != x)
        return find(p[x]);
    return p[x];
}

此时相当于将结点连在其父结点上，如果数据把结点集合都卡成一串会超时，要使用并查集的路径压缩：

1
2
3
4
5
6
int find(int x) 
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

这段代码不仅能返回一个结点的祖宗节点，还能将该节点直接接在其祖宗节点之上，实现近乎 的查找。

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
#include <iostream>
using namespace std;
const int N = 1e5 + 9;

int n, m, p[N];

int find(int x) 
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}


int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        p[i] = i;
    while (m --)
    {
        char opt;
        int a, b;
        cin >> opt >> a >> b;
        if (opt == 'M')
            p[find(a)] = find(b);
        else
            cout << (find(a) == find(b) ? "Yes" : "No") << '\n';
    }
    return 0;
}

连通块中点的数量

给定一个包含  个点（编号为 ）的无向图，初始时图中没有边。

现在要进行  个操作，操作共有三种：

  1. C a b，在点  和点  之间连一条边，a 和 b 可能相等；
  2. Q1 a b，询问点  和点  是否在同一个连通块中，a 和 b 可能相等；
  3. Q2 a，询问点  所在连通块中点的数量；

输入格式

第一行输入整数  和 。

接下来  行，每行包含一个操作指令，指令为 C a b，Q1 a b 或 Q2 a 中的一种。

输出格式

对于每个询问指令 Q1 a b，如果  和  在同一个连通块中，则输出 Yes，否则输出 No。

对于每个询问指令 Q2 a，输出一个整数表示点  所在连通块中点的数量

每个结果占一行。

数据范围

输入样例：

1
2
3
4
5
6
5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5

输出样例：

1
2
3
Yes
2
3

思路分析

和上一题差不多，只不过需要多维护集合的大小。用 cnt[i] 表示 i 所在集合的大小，当执行 p[a] = b 之前先执行 cnt[b] += cnt[a]（a、b都是祖宗节点，查询和转移集合大小都统一用祖宗节点）。注意两句话尽量不要对调，虽然下方的代码对调不会出错，但是如果写的是 cnt[find(b)] += cnt[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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <iostream>
using namespace std;
const int N = 1e5 + 9;

int n, m, p[N], cnt[N];

int find(int x) 
{
    if (p[x] != x)
        p[x] = find(p[x]);
    return p[x];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        p[i] = i;
        cnt[i] = 1;
    }
    while (m --)
    {
        string opt;
        int a, b;
        cin >> opt >> a;
        if (opt == "C")
        {
            cin >> b;
            // 找到a、b的祖宗节点
            a = find(a), b = find(b);
            if (a != b)
            {
	            cnt[b] += cnt[a];
                p[a] = b;
            }
        }
        else if (opt == "Q1")
        {
            cin >> b;
            cout << (find(a) == find(b) ? "Yes" : "No") << '\n';
        }
        else
            cout << cnt[find(a)] << '\n';
    }
    return 0;
}

堆

堆排序

输入一个长度为  的整数数列，从小到大输出前  小的数。

输入格式

第一行包含整数  和 。

第二行包含  个整数，表示整数数列。

输出格式

共一行，包含  个整数，表示整数数列中前  小的数。

数据范围

，
数列中元素

输入样例：

1
2
5 3
4 5 1 3 2

输出样例：

1
1 2 3

思路分析

本题可以使用stl中的优先队列，也可以训练一下手写堆。

堆的本质是一棵完全二叉树：除了最后一层外，其他各层都是满的，并且最后一层的叶子结点都依次靠左排列。其次，还要满足：对于小根堆，任一结点的值都 其子结点的值，根节点是最小值；对于大根堆，任一结点的值都 其子结点的值，根节点是最大值。

使用数组模拟堆时，如果当前结点的下标是 ，那么其左子结点下标是 ，右子结点下标是 ，父结点下标是 （向下取整）。

弹出堆顶可以将堆底（编号最大的）删去，再堆将顶变为堆底，然后对堆顶使用down。s

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
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5 + 9;

int heap[N];
int n, m, idx;

// 上升时只需要跟父结点比，比父结点小就交换
void up(int k)
{
    int t = k / 2;
    if (t && heap[t] > heap[k])
    {
        swap(heap[t], heap[k]);
        up(t);
    }
    return;
}

// 下降时需要和两个子结点比，和更小者互换（如果和另一个换了，还要再和最小者换一次）
void down(int k)
{
    int t = k;
    if (2 * k <= idx && heap[t] > heap[2 * k])
        t = 2 * k;
    if (2 * k + 1 <= idx && heap[t] > heap[2 * k + 1])
        t = 2 * k + 1;
    if (t != k)
    {
        swap(heap[t], heap[k]);
        down(t);
    }
}

int pop()
{
    int t = heap[1];
    heap[1] = heap[idx];
    idx--;
    down(1);
    return t;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin >> heap[++idx];
        up(idx);
    }
    while (m --)
        cout << pop() << ' ';
    return 0;
}

哈希表

模拟散列表

题干

维护一个集合，支持如下几种操作：

  1. I x，插入一个整数 ；
  2. Q x，询问整数  是否在集合中出现过；

现在要进行  次操作，对于每个询问操作输出对应的结果。

输入格式

第一行包含整数 ，表示操作数量。

接下来  行，每行包含一个操作指令，操作指令为 I x，Q x 中的一种。

输出格式

对于每个询问指令 Q x，输出一个询问结果，如果  在集合中出现过，则输出 Yes，否则输出 No。

每个结果占一行。

数据范围


输入样例：

1
2
3
4
5
6
5
I 1
I 2
I 3
Q 2
Q 5

输出样例：

1
2
Yes
No

思路分析

使用拉链法哈希表，考虑最接近 的质数：100003（用质数做模可以防止“规律数据”导致的堆积）。将模100003的结果当作哈希表的一个索引，然后对这些索引用邻接表做拉链法。由于数据有正有负，因此要注意对负数的哈希处理：(x % N + N) % N，x%N是为了让其小于N，使得x%N+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
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100003;

int h[N], e[N], ne[N], idx = 1;
int n;

void insert(int x)
{
    int k = (x % N + N) % N;
    e[idx] = x;
    ne[idx] = h[k];
    h[k] = idx++;
}

bool exist(int x)
{
    int k = (x % N + N) % N;
    for (int i = h[k]; i; i = ne[i])
        if (e[i] == x)
            return true;
    return false;
}

int main()
{
    cin >> n;
    while(n --)
    {
        char opt;
        int x;
        cin >> opt >> x;
        if (opt == 'I')
            insert(x);
        else
            cout << (exist(x) ? "Yes" : "No") << '\n';
    }
}

或者使用开放寻址法：创建一个 倍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
31
32
33
34
35
36
37
38
39
40
41
42
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3e5 + 9;
const int null = 0x3f3f3f3f;
// 将数组初始化为很大的数（超过可能存放的数据）

int a[N];

int find(int x)
{
    int k = (x % N + N) % N;
    while (a[k] != null && a[k] != x)
    {
        k++;
        // k到末尾时重置
        if (k == N)
            k = 0;
    }
    // 如果非空且不为x就轮到下一个，最后返回的k要么为空，要么为x的位置
    // 插入时，如果为空，那么x刚好放这里；如果为x，那么保证没有重复元素
    // 查找时，如果为空，那么x不存在；如果为x，那么x存在
    return k;
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int n;
    memset(a, 0x3f, sizeof(a));
    cin >> n;
    while (n--)
    {
        char opt;
        int x;
        cin >> opt >> x;
        if (opt == 'I')
            a[find(x)] = x;
        else 
	        cout << (a[find(x)] == x ? "Yes" : "No") << '\n';
    }
}

字符串哈希

给定一个长度为  的字符串，再给定  个询问，每个询问包含四个整数 ，请你判断  和  这两个区间所包含的字符串子串是否完全相同。

字符串中只包含大小写英文字母和数字。

输入格式

第一行包含整数  和 ，表示字符串长度和询问次数。

第二行包含一个长度为  的字符串，字符串中只包含大小写英文字母和数字。

接下来  行，每行包含四个整数 ，表示一次询问所涉及的两个区间。

注意，字符串的位置从  开始编号。

输出格式

对于每个询问输出一个结果，如果两个字符串子串完全相同则输出 Yes，否则输出 No。

每个结果占一行。

数据范围

输入样例：

1
2
3
4
5
8 3
aabbaabb
1 3 5 7
1 3 6 8
1 2 1 2

输出样例：

1
2
3
Yes
No
Yes

思路分析

将每一个字符对应的ASCII码转换成P进制数，就可以得到这个字符串的哈希值。根据规律，P=131或者13331时字符串的哈希值几乎不可能重复，因此P可以取131；同时为了防止值太大，一般选取最后模上一个值Q，而当Q取2^64时也不容易重复。所以我们可以将得到的字符串哈希放在unsigned long long，超出部分爆掉相当于自动取模。

得到了字符串的前缀和哈希数组，想要得到中间某个字串 的哈希值，只需要用r的哈希值减去 l-1的哈希值。例如：有 的哈希值和 的哈希值，想得到 的哈希值，只需要将 乘 ，得到 的哈希值，相减就是DE哈希值。

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
#include <iostream>
using namespace std;
typedef unsigned long long ull;
const int N = 1e5 + 9;
const int P = 131;

ull a[N], p[N];
int n, m;

ull SubHash(int l, int r)
{
    return a[r] - a[l - 1] * p[r - l + 1];
}

int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    string s;
    cin >> n >> m >> s;
    p[0] = 1;
    for (int i = 1; i <= n; i++)
    {
        a[i] = P * a[i - 1] + (ull)s[i - 1];
        // 将P的幂次提前计算出来，以便后面使用
        p[i] = P * p[i - 1];
    }
    while (m --)
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        cout << (SubHash(l1, r1) == SubHash(l2, r2) ? "Yes" : "No") << '\n';
    }
}