#數組模擬鏈表

#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           rootY2     - 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為當前節點uif(u*2 <= size && h[u*2] < h[t]) t = u*2;// 如果左子節點更小，更新tif(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;// 初始堆大小等于nfor(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;  // 在堆數組中插入元素 xup(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 setwhile(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 和實際的字符串 strscanf("%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;//yxcdefccout << 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 / multisetinsert()find()count()erase()1,輸入是一個數x,刪除所有x;o(k+logn)2,輸入一個迭代器，刪除這個迭代器;lower_bound (x) 返回大于等于x的最小的數的迭代器upper_bound (x) 返回大于x的最小的數的迭代器很重要
map/multimap insert() 插入的數是一個pairerase()  輸入的參數是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 ()返回多少個1any()判斷是否至少有一個1none() 判斷是否全為0set() 把所有位置變成1set(k , v) 把第k位變成vreset() 把所有位變成0flip() 等價于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]]