自学内容网 自学内容网
自学内容网 > 正文

第二讲 数据结构

🕗 发布于 2024-07-13 21:36 数据结构  算法  图论  

#数组模拟链表

#include <iostream>
using namespace std;
const int N = 100010;
int head ,e[N], ne[N],idx;
//ne[i]表示节点i的next指针是多少
//e[i]表示节点i 的值
//head 表示头结点的下标
//idx 存储当前已经用了哪个点
void init()
{
head = -1;//头结点指向下标为0的地方，单独设置索引
// 表示链表为空
idx = 0;//初始化表示还没有用节点
// 从起始位置开始使用节点
}
void add_to_head(int x){//插入节点
e[idx] = x;//赋值

ne[idx] = head;//新节点next指向为head的指向
// 将新节点的指针指向当前头节点位置
head = idx;//head指向新节点，节点是一个数字
// 更新头节点为新节点
idx++;//自动往前，表示添加进一个数
// 更新索引位置，准备下一个新节点的添加
}
//将x插入到k节点之后 
void add(int k,int x)
{
e[idx] = x;
ne[idx] = ne[k];// 新节点的下一个节点设为第 k 个节点的下一个节点
ne[k] = idx;// 第 k 个节点的下一个节点更新为新节点
idx++;

}
void remove(int k){
ne[k] = ne[ne[k]];
}

int main ()
{
int m;
cin >> m;
init();
while(m--){
int k,x;
char op;
cin >> op;
if(op == 'H')
{
cin >> x;
add_to_head(x);
}
else if (op == 'D')
{
cin >> k;
if(!k) head = ne[head];
remove(k-1);
}
else {
cin >> k >>x;
add(k-1,x);
}
}
for(int i = head ;i!=-1;i = ne[i]) 
cout << e[i] << ' ';
cout << endl;
return 0;
}

![[Pasted image 20240708114943.png]]

  • idx:

    • 单纯表示链表中节点的位置或索引。
    • 例如 e[idx] = x 表示在位置 idx 处存储值 x。

  • ne[idx]:

    • 表示索引 idx 处节点的“指针”，即指向下一个节点的索引。
    • 例如 ne[idx]，存储的是下一个节点的位置索引。
      #双链表
#include <iostream>
using namespace std;
const int N = 100010;
int m;
int e[N], l[N],r[N],idx;
void init(){
r[0] = 1,l[1] = 0;
idx = 2;
}
void add(int k,int x)
{
 e[idx] = x;
 r[idx] = r[k];
 l[idx] = k;
 l[r[k]] = idx;
 r[k] = idx;
 }
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k] ;

}
int main (){
 
}

#模拟栈

#include <iostream>
using namespace std;
const int N = 100010;
int stk[N],tt;//栈
stk[++tt] = x;//入栈 
tt--;//弹出
if(tt>0) not empty;//判断是否为空
else empty;
stk[tt];//栈顶


//队尾插入元素，在队头弹出元素
int q[N],hh,tt = -1;
//插入
q[++tt] = x;
//弹出
h++;
//判断队列是否为空
if(hh<=tt)not empty;
else empty;

//取出队头元素
q[hh];
q[tt];//队尾


#include <iostream>
#include <vector>

// 定义栈
template <typename T>
class Stack {
private:
    std::vector<T> items;

public:
    // 入栈
    void push(const T& element) {
        items.push_back(element);
    }

    // 出栈
    T pop() {
        if (isEmpty()) {
            throw std::runtime_error("Stack is empty");
        }
        return items.back(); // 返回并移除栈顶元素
    }

    // 查看栈顶元素
    T top() const {
        if (isEmpty()) {
            throw std::runtime_error("Stack is empty");
        }
        return items.back();
    }

    // 判断栈是否为空
    bool isEmpty() const {
        return items.empty();
    }
};

// 定义队列
template <typename T>
class Queue {
private:
    std::vector<T> items;

public:
    // 入队
    void enqueue(const T& element) {
        items.push_back(element);
    }

    // 出队
    T dequeue() {
        if (isEmpty()) {
            throw std::runtime_error("Queue is empty");
        }
        T front = items.front(); // 保存并移除队头元素
        items.erase(items.begin());
        return front;
    }

    // 查看队头元素
    T front() const {
        if (isEmpty()) {
            throw std::runtime_error("Queue is empty");
        }
        return items.front();
    }

    // 判断队列是否为空
    bool isEmpty() const {
        return items.empty();
    }
};

int main() {
    Stack<int> stack;
    stack.push(1);
    std::cout << "Stack top: " << stack.top() << std::endl;

    Queue<int> queue;
    queue.enqueue(1);
    std::cout << "Queue front: " << queue.front() << std::endl;

    return 0;
}

![[Pasted image 20240708160006.png]]

#include <iostream>
using namespace std;

const int N = 100010;//定义一个常量，用于设置栈的最大容量
int n ;//用于存储输入的整数的个数
int stk[N],tt;//stk是一个数组，用于模拟栈，tt是栈顶指针

int main(){
scanf("%d",&n);
for(int i = 0;i<n;i++)
{
int x;
scanf("%d",&x);
while(tt && stk[tt] >= x)tt--;
//在栈非空且栈顶元素大于等于当前数的情况下，不断弹出栈顶元素
if(tt)
 printf("%d",stk[tt]);
 //如果栈非空，输出栈顶元素（比当前数字小的最近的那个数)
else printf("-1");
//如果栈为空，输出-1（没有比当前数字小的数)

stk[++tt] = x;
//将当前数字压入栈顶
}
return 0;
}
滑动窗口最小值问题

给定一个长度为 n 的整数数组 a 和一个整数 k，要求你计算每个长度为 k 的滑动窗口中的最小值。当窗口一次向右滑动一个位置时，你需要输出窗口中的最小值。你的任务是设计一个时间复杂度为 O(n) 的算法来解决这个问题。

输入格式：

  1. 第一行为两个整数 n 和 k，分别表示数组的长度和窗口的大小。
  2. 第二行为 n 个整数，表示数组 a 的元素。

输出格式：

输出一行，共 n - k + 1 个整数，分别表示每个滑动窗口中的最小值，用空格分隔。

