#### [](
)5.單調棧
**常見模型：找出每個數左邊離它最近的比它大/小的數**


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

while (tt && check(stk[tt], i)) tt -- ;
stk[ ++ tt] = i;

#### [](
)6\. 單調隊列
**常見模型：找出滑動窗口中的最大值/最小值**


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

while (hh <= tt && check_out(q[hh])) hh ++ ; // 判斷隊頭是否滑出窗口
while (hh <= tt && check(q[tt], i)) tt -- ;
q[ ++ tt] = i;

#### [](
)7.KMP


1.
2.
3.
4.
5.
6.
7.
8.
9.

while (j && p[i] != p[j + 1]) j = ne[j];
if (p[i] == p[j + 1]) j ++ ;
ne[i] = j;

while (j && s[i] != p[j + 1]) j = ne[j];
if (s[i] == p[j + 1]) j ++ ;
if (j == m)
{
j = ne[j];
// 匹配成功後的邏輯
}

#### [](
)8.Trie樹


1.
2.
3.
4.
5.
6.
7.
8.
9.

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

#### [](
)9.並查集
**(1)樸素並查集：**


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

// 返回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);

**(2)維護size的並查集：**


1.
2.
3.
4.
5.
6.
7.

//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);

**(3)維護到祖宗節點距離的並查集：**


1.
2.
3.
4.
5.
6.
7.

//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)的偏移量

#### [](
)10.堆


1.
2.
3.
4.
5.
6.
7.
8.
9.

swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);

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

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

#### [](
)11.一般哈希
**(1) 拉鏈法**


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

// 向哈希錶中插入一個數
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;
}

**(2) 開放尋址法**


1.
2.
3.
4.
5.
6.
7.

// 如果x在哈希錶中，返回x的下標；如果x不在哈希錶中，返回x應該插入的比特置