前言
這期將會講到基礎算法篇里面的數據結構（進階），主要包括單調棧，單調隊列，并查集，擴展域并查集，帶權并查集，字符串哈希，Trie樹。
數據結構(進階）正文
單調棧
里面存儲的單增或者單減的棧
應用:
1.尋找當前元素左側，離它最近，并且比它大的元素在哪
2.尋找當前元素左側，離它最近，并且比它小的元素在哪
3.尋找當前元素右側，離它最近，并且比它大的元素在哪
4.尋找當前元素右側，離它最近，并且比它小的元素在哪
尋找當前元素左側，離它最近，并且比它大的元素在哪
int a[N]里面存數（已存好）
ret里面存的答案
stack<int>st;//維護一個單調遞減的棧,里面存的是下標
for(int i = 1;i<=n;i++)
{
//棧里面小于等于a[i]的元素全部出棧while(st.size()&&a[st.top()]<=a[i]) st.pop();
//此時棧頂元素存在，棧頂元素就是所求結果if(st.size()) ret[i]=st.top();
st.push(i);}
尋找當前元素右側，離它最近，并且比它大的元素在哪
改成for(int i = n;i>=1;i--)
尋找當前元素左側，離它最近，并且比它小的元素在哪
int a[N]里面存數（已存好）
ret里面存的答案
stack<int>st;//維護一個單調遞增的棧，里面存的是下標
for(i=1;i<=n;i++)
{
//棧里面大于等于a[i]的元素全部出棧
while(st.size()&&a[st.top()]>=a[i])st.pop();//這里的符號是跟上面的唯一區別
//此時棧頂元素存在，棧頂元素就是所求結果
if(st.size()) ret[i]=st.top();
st.push(i);}
尋找當前元素右側，離它最近，并且比它小的元素在哪
把上面改為for(int i=n;i>=1;i--)即可//n次逆遍歷可以記一下是這個
總結:
找左側，正遍歷；找右側，逆遍歷；
比它大，單調減；比它小，單調增。//構造___棧
例題: 洛谷 P1901 發射站
洛谷 P1901 發射站
單調隊列
是一個存單調元素的雙端隊列
應用:解決滑動窗口內的最大值最小值問題
(前面基礎算法的滑動窗口不是用來求其中的最值的)
洛谷 P1886 滑動窗? /【模板】單調隊列
例題：洛谷 P1886 滑動窗? /【模板】單調隊列
int a[N]里面存的元素(已存好)
窗口內最大值:
從左往右遍歷元素，維護一個單調遞減的雙端隊列
當前元素進隊之后，注意維護隊列內的元素在大小為k的窗口內
此時隊頭元素就是最大值
代碼：
deque<int>q;//存下標
for(int i = 1;i<=n;i++)
{while(q.size()&&a[q.back()]<=a[i])q.pop_back();
q.push_back(i);
if(q.back()-q.front()+1>k) q.pop_front();
if(i>=k)cout<<a[q.front()]<<" ";}窗口內最小值:
從左往右遍歷元素，維護一個單調遞增的雙端隊列
當前元素進隊之后，注意維護隊列的元素在大小為k的窗口內
此時隊頭元素就是最小值
并查集
并查集是一種用于維護元素所屬集合的數據結構，用雙親表示法來實現
應用eg:維護連通塊的信息
相關的一些概念:
查詢操作:查找元素x屬于哪一個集合，一般會在每個集合中選取一個元素作為代碼,查詢的是這個集合中的代表元素
合并操作:將元素x所在的集合與元素y所在的集合合并成一個元素
(注意:合并的是元素所屬的集合，而并非單單兩個元素)
判斷操作:判斷元素x和y是否在同一個集合
洛谷 P1551 親戚
并查集的實現:
例題：洛谷 P1551 親戚
1.初始化:讓元素自己指向自己即可
int fa[N];一般并查集用fa來表示
for(int i=1;i<=n;i++) fa[i] = i;2.查詢操作:就是一直向上"找爸爸"(這個find可以多次使用)
int find(int x)//查詢x所在集合的代表元素是誰
return fa[x] == x?x:find(fa[x]);//是x就返回x，不是就find(fa[x])3.合并操作:(重復合并不會出錯)
讓元素x所在集合的代表元素指向元素y所在集合的代表元素
void un(int x,int y)
{ int fx = find(x);int fy = find(y);fa[fx] = fy;}4.判斷操作
看看兩者所在集合的總代表元素是否相同
bool issame(int x,int y)
{return find(x) == find(y);}
擴展域并查集
元素之間存在多種關系比如:朋友和敵人 而不像上面只存在:親戚這樣一種關系的話，就要用擴展域并查集
和普通并查集的區別:將每個元素拆分成多個域，每個域代表?種狀態或者關系
洛谷 P1892 [BOI2003] 團伙
例題:洛谷 P1892 [BOI2003] 團伙
這里只寫不同點:
find和un與上面的寫法一模一樣
//兩種關系，所以N*2：x的母敵人是x+n
int fa[N*2];
//初始化:
for(int i=1;i<=n*2;i++) fa[i]=i;
while(m--)//m是題目中的"m個關系"
{if(op == 'F') un(x,y);else//敵人，讀取的是y和x是敵人關系{//存法:這倆都得寫，少一個都不行un(x,y+n);//這兩是朋友關系un(y,x+n);//這兩是朋友關系}
}
帶權并查集
概念:就是在普通并查集的基礎上，為每個結點增加一個權值。這個權值可以表示當前結點與父結點之間的信息(因為find那我們用的路徑壓縮，因為最終這個權值是當前結點相對于根節點的信息)
洛谷 P1196 [NOI2002] 銀河英雄傳說
帶權并查集的一些操作:(這里的d[N]以到父結點的距離為例)
例題:洛谷 P1196 [NOI2002] 銀河英雄傳說
新加了一個d[N]1.初始化:
多初始化個d[i]即可2.查詢操作:(對這種代碼來說，一個結點只能進行一次這種find操作!)
int find(int x)
{ if(fa[x]==x) return x;int t = find(fa[x]);//這一步要先搞d[x]+=d[fa[x]];//不為距離時可能會變為其他
return fa[x] = t;//完成路徑壓縮
}3.合并操作://x所在集合與y所在集合合并，x與y之間的權值是w
void un (int x,int y, int w)
{int fx = find(x),fy = find(y);
if(fx!=fy){fa[fx] = fy;d[fx]= d[y]+w-d[x]; //可能會變，這里是拿距離舉例的} }4.查詢操作://查詢y與x之間的距離
int query(int x,int y)
{int fx = find(x),fy = find(y);
//如果不在同一個集合中，說明距離未知(具體返回什么要看題意）if(fx!=fy)return 0x3f3f3f3f;
return d[y]-d[x];
}
字符串哈希
一般利用前綴和思想去預處理字符串匯總每個前綴的哈希值
（使用前提:需要多次詢問一個字符串的子串的哈希值）
核心思想:把字符串映射成P進制數字
P一般選擇13331或者131
字符串哈希的作用:
字符串哈希一般用于判斷兩個字符串及其各子串是否相等
(和字典樹的區別是這個字符串哈希側重于判斷功能)
洛谷 P10468 兔?與兔?
例題:洛谷 P10468 兔?與兔?
前綴字符串哈希模板:
typedef unsigned lon long ULL;
P = 13331;
int len;
string s;//一般都要搞一下s = ' '+s;來讓i從1開始搞
ULL f[N];//前綴哈希數組
ULL p[N];//記錄P的i次方－>p[i]為P的i次方
//處理前綴哈希數組以及P的i次方數組
void init_hash()
{f[0] = 0;p[0] = 1;for(int i = 1;i<=len;i++){ f[i]=f[i-1]*P+s[i];p[i]=p[i-1]*P;} }
//快速求得任意區間的哈希值
ULL get_hash(int l,int r)
{return f[r]-f[l-1]*p[r-l+1];}如果題目只是簡單的求單個字符串的哈希值:
ULL gethash()
{ULL ret = 0;for(int i =1;i<=len;i++){ret = ret*p+s[i];} return ret;}
Trie樹（又叫字典樹或前綴樹）
是一種能夠快速插入和查詢字符串的數據結構
理解:我們可以把字典樹想象成一顆多叉樹，每一條邊代表一個字符，從根節點到某個節點的路徑就代表了一個字符串
作用:
1.查詢某個單詞是否出現過，并且出現幾次
2.查詢有多少個單詞是以某個字符串為前綴
3.查詢所有以某個前綴開頭的單詞
字典樹的實現:
默認需要存的全是小寫字母1.準備工作int tree[N][26],p[N],e[N];//N一般令為所有字符串中一共有多少個字符
// p[i]表示第i個被開辟的點被經過了多少次，
//e[i]表示以第i個被開辟的點為結尾的有多少個
int idx;2.插入字符串
void insert(string&s)
{int cur = 0;//從根節點開始p[cur]++;//這個格子經過一次for(auto ch:s){
//這個path的表達式常改!!!依據題意改int path = ch - 'a';//如果沒有路if(tree[cur][path] == 0) tree[cur][path]= ++idx;cur = tree[cur][path];p[cur]++ }e[cur]++;
}3.查詢字符串出現的次數:
int find(string&s)
{int cur = 0;for(auto ch:s){int path = ch - 'a';if(tree[cur][path] == 0) return 0;cur = tree[cur][path];} return e[cur];}4.查詢有多少個單詞以字符串s為前綴:int find_pre(string&s)
{int cur = 0;for(auto ch:s){int path = ch-'a';if(tree[cur][path] == 0) return 0;cur = tree[cur][path];} return p[cur];}例題:洛谷 P2580 于是他錯誤的點名開始了
洛谷 P2580 于是他錯誤的點名開始了