示例：

输入：

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

输出：

-1 -3 -3 -3 3 3

说明：

  • 对于输入数组 [1, 3, -1, -3, 5, 3, 6, 7] 和 k = 3，滑动窗口的最小值依次为：-1, -3, -3, -3, 3, 3。

测试用例

测试用例 1

输入：

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

输出：

-1 -3 -3 -3 3 3
测试用例 2

输入：

5 2
4 2 12 5 8

输出：

2 2 5 5
测试用例 3

输入：

5 5
10 9 8 7 6

输出：

6
测试用例 4

输入：

6 1
2 1 4 5 3 6

输出：

2 1 4 5 3 6
测试用例 5

输入：

10 4
4 3 5 4 3 3 6 7 3 3

输出：

3 3 3 3 3 3 3 3 3

#滑动窗口

#include <iostream>
using namespace std;

const int N = 1000010;
int n;
int a[N],q[N];// 用于存储元素索引的双端队列
int main()
{
//读入数组长度和窗口大小
scanf("%d%d",&n，&k);
for(int i =0;i<n;i++){
scanf("%d",&a[i]);
}
//hh表示队列的头部（最小值的位置）。
//tt是队列尾部。
int hh = 0,tt = -1;
for(int i = 0;i<n;i++)
{
//检查队列头部是否在窗口之外
//如果 `q[hh]` 这个位置的元素无法成为当前窗口的一部分，则将它从队列头部移除。
if(hh <= tt && i-k+1>q[hh]) hh++;
//保证队列单调递增，确保最小值在队列头部
//从队尾开始，将所有大于或等于当前元素 `a[i]` 的元素索引移除。
//这样做是为了确保队列里保留的都是可能成为当前窗口最小值的索引。
while(hh <= tt && a[q[tt]] >= a[i]) tt--;
//插入当前元素索引到队列
q[++tt] = i;
//当前窗口形成(即窗口长度达到k)时，输出队列头部最小值

if(i >= k-1) printf("%d",a[q[hh]]);

}
puts("");
return 0;
}

  1. 读取输入的修改：

    • 增加了读取窗口大小 k 的语句：scanf("%d%d", &n, &k);。
    • 这个窗口大小 k 在原代码中没有定义。

  2. 滑动窗口逻辑的维护：

    • 通过条件 if(hh <= tt && i - k + 1 > q[hh]) hh++; 检查队列头部是否在当前窗口之外，如果在窗口之外，则将头部元素移除。（处理多个符合逻辑的情况，控制窗口往右继续走）
    • 通过 while(hh <= tt && a[q[tt]] >= a[i]) tt--; 维护一个单调递增的队列，确保最小值在队列头部。
    • 使用 q[++tt] = i; 插入当前元素的索引到队列。

  3. 输出窗口最小值：

    • 当索引 i >= k-1 时，窗口已经形成，每次输出队列头部的最小值：if(i >= k - 1) printf("%d ", a[q[hh]]);。
    • 输出之间增加了一个空格以便结果更清晰。

  4. 换行输出：

    • 加入 puts(""); 以确保输出结束时换行。

假如数组 a = [1, 3, -1, -3, 5, 3, 6, 7]，窗口大小 k = 3，我们模拟一下代码执行的步骤：

  1. i = 0 (a[0] = 1)：

    • 队列更新：hh = 0, tt = 0, q = [0]。

  2. i = 1 (a[1] = 3)：

    • 队列更新：hh = 0, tt = 1, q = [0, 1]。

  3. i = 2 (a[2] = -1)：

    • 队列更新前，q = [0, 1]；由于 a[1] >= a[2] 和 a[0] >= a[2]，所以移除这些索引。
    • 队列更新：hh = 0, tt = 0, q = [2]。
    • 当前窗口形成，输出 a[q[hh]] 即 -1。

  4. i = 3 (a[3] = -3)：

    • 队列更新前，q = [2]；由于 a[2] >= a[3]，移除索引 2。
    • 队列更新：hh = 0, tt = 0, q = [3]。
    • 当前窗口形成，输出 a[q[hh]] 即 -3。

#KMP

#include <iostream>
using namespace std;
const int N = 10010, M = 100010;
int n,m;
char p[N],s[M];
int ne[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;
}
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时值为-1
#include <iostream>
using namespace std;
const int N = 10010, M = 100010;
int n, m;
char p[N], s[M];
int ne[N];
int main() {
cin >> n >> p >> m >> s;
ne[0] = -1;
for (int i = 1, j = -1; i <= n; i++)
{
while (j != -1 && p[i] != p[j + 1])
j = ne[j];
if (p[i] == p[j + 1])
j++;
ne[i] = j;
}
for (int i = 0, j = -1; i <= m; i++)
{
while (j != -1 && 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;
}

这段代码是经典的KMP（Knuth - Morris - Pratt）字符串匹配算法的实现，用于在一个长字符串 s 中查找一个模式串 p 出现的位置。

整体思想

KMP算法通过预处理模式串 p 来构造一个“部分匹配”表（即 ne 数组），从而在匹配过程中避免重复的字符比较，实现线性时间复杂度的匹配。

代码详解

变量和输入

const int N = 10010, M = 100010;
int n, m;
char p[N], s[M];
int ne[N];

cin >> n >> p + 1 >> m >> s + 1;

N 和 M 是两个常量，分别定义模式串 p 和文本串 s 的最大长度。

n 是模式串 p 的长度，m 是文本串 s 的长度。

p 和 s 分别是模式串和文本串，数组下标从1开始（因此输入和处理下标都从1开始）。

ne 是“部分匹配”表（next数组），用于存储前缀信息。

构造next数组

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;
}

i 是当前处理的模式串中的字符的索引，从2开始，因为 ne[1] 是默认初始化为0的。

j 是当前最长的前缀长度。

while (j && p[i] != p[j + 1]) j = ne[j]; ：如果当前字符 p[i] 和 p[j + 1] 不匹配，尝试找一个更短的前缀使其匹配，使用 ne[j] 来减少前缀长度。

if (p[i] == p[j + 1]) j++; ：如果字符匹配，增加最长前缀长度 j。

ne[i] = j; ：更新 ne 数组，ne[i] 表示到位置 i 为止的最长相同前后缀的长度。

KMP匹配过程

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(“%dn”, i - n + 1); // 这里保持风格一致应使用换行符
j = ne[j];
}
}

i 是文本串 s 的当前处理字符的索引。

j 是模式串 p 中当前匹配到的最长前缀长度。

while (j && s[i] != p[j + 1]) j = ne[j]; ：如果当前字符 s[i] 和 p[j + 1] 不匹配，尝试找一个更短的前缀使其匹配，使用 ne[j] 来减少前缀长度。

if (s[i] == p[j + 1]) j++; ：如果字符匹配，增加匹配长度 j。

if (j == n)：如果匹配长度 j 等于模式串长度 n，说明找到了一个完整的匹配。

printf(“%dn”, i - n + 1); ：输出模式串在文本串中出现的位置（这里要注意输出规则，用"n"代替原来的输出逻辑）。

j = ne[j]; ：找到一个匹配后，将 j 更新为 ne[j] 以继续查找下一个可能的匹配。

运行示例

假如输入是：

5 abcde
13 abcabcdefgabc

模式串 p 为 “abcde”，长度 n = 5。

文本串 s 为 “abcabcdefgabc”，长度 m = 13。
这段代码会在文本串 s 中查找模式串 p 的位置。

构造next数组：

最终形成的 ne 数组可能是[0, 0, 0, 0, 0]，因为模式串中没有任何重复的前后缀。

进行KMP匹配：

在 Text 中从第 1 到第 13 个字符进行匹配。

匹配到第 6 场时，发现等于模式串长度。

最终输出匹配的起始位置。

#trie树

高效的存储和查找字符串集合的数据结构
![[Pasted image 20240709110708.png]]

#include <iostream> 
using namespace std;
const int N = 100010;
int son[N][26],cnt[N],idx; 
    //- `son[N][26]` 是Trie的结构，
    //`son[i][j]` 表示节点 `i` 的第 `j` 个孩子节点，`j` 从0到25对应字母 'a' 到 'z'。
   //- `cnt[N]` 用于存储以节点 `i` 结尾的字符串的数量。
   //- `idx` 是Trie中当前节点的总数。
   //- `str[N]` 用于存储临时字符串。
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[0] == 'l') insert(str);
   else printf("%d\n",query(str));
    }
return 0;
}

Trie的每个节点不仅仅存储单一的字符，而是通过一个二维数组 son[N][26] 来存储子节点，从而形成一个树形结构。根节点为空，通过子节点逐渐构建整个树。

Trie的构建过程

初始状态：

idx 初始化为0，表示根节点。
son[0][…] 也初始化为0，表示根节点的26个子节点都为空。

插入单词

通过插入字符串逐字符构建Trie。以下是细节步骤：

插入 “apple”

从根节点出发，p 初始化为0。

处理字符 ‘a’，u = ‘a’ - ‘a’ = 0，son[0][0] 为空，创建新节点1，son[0][0] = 1，然后 p 更新为1。

处理字符 ‘p’，u = ‘p’ - ‘a’ = 15，son[1][15] 为空，创建新节点2，son[1][15] = 2，然后 p 更新为2。

处理字符 ‘p’，u = 15，son[2][15] 为空，创建新节点3，son[2][15] = 3，然后 p 更新为3。

处理字符 ‘l’，u = ‘l’ - ‘a’ = 11，son[3][11] 为空，创建新节点4，son[3][11] = 4，然后 p 更新为4。

处理字符 ‘e’，u = ‘e’ - ‘a’ = 4，son[4][4] 为空，创建新节点5，son[4][4] = 5，然后 p 更新为5。

到达字符串结尾，cnt[5]++，表示以该节点结尾的字符串数量加1。

插入 “banana”

从根节点出发，p 初始化为0。

处理字符 ‘b’，u = ‘b’ - ‘a’ = 1，son[0][1] 为空，创建新节点6，son[0][1] = 6，然后 p 更新为6。

处理字符 ‘a’，u = 0，son[6][0] 为空，创建新节点7，son[6][0] = 7，然后 p 更新为7。

处理字符 ‘n’，u = ‘n’ - ‘a’ = 13，son[7][13] 为空，创建新节点8，son[7][13] = 8，然后 p 更新为8。

处理字符 ‘a’，u = 0，son[8][0] 为空，创建新节点9，son[8][0] = 9，然后 p 更新为9。

处理字符 ‘n’，u = 13，son[9][13] 为空，创建新节点10，son[9][13] = 10，然后 p 更新为10。

处理字符 ‘a’，u = 0，son[10][0] 为空，创建新节点11，son[10][0] = 11，然后 p 更新为11。

到达字符串结尾，cnt[11]++，表示以该节点结尾的字符串数量加1。

结构图示

假设插入 “apple” 和 “banana” 后 Trie 的结构大致如下：

Root
|
±-(‘a’)–(Node 1)
| |
| ±-(‘p’)–(Node 2)
| |
| ±-(‘p’)–(Node 3)
| |
| ±-(‘l’)–(Node 4)
| |
| ±-(‘e’)–(Node 5, cnt[5] = 1)
|
±-(‘b’)–(Node 6)
|
±-(‘a’)–(Node 7)
|
±-(‘n’)–(Node 8)
|
±-(‘a’)–(Node 9)
|
±-(‘n’)–(Node 10)
|
±-(‘a’)–(Node 11, cnt[11] = 1)

根节点的子节点包括 ‘a’ 和 ‘b’，分别指向 Node 1 和 Node 6。

路径 “a -> p -> p -> l -> e” 对应 “apple”，终止于 Node 5。

路径 “b -> a -> n -> a -> n -> a” 对应 “banana”，终止于 Node 11。

查询单词

查询操作类似插入操作，通过逐字符沿Trie树移动：

查询 “apple”:

从根节点出发，依次沿字符 ‘a’ -> ‘p’ -> ‘p’ -> ‘l’ -> ‘e’ 移动到节点 Node 5，返回 cnt[5]，为1。

查询 “banana”:

从根节点出发，依次沿字符 ‘b’ -> ‘a’ -> ‘n’ -> ‘a’ -> ‘n’ -> ‘a’ 移动到节点 Node 11，返回 cnt[11]，为1。

#并查集
1.将两个集合合并
2.询问两个元素是否在一个集合当中
![[Pasted image 20240709115151.png]]

并查集（Disjoint Set Union，简称 DSU 或 Union-Find）是一种非常高效的数据结构，用于处理动态连通性问题。它特别擅长解决一些关于集合合并和查找的问题，比如判断两个元素是否属于同一个集合、将两个集合合并等。以下是并查集的一些优点和常见应用：

优点

  1. 快速合并和查找操作：

    • 并查集可以在近乎常数时间内完成合并和查找操作。通过路径压缩（Path Compression）和按秩合并（Union by Rank/Size），可以将时间复杂度优化到近乎 𝑂(1)O(1)，也就是极为接近常数时间。

  2. 实现简单：

    • 并查集的实现相对简单，只需要一个数组来记录每个元素的父节点，以及在用到路径压缩和按秩合并时，再维护一个额外的数组来记录每个树的秩或大小。

  3. 灵活：

    • 并查集可以处理动态变化的数据，适用于不断新增和合并的集合操作，不需要预先知道集合的具体结构。

常见应用

  1. 连通性问题：

    • 在无向图中判定连通分量，判断两个顶点是否在同一个连通分量中。
    • 常用于网络中的网络连通性检测。

  2. 最小生成树（Kruskal’s Algorithm）：

    • 用于Kruskal算法中，对边进行排序后，逐步添加边到生成树中，确保加入的边不会形成环。

  3. 等价性判定：

    • 在字符串、图像处理等领域，判断多个元素是否在同一个等价类中。

  4. 动态连通性：

    • 在动态变化的数据集上，迅速判断两元素是否连通或合并两个集合。

详细解释

路径压缩（Path Compression）

路径压缩用于优化 find 操作，使得每次查找根节点时，将经过的所有节点直接连到根节点上，从而使得下次查找更快。路径压缩的具体做法是，在 find 操作中，将当前节点的父节点直接设置为根节点：

int find(int x)
{
if(p[x] != x){
p[x] = find(p[x]);//递归查找根节点，并进行路径压缩
}
return p[x];
}
按秩合并（Union by Rank/Size）

按秩合并是一种合并操作的优化，目标是将较小（或较矮）的树合并到较大（或较高）的树上，以减少树的高度，从而提高查找效率。具体做法是，每次合并时，比较两棵树的高度（秩）或大小，将较小（或较矮）的树根指向较大（或较高）的树根：

void union（int x ,int y )
{
int rootX = find(x);
int rootY = find(y);
if(rootX != rootY){
if(rank[rootX] > rank[rootY])
{
p[rootY] = rootX;
}
else if (rank[rootX] < rank[rootY])
 { 
 p[rootX] = rootY; 
 } else {
  p[rootY] = rootX; rank[rootX]++; 
  }
}
}
  1. 当 rank[rootX] == rank[rootY] 时，它们的秩相同。
  2. 此时，如果我们任意选择一个节点作为新的根节点，合并后树的高度将会增加1，因为两颗子树的高度相等并接近。
操作解释：
  • p[rootY] = rootX;：
    • 将 rootY 的父节点设为 rootX。这样，rootY 以及以 rootY 为根的子树节点都将属于以 rootX 为根的集合。
  • rank[rootX]++;：
    • 将 rootX 的秩增1，因为现在 rootX 成为了较高树的根节点（包含了之前与它秩相同的另一棵子树），高度增加了1。

合并的具体例子

假设有两个节点 x 和 y，分别对应的树的结构及秩如下：

x -> rootX (rank[rootX] = 2)
y -> rootY (rank[rootY] = 2)

树的图示：

   rootX           rootY
    2     - rank    2
  /             /   
...   ...      ...   ...

当 rank[rootX] == rank[rootY] 时，

  • 我们将 rootY 挂在 rootX 上
  • 然后增加 rootX 的 rank

合并后树的图示：

        rootX (rank = 3)
        /     
     ...      rootY
              /   
           ...   ...

此时，新的集合的根节点是 rootX，并且它的秩增加了一层，变成 rank[rootX] = 3。

通过这样的合并，尽可能使得并查集的树保持平衡，从而保障了树的高度不至于增大太快，提升了后续查找（find）操作的效率。

总结

并查集是一种简单而高效的数据结构，特别适用于一些需要频繁合并和查找操作的场景。通过路径压缩和按秩合并的优化，可以在近乎常数时间内处理动态连通性问题。不论是在图论问题、网络连通性检测还是其他需要判定等价关系的领域，并查集都显示出其强大的优势。

![[Pasted image 20240709120242.png]]

#include <iostream>
 using namespace std;
 const int N = 100010;
 int n,m;
 int p[N];//数组 `p` 是并查集的父指针数组，`p[i]` 表示元素 `i` 的直接父节点。
 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);
 //将 `a` 所在集合的根节点指向 `b` 所在集合的根节点，实现合并。
 else {
 if(find(a) == find(b)) puts("Yes");
 else puts("No");
 
 }
 
 }
 return 0;
 }

将 M 操作写成 find(a) = find(b) 是不正确的，因为 find(a) 和 find(b) 返回的是两个集合的根节点的值，而并不是对这些值本身进行修改。正确地进行合并操作需要通过父指针数组 p 来修改元素所属集合的根节点。下面详细解释其中的原因。

正确做法：

p[find(a)] = find(b);

  • find(a) 返回 a 所在集合的根节点。
  • find(b) 返回 b 所在集合的根节点。
  • 通过 p[find(a)] = find(b)，我们将 a 所在集合的根节点指向 b 所在集合的根节点，从而实现了两个集合的合并。

错误写法：

find(a) = find(b);

  • find(a) 和 find(b) 返回的是两个整数值，分别代表 a 和 b 所属集合的根节点。
  • find(a) = find(b) 并不能改变 p 数组的内容，因为 find 函数返回的是根节点的值而不是引用，无法直接修改根节点的父指针。
  • 换句话说，这样的赋值语句只是在尝试将一个值赋值给另一个值，但实际上并没有改变并查集的数据结构，无法实现合并两集合的效果。

举例说明

假设有两个元素 a 和 b：

  • a 的根节点是 rootA。
  • b 的根节点是 rootB。

正确的操作是：

p[rootA] = rootB;

这相当于将 a 所在集合的根节点 rootA 指向 b 所在集合的根节点 rootB， 从而合并两个集合。

错误的操作：

rootA = rootB;

这只是将 rootA 和 rootB 这两个值交换（在C++中运行时甚至会报错，因为 find(x) 返回的是右值（rvalue）），但并没有涉及父指针数组 p，所以并不会影响并查集的结构。

结论

在并查集进行合并操作时，必须通过 p 数组修改根节点的指向。如下的操作才能正确实现集合的合并：

p[find(a)] = find(b);

这是因为我们需要通过修改 p 数组来更新集合的父子关系，才能正确维护并查集的结构。简单的 find(a) = find(b) 是不会起到这一效果的，因为找出的根节点值无法直接改变集合的

find(x)：用于查找元素 x 所在集合的根节点。

  • 如果 x 的父节点不是它自己（即 p[x] != x），则递归查找其父节点的根，并进行路径压缩。
  • 路径压缩：在递归返回时，将 x 的父节点直接设置为根节点。这减少了未来操作的时间复杂度。

路径压缩的核心思想是，在执行 find 操作时，不仅仅是找到一个元素的根节点，而是将这个元素沿途经过的所有节点都直接指向根节点。通过这种方式，可以显著平摊并减少树的高度，从而极大地加快后续的 find 和 union 操作。这种优化在实际使用过程中可以显著提升效率。

具体地，路径压缩的过程如下：

对于每个节点，如果它不是根节点（即它的父节点不是它自己），我们递归地找到它的根节点。

在找到根节点之后，将沿途经过的所有节点的父节点直接设为这个根节点。

通过这种方式，下一次对同一个节点的 find 操作会更加高效，因为路径被压缩了。下面我们通过代码段和示意图详细说明路径压缩的效果。

路径压缩代码示例

以下是路径压缩在 find 操作中的实现：

int find(int x) {
if (p[x] != x) {
p[x] = find(p[x]); // 递归找到根节点，并将当前节点的父节点直接设为根节点
}
return p[x];
}

路径压缩前后的树形变化
初始状态（没有路径压缩）
假设初始集合关系如下：

p : 0 1 2 3 4 5 6 7
| | | | | | |
0 1 2 3 4 5 6 7

操作： union(2, 3)， union(3, 4)， union(4, 5)

结果：
p : 0 1 2 3 4 5 6 7
| | |
2–3–4–5

树：

2 → 3 → 4 → 5

此时，如果我们执行 find(2)，路径将不会被压缩，之后的 find(3)，find(4)，find(5)还是需要多次递归。

路径压缩效果

执行 find(2) 后，通过路径压缩，所有经过的节点将直接指向根节点：

find(2)
->find(p[2]) = find(3)
->find(p[3]) = find(4)
->find(p[4]) = find(5)

通过路径压缩，节点 2、3、4 都直接指向根节点 5:

p: 0 1 2 3 4 5 6 7
| | |
2->3->4->5
/ | |
/ / /
| / /
5

简单树形：

2 → 5
3 → 5
4 → 5
5

2, 3, 4 All point to 5 directly after invoking find(2).

后续查找的效率提升

特别地，再执行一次 find(2), find(3), find(4), find(5)，这些操作都将直接返回根节点 5，时间复杂度大幅降低。

总结

路径压缩有效地将所有节点直接连到根节点，使得树的高度变为1。尽管路径压缩不会一下子改变树的高度，但随着越来越多的查找操作执行，树高度会逐渐降低，进而提升操作效率。通过这种方式，并查集能够在均摊时间复杂度近乎O(1) 的情况下完成查找和合并操作，表现出极高

![[Pasted image 20240709120427.png]]

#include <iostream>
using namespace std;
const int N = 100010;
int n,m;
int p[N],size[N];
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;
size[i] = 1;

}
while(m--)
{
char op[5];
int a,b;
scanf("%s",op);
if(op[0] == 'C')
{
scanf("%d%d",&a,&b);
if(find(a) = find(b)) continue;
size[find(b)] += size[find(a)];
p[find(a)] = find(b);
}
else if(op[1] == '1')
{
scanf("%d%d",&a,&b);
if(find(a) == find(b)) puts("Yes");
else put("No");
}
else {
scanf("%d",&a);
printf("%d\n",size[find(a)]);
}
}
return 0;
}

![[Pasted image 20240709155724.png]]

#堆
![[Pasted image 20240709160134.png]]
![[Pasted image 20240709160838.png]]
![[Pasted image 20240709161048.png]]

堆排序
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m;
int h[N],size;

void down(int u)
{
int t = u;// 初始化t为当前节点u
if(u*2 <= size && h[u*2] < h[t]) t = u*2;// 如果左子节点更小，更新t
if(u*2+1 <=size && h[u*2+1] < h[t])t = u*2+1;// 如果右子节点更小，更新t
 // 如果t被更新，意味着当前节点h[u]不是最小的，需要调整
if(u != t)
{
swap (h[u],h[t]);
down(t);// 递归对子节点进行调整
}
}
void up (int u)
{
while(u/2 && h[u/2] > h[u])// 当父节点存在且父节点值大于当前节点值
{
swap (h[u/2],h[u]);// 交换当前节点与父节点
u/= 2;// 移动到父节点进行下一轮比较 }
}
}
int main ()
{

scanf ("%d%d",&n,&m);
for(int i = 1;i<=n;i++)// 读入初始堆元素
scanf("%d",&h[i]);
size = n;// 初始堆大小等于n
for(int i= n/2;i;i--)// 从最后一个非叶子节点开始向前进行向下调整，构建最小堆
down(i);
while(m--)// 删除m个堆顶元素
{
printf("%d",h[1]);// 打印堆顶元素（最小值）
h[1] = h[size];// 将最后一个元素移动到堆顶，并减少堆大小
size--;
down(1);// 从堆顶开始向下调整

}
return 0;
}

for(int i = n / 2; i; i--) down(i); 这一行代码是堆构建的核心。为什么从 n / 2 开始？这是因为：

  1. 堆的叶子节点不需要向下调整，它们天然满足堆的性质。
  2. 对于一个完全二叉树，最后一个非叶子节点的索引是 n / 2。

从 n / 2 开始向前调整，可以确保所有节点都被适当地调整，最终形成一个最小堆。
![[Pasted image 20240709163817.png]]

#include <iostream>
#include <algorithm>
#include <string.h>

using namespace std;
const int N = 100010;
int n,m;
int h[N],ph[N],hp[N],size;// h是堆数组，ph和hp互为反函数
//代码中引入了 `ph`（position heap）和 `hp`（heap position）两个数组，用于互为反函数的索引管理。
void heap_swap(int a,int b)
{
swap(ph[hp[a]],ph[hp[b]]);// 更新ph数组，使其同步hp的变化
swap(hp[a],hp[b]);// 交换hp中的位置
swap(h[a],h[b]);// 交换堆数组 h 中的值
}
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/2] > h[u])
{
heap_swap(u/2,u);
u/= 2;
}
}
int main ()
{

int n,m =0;
scanf("%d",&n);
while(n--)
{
char op[10]; // 操作
int k, x;
scanf("%s", op);
if (!strcmp(op, "I")) { // 插入操作
    scanf("%d", &x);
    size++;  // 增加堆大小
    m++;     // 增加元素序号
    ph[m] = size; // ph记录m元素在size位置
    hp[size] = m; // hp记录size位置是m元素
    h[size] = x;  // 在堆数组中插入元素 x
    up(size);     // 向上调整以维护最小堆性质
}
else if (!strcmp(op, "PM")) { // 输出最小值
    printf("%dn", h[1]); // 堆顶即为最小值
}
else if (!strcmp(op, "DM")) { // 删除最小值
    heap_swap(1, size); // 交换堆顶和最后一个元素
    size--;             // 减小堆大小
    down(1);            // 从堆顶向下调整
}
else if (!strcmp(op, "D")) { // 删除任意位置元素
    scanf("%d", &k);
    k = ph[k];           // 找到k位置对应的堆位置
    heap_swap(k, size);  // 交换k位置与堆的最后一个元素
    size--;              // 减小堆的大小
    down(k), up(k);      // 双向调整维护堆性质
}
else { // 修改任意位置元素
    scanf("%d%d", &k, &x);
    k = ph[k];           // 找到k位置对应的堆位置
    h[k] = x;            // 修改值
    down(k), up(k);      // 双向调整维护堆性质
}

}

}
return 0;
}

“position in heap” 和 “heap position”

  • ph（position heap）：记录的是某一个元素在 hp 中的位置。
  • hp（heap position）：记录的是堆中某一个位置所对应的输入顺序。

我的理解是ph代表的是一个位置，而hp是这个位置上的数对应的插入顺序编号

回顾 ph 和 hp 的作用

  • ph[k]: 第 k 个插入操作对应的值在堆数组 h 中的位置。
  • hp[u]: 堆数组 h 的位置 u 对应的插入操作编号。

hp 的具体作用解析

假设我们正在维护一个最小堆，并且需要支持随时定位任意插入的元素（例如根据插入操作的编号快速找到该元素在堆中的位置)，并且执行修改或删除操作。理解 hp 作用的关键在于考虑位置交换问题。

具体案例

假设我们进行以下操作：

  1. 插入 10，编号 1。
  2. 插入 20，编号 2。
  3. 插入 15，编号 3。

此时，堆 h 的结构看起来如下（1 表示堆顶）：

h  = [无, 10, 20, 15]
ph = [无, 1, 2, 3]  // 编号1的元素在h[1]，编号2的元素在h[2]，编号3的元素在h[3]。
hp = [无, 1, 2, 3]  // h[1]是编号1的元素，h[2]是编号2的元素，h[3]是编号3的元素。

删除或修改元素的操作

现在，假设我们要删除编号为 2 的元素（即 20). 可以通过 ph[2] 知道 20 目前在堆中的位置是 2。我们将 h[2] 位置上的值删除，并将堆的最后一个元素 15 移动到 h[2]，并重新调整堆，同时更新 ph 和 hp。

删除操作可能如下：

void delete_by_position(int pos) { 
swap(h[pos], h[size]);   
// 将最后一个元素移到删除位置 
swap(ph[hp[pos]], ph[hp[size]]); 
// 更新ph数组    
swap(hp[pos], hp[size]); 
// 更新hp数组    
size--;                   // 移除最后一个元素 
down(pos);                // 堆调整 
}  
void down(int pos) {   
// 堆调整过程 
}

这样删除位置的元素时，我们必须维护 ph 和 hp 数组的一致性。即使在堆调整（down/up）的过程中，我们也需要频繁交换堆元素，hp 数组帮助我们快速找到交换后的新位置。

插入操作中的应用

假设我们插入 5，插入编号 4：

  1. 插入 5 后堆 h 变为 [无, 10, 15, 5]。
  2. 交换位置，调整堆，最终堆变为 [无, 5, 15, 10]。

在堆调整过程中，ph 和 hp 必须相应更新。调整步骤如下：

  • 插入 h[(size+1)] = 5
  • 更新 ph[4] = size+1 即 ph[4] = 4
  • 然后在堆调整过程中：
    • swap(h[1], h[4])，swap(hp[1], hp[4])，更新 hp 和 ph 数组。

调整后的堆结构：

h  = [无, 5, 15, 10]
ph = [无, 1, 3, 2, 1] // 更新后的位置
hp = [无, 4, 2, 3]   // 更新后的插入操作位置

继续堆的维护

无论堆的 h 中进行上浮或下沉操作，hp 和 ph 允许在常数时间内更新堆元素的位置高度，从而减少搜索复杂度。

总结

  • ph 用来通过插入编号查找到堆中的位置。
  • hp 则用来通过堆中的位置快速找到对应的插入编号。

两者结合使得堆的插入、删除和修改操作都能在常数时间内查询和更新。 hp 对数组翻译可以使任意操作能在O(1)时间复杂度下对位置关系更新，并且维护堆排序的有效性。

这两个数组的作用是互为反函数，以便进行高效的元素位置交换和调整。
我们通过在代码中添加详细注释，再次解释这个堆的操作。

#哈希表
![[Pasted image 20240709170550.png]]

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100003;//最好用质数
//`N` 的值是一个大质数，使用质数作为哈希表的大小可以显著减少哈希冲突。因为质数能更均匀地把数据分布到各个槽中，提高哈希表的查找和插入效率。
int h[N],e[N],ne[N],idx;
void insert(int x)
{
int k = (x%N +N)%N;
/*`x % N`: 计算 `x` 对 `N` 取模的结果。
`+ N` 再次加上 `N` 用于处理 `x` 可能是负数的情况，
例如 `-1 % N` 可能会产生负数结果。
再次取模 `% N` 是为了确保结果始终在 `[0, N-1]` 范围内。

这个步骤的目的是将哈希值规范化为一个非负数索引，用于访问哈希表中的数组槽位。*/
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 ;
}

int main()
{
int n; 
scanf("%d",&n);
memset(h,-1,sizeof h);
while(n--)
{
char op[2];
int x;
scanf("%s%d",op,&x);
if(*op == 'I')insert(x);
else {
if(find(x))puts("yes");
else puts("No");

}
}
return 0;
}

开放寻址法

#include <iostream>
#include <cstring>
using namespace std;
const int N = 200003,null = 0x3f3f3f;
int h[N];
int find(int x)
{
int k = (x%N + N) % N;
while(h[k] != null && h[k] != x)
{
k++ ;
if(k == N) k = 0;
}
return k ;
}
int main ()
{
int n;
scanf("%d",&n);
memset(h,0x3f,sizeof h);//按字节的map set
while(n--)
{
char op[2];
int x;
scanf("%s%d",op,&x);
int k = find(x);
if(*op == 'I') h[k] = x;
else {
if (h[K] != null) puts("Yes");
else puts("No");

}
}
return 0;

}

![[Pasted image 20240709174144.png]]

字符串前缀哈希的核心思想是：

  1. 通过某种哈希函数将字符串映射为一个整数（哈希值）。
  2. 利用前缀哈希预处理，将字符串的所有前缀都计算出哈希值，存储在一个数组中。
  3. 通过前缀哈希值，可以在常数时间内计算任意子字符串的哈希值。

大白话就是对字符串进行设置一个哈希值，从第一个开始，每加一个就设置一个，belike:
a -12
ab-14
abb-16

我们常用的哈希函数形式为： [ text{hash}(s) = (s[0] times P^0 + s[1] times P^1 + s[2] times P^2 + ldots + s[n-1] times P^{n-1}) % M ]

每个字符 ( s[i] ) 乘以一个不同的幂次 ( P^i )，最后结果取模 ( M )，以减少冲突。选择合适的质数 ( P ) 和 ( M ) 是关键。

![[Pasted image 20240709174956.png]]

#include <iostream>
using namespace std;
typedef unsigned long long ULL;// 定义一个无符号长整形别名 ULL
const int N = 100010,p = 131;// 字符串的最大长度
// p基数，可选的质数，通常选为131或13331
int n,m;// 字符串长度和询问次数
char str[N];// 存储输入的字符串，长度为 N
ULL h[N],p[N];// 前缀哈希数组 h 和幂数组 p
// 函数 get 用于获取子串的哈希值
ULL get(int l ,int r)
{
return h[r]-h[l-1] *p[r-l+1];
}
int main ()
{// 读取输入的字符串长度 n，询问次数 m 和实际的字符串 str
scanf("%d%d%s",&n,&m,str+1);
p[0] = 1;
// 预处理计算前缀哈希值和幂值
for(int i = 1;i<=n;i++)
{
p[i] = p[i-1] * p;// 计算 p 的幂次
h[i] = h[i-1] * p + str[i];// 计算前缀哈希值
}
while(m--)
{
int l1,r1,l2,r2;
scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
// 比较两个子串的哈希值
if(get(l1,r1) == get(l2,r2)) puts("Yes");
// 哈希值相同，子字符串相等
else puts("No");// 哈希值不同，子字符串不相等 
}
return 0;
}

幂次数组 p 的作用

幂次数组的作用是存储基数 P 的不同幂次。之所以需要这个数组，是因为在计算哈希值时，我们需要用到 P 的幂次。具体而言，p$i$ 表示 P 的 i 次方。

前缀哈希

前缀哈希是一种技巧，通过预处理字符串使得任意子串的哈希值可以通过一次减法和乘法快速计算。

假设我们有一个字符串 str，长度为 n，基数 P 为 131。我们要计算字符串 str 的前缀哈希数组 h 和幂次数组 p。

幂次数组 p 的计算
for (int i = 1; i <= n; i++) 
{ pi=p[i - 1]* P; }

#stl
![[Pasted image 20240709180259.png]]
![[Pasted image 20240709180611.png]]

vector
size()返回元素个数
empty()返回是否为空
clear()清空
front()/back()
push_back()/pop_back()
begin()/end()
支持比较运算

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
int main()
{
vector<int> a;
for(int i = 0;i<10;i++)
a.push_back(i);
for(int i = 0;i<a.size();i++) cout << a[i] << ' ';
cout << endl;
for(vector<int> ::iterator i = a.begin();i != a.end();i++)
cout << *i << ' ';
cout << endl;
for(auto x : a) cout << x << ' ';
cout << endl;
return 0;
}

pair<int,int>
first,second,
pair <int ,pair<int ,int>> p;

string 字符串， substr(),c_str()
size()
empty()
clear()
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main ()
{
string a = "yxc";
a+="def";
a+='c';
cout << a << endl;//yxcdefc
cout << a.substr(1,2) << endl;//xc

}

queue
push()
front()
size()
back()
empty()
pop()

priority_queue 
push()
top()返回堆顶元素
pop()弹出堆顶元素
//默认大根堆
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
int main()
{
priority_queue<int> heap;
heap.push(-x);//小根堆
/
priority_queue<int,vector<int>,greater<int>> heap;
return 0;
}

stack
size()
empty()
push()
top()
pop()


deque //双端队列
size ()
empty()
clear()
front()
back()
push_back() /pop_back()
push_front()/pop_back()
begin()/end()
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
deque<int> q;
q.clear();
return 0;
}

set map multiset multimap 基于平衡二叉树，动态维护有序序列
size()
empty()
clear()
begin()/end() ++,-- 返回前驱和后继
set / multiset
insert()
find()
count()
erase()
1,输入是一个数x,删除所有x;o(k+logn)
2,输入一个迭代器，删除这个迭代器;

lower_bound (x) 返回大于等于x的最小的数的迭代器
upper_bound (x) 返回大于x的最小的数的迭代器
                      很重要
map/multimap 
insert() 插入的数是一个pair
erase()  输入的参数是pair或者迭代器
find()


#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <map>

using namespace std;
int main()
{
map<string ,int> a;
a["yxc" ] = 1;
cout << a["yxc"] << endl;
return 0;

}

![[Pasted image 20240709193834.png]]

bitset 


`bitset` 是 C++ 标准库中的一个模板类，用于在编译时创建固定大小的位数组。
它提供了方便的位操作功能，比如位与、位或、位异或、左移和右移等
操作。

`bitset` 是在 `<bitset>` 头文件中定义的。

 
bitset<10000> s;
~ & | ^
>> <<
== !=
[]
count ()返回多少个1
any()判断是否至少有一个1
none() 判断是否全为0
set() 把所有位置变成1
set(k , v) 把第k位变成v
reset() 把所有位变成0
flip() 等价于
flip(k) 把第k位取反

bs1.set(1); // 将第1位设置为1 
bs2.set(); // 将所有位设置为1
bs1.reset(1); // 将第1位设置为0 
bs2.reset(); // 将所有位设置为0
bs2.flip(1); // 翻转第1位 
bs3.flip(); // 翻转所有位

- `count()`: 返回位为1的个数。
- `any()`: 如果至少有一位是1，返回 `true`。
- `none()`: 如果所有位都是0，返回 `true`。
- `all()`: 如果所有位都是1，返回 `true`。

习题

![[Pasted image 20240709195157.png]]
![[Pasted image 20240709195615.png]]

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int n,m,x;
int a[N],b[N];
int main()
{
scanf("%d%d%d",&n,&m,&x);
for(int i = 0;i<n;i++)
scanf("%d",&a);
for(int i = 0;i<m;i++)scanf("%d",&b[i]);
for(int i = 0,j = m-1;i<n;i++)
{
while(j >= 0 && a[i] + b[j] > x)j--;
if(a[i]+b[j] == x) printf("%d%d\n" ,i,j);

}
return 0;
}

区间和
![[Pasted image 20240706160759.png]]
![[Pasted image 20240709201648.png]]
可以改成lower_bound

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 300010;
int n, m;
int a[N], s[N];
vector<int> alls;
vector<PII> add, query;

int find(int x) {
    return lower_bound(alls.begin(), alls.end(), x) - alls.begin() + 1;
}

vector<int>::iterator unique(vector<int>& a) {
    int j = 0;
    for (int i = 0; i < a.size(); i++)
        if (!i || a[i] != a[i - 1])
            a[j++] = a[i];
    return a.begin() + j;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        int x, c;
        cin >> x >> c;
        add.push_back({ x,c }); // 插入数
        alls.push_back(x); // 离散化的数组
    }
    for (int i = 0; i < m; i++) {
        int l, r;
        cin >> l >> r;
        query.push_back({ l,r });
        alls.push_back(l); // 待离散化数组
        alls.push_back(r);
    }
    // 去重
    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    // 处理插入
    for (auto item : add) {
        int x = find(item.first);
        a[x] += item.second;
    }

    // 处理前缀和
    for (int i = 1; i <= alls.size(); i++) s[i] = s[i - 1] + a[i];

    // 处理询问
    for (auto item : query) {
        int l = find(item.first), r = find(item.second);
        cout << s[r] - s[l - 1] << endl;
    }
    return 0;
}

单链表

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010;
int head ,e[N],ne[N],idx;
void init()
{
head = -1;
}
void add_head(int x)
{
e[idx] = x,ne[idx] = head,head = idx ++ ;

}
void add_k(int k ,int x)
{
e[idx] = x ,ne[idx] = ne[k],ne[k] = idx++;
}
void remove(int k)
{
ne[k] = ne[ne[k]];
}
int main()
{
init();
int m;
cin >> m;
while(m--)
{
char op;
int k ,x;
cin >> op;
if(op == 'H')
{
cin >> x;
add_head(x);
}
else if(op == 'I')
{
cin >> k >>x;
add_k(k-1,x);
}
else 
{
cin>>k;
if(!k) head = ne[head];
else remove(k-1);
}
}
for(int i = head;i!= -1;i = ne[i])
cout << e[i] << ' ';
cout << endl;
return 0;
}

![[Pasted image 20240709203943.png]]

循环双链表
#include <iostream>

const int N = 100010;
int e[N],l[N],r[N],idx;
void init()
{
r[0] = 1,l[1] = 0;
idx = 2;
}
void add(int k,int x)
{
e[idx] = x;
r[idx] = r[k];
l[idx] = k;
l[r[k]] = idx;
r[k] = idx;
idx++ ;

}
void remove(int k)
{
r[l[k]] = r[k];
l[r[k]] = l[k];
}
int main()
{
int m;
cin >> m;
init();
while(m--)
{
string op;
int k ,x;
cin >> op;
if(op == "L")
{
cin >> x;
add(0,x);
}
else if(op == "R")
{
cin >> x;
add(l[1],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 << r[i] << ' ';
cout << endl;
return 0;
}

kmp
![[Pasted image 20240709210425.png]]


原文地址：https://blog.csdn.net/2302_79934729/article/details/140388717

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2024