[簡報](https://hackmd.io/@Lssh-Algorithm/Syn6N7izc) # 資料結構 --- ## STL ---- ## STL - `vector` - `tuple` - `algorithm` - `set` - `map` - `priority_queue` - `stringstream` ---- ### vector 多功能的陣列 ```cpp [] #include <vector> vector<int> v; v.size(); // v 的長度 v.resize(n); // 調整大小為 n v.clear(); // 初始化 v v.push_back(val); // 放 val 在 v 後面 v.begin(); v.end(); // v 的 iterator ``` ---- ### vector | vector | array | | --- | --- | | 可更動大小 | 不能更動大小 | | 宣告較複雜 | 宣告簡單 | | 功能多 | 很單純的陣列 | ---- ### vector #### construct - `vector<int> v(n, 0);` - `int`: 陣列中要放的型別 - `v`: 名字 - `n`: 長度 - `0`: 初始值 - 沒放的話則會是預設值 - 二維陣列 ``` vector<vector<int> > v(n,vector<int> (n, 0)); ``` ---- ### vector #### `push_back()` v.s. `emplace_back()` - `v.push_back(val);` - 把 `val` 的值**複製**進去 - `v.emplace_back(val);` - 把 `val` 做為**參數**來宣告 - 速度上幾乎**沒差** - 除非你 `push_back()` 一個很大的東西 ---- ### vector #### `push_back()` v.s. `emplace_back()` - `emplace_back()` 的好處在於它可以減少 「宣告」的繁瑣 ```cpp [|1|3-4|6-7] vector<pair<int, int> > arr; int main() { arr.push_back(make_pair(2, 5)); // 要先產生 pair 才可以被複製 arr.emplace_back(2, 5); // 簡潔許多 return 0; } ``` ---- ### vector #### `resize()` - `v.resize(n)` - 把 `v` 長度設為 $n$ - `v.resize(n, 0)` - 如果 `v` 需要**增加長度**，值會是 $0$ - 已存在的值**不會**被改變！！ - `v.assign(n, 0)` - 把 `v` 初始化成長度為 $n$ 且值為 $0$ ---- ### vector #### `resize()` v.s. `reserve()` - `resize(n)` 可以把陣列長度設為 $n$ - `reserve(n)` 在陣列後面預留 $n$ 的空間 - `v` 的 `size` 仍不變 - 用來避免 `push_back()` 時， 可能需要花 $\mathcal{O}(n)$ 的時間搬移 `v` 到連續記憶體更長的地方 ---- ### vector #### 請不要用 `erase()`, `insert()` - vector 是連續儲存的，所以**移除**或**插入**在中間會需要 $\mathcal{O}(n)$ 的時間。 ---- ### vector #### iterator - `v.begin()`: 回傳指向第 0 個的 iterator - `v.end()`: 回傳指向最後一項的下一項的 iterator 所以 `v.begin()` 到 `v.end()` 是**左閉右開** - `v.rbegin()`: 回傳指向最後一項的 iterator - `v.rend()`: 回傳指向第 0 項的前一項的 iterator ---- ### vector #### iterator for 迴圈 ```cpp [|5|7-9] #include <vector> vector<int> v(10); int main() { for (int &i: v) cin >> i; // 輸入 10 個東西到 v for (auto it = v.begin(); it != v.end(); ++it) { cout << *it << '\n'; // 記得加 * 在變數前面來取值 } } ``` ---- ### tuple 適合儲存一組資料的東西（例如： x, y 座標） ``` cpp [|4|5|6|4, 8|5, 9] #include <tuple> #include <string> #include <vector> tuple<int, long long, string> t = {13, 53, "hello"}; pair<int, long long> p = {11, 42}; pair<int, vector<int> > pp; // 要存 vector 也可以 get<0>(t) // 回傳 t 的第 0 個東西 (13) p.first; p.second; // 分別回傳 p 的第 0 項跟第 1 項 ``` ---- ### tuple #### construct - `tuple` 最多可以存 10 樣東西 - `pair` 是特化版的 `tuple` ，只能存兩種東西 - `pair<int, long long> p = {11, 42};` - `make_pair(11, 42);` ---- ### algorithm ```cpp [] #include <algorithm> ``` - `sort()` - `lower_bound()`, `upper_bound()` - `nth_element()` - `next_permutation()` ---- ### algorithm #### `sort()` $$ \mathcal{O}(n\lg n) $$ - `sort(v.begin(), v.end());` - 把 `v.begin()` 到 `v.end()` 之間排序 - `sort(v.begin(), v.end(), cmp);` - 依照自訂的 `cmp` 函式來排序 ---- ### algorithm #### 自訂 `cmp` ```cpp [|3|3,8|3-6,9|3,10] #include <algorithm> #include <vector> vector<int> v = {1, 3, 5, 2, 4}; bool cmp(const int &x, const int &y) { return x > y; } int main() { sort(v.begin(), v.end()); // 由小到大（預設） sort(v.begin(), v.end(), cmp); // 由大到小（利用 cmp 函式） sort(v.rbegin(), v.rend()); // 也是由大到小（倒著排序） } ``` ---- ### algorithm #### `lower_bound()`, `upper_bound()` <font size=6> 二分搜 $$ \mathcal{O}(\lg n) $$ - `vector` 要事先排序好 - `lower_bound(v.begin(), v.end(), val);` - 在範圍找出 $\geq$ `val` 中，最小的 iterator - `upper_bound(v.begin(), v.end(), val);` - 在範圍找出 $\gt$ `val` 中，最小的 iterator - `{1, 2, 3, 3, 5}` `-------^-----^-` </font> ---- ### algorithm #### `nth_element()` $$ \mathcal{O}(n) $$ - `nth_element(v.begin(), v.begin() + val, v.end());` - 在範圍中，找出第 `val` 項 - 第 `val` 項之前的值都會 $\leq$ 第 `val` 項 - 第 `val` 項之後的值都會 $\geq$ 第 `val` 項 - 可以放 `cmp` - `{1, 5, 4, 2, 3} -> {1, 2, 3, 5, 4}` ---- ### algorithm #### `next_permutation()` $$ \mathcal{O}\Big(\frac{n}{2}\Big) $$ - `next_permutation(v.begin(), v.end());` - 找出下一**字典序**大的排列 - `prev_permutation()` 可以找下一小的 - 可以放 `cmp` - `{1, 2, 3, 4, 5} -> {1, 2, 3, 5, 4}` ---- ### set 沒錯，就是數學課教的**集合** ```cpp [] #include <set> set<int> s; s.insert(val); // 在 s 中放入 val s.erase(val); // 把 val 從 s 中移除 s.clear(); // 清空 s s.size(); // s 的大小 s.find(val); // 找 val 的 iterator s.count(val); // 找 val 在 s 中的數量 s.begin(); s.end(); // iterator ``` ---- ### set - 值**不能重複** （`multiset` 支援插入重複的值） - 會自動排序 - 可以快速取最大、最小值 - `unordered_set` 則不會排序 - 不能隨機取值 - 就是不行用 `s[2]` 來找第 2 小的東西啦 - 可以用 iterator 迭代 ---- ### set #### construct - `set<int> s;` - `set<int, cmp> sc;` - 依照 `cmp` 去排序 - 但是跟普通宣告 `cmp` 的方式不太一樣... ---- ### set #### construct ```cpp [|9|3-7,10] #include <set> struct cmp { bool operator() (const int &a, const int &b) const { return a > b; } }; set<int> s; // 由小到大排列 set<int, cmp> sc; // 由大到小排列 ``` ---- ### set #### `insert()` - `s.insert(val);` - 放 `val` 進 `s` 裡面 - `s.emplace(val);` - 和 vector 一樣 ---- ### set #### `erase()` - `s.erase(val);` - 在 set 中移除值為 `val` 的東西 - 回傳被移除後的個數 - `val` 也可以是 iterator - 回傳被移除後的下一個 iterator （下一個比它大的） ---- ### set #### `erase()` 毒瘤操作 ```cpp [|5|6-10|7-8|6-10] #include <set> set<int> s; int main() { s.emplace(1); s.emplace(2); s.emplace(3); for (auto it = s.begin(); it != s.end(); ) { if (*it == 2) it = s.erase(it); // 如果 it 指向 2，erase 以後會回傳 3 的 iterator else it++; } } ``` ---- ### set #### `find()` - `s.find(val);` - 回傳 `val` 的 iterator - 如果 `val` 不存在，則會回傳 `s.end()` ---- ### set #### `count()` - `s.count(val);` - 回傳 `val` 的個數 - set 同樣的值只能有一個，所以只會回傳 0 或 1 ---- ### set #### `iterator` - `s.begin()` 指向第 0 項（最小值） - `s.rbegin()` 指向最後一項（最大值） - 跟 vector 一樣，可以用 for 迴圈迭代 ---- ### map 跟字典一樣，問一個答一個 ```cpp [] #include <map> map<int, string> m; // <key, value> m[1] = "NCKU"; m[5] = "YYDS"; // 定義 m.clear(); // 清空 m.find(val); // 回傳 key = val 的 iterator m.count(val); // 回傳 key = val 的個數 m.begin(); m.end(); // iterator ``` ---- ### map - 每個元素一個 pair (`{key, value}`) - key 不能重複 (`multimap` 支援 `key` 重複) - 會自動排序 (依據 `key` 進行排序) - `unordered_map` 則不會排序 ---- ### map #### usage ```cpp [] #include <map> map<int, int> m; m[2] = 7; // 定義 m[4]++; // 如果索取的 key 未被定義，則會使用預設 // m[4] = 1 ``` ---- ### map #### `find()` - `m.find(2);` - 尋找 `key` $=$ 2 的元素 - 回傳 `pair {2, 7}` ---- ### map #### iterator ```cpp [] #include <map> map<int, int> m; for (pair<const int, int> &i: m) { cout << "key: " << i.first << ' '; cout << "value: " << i.second << '\n'; } ``` ---- ### priority_queue 跟 queue 有甚麼差別呢？ ```cpp [] #include <queue> priority_queue<int> pq; pq.empty(); // 是否空了 pq.size(); // 大小 pq.top(); // pq 中，值最大的 pq.pop(); // pq 中，移除值最大的 pq.push(val); // 把 val 放入 pq 中 ``` ---- ### priority_queue #### construct <font size=6> - `priority_queue<int> pq;` - 預設是**從大到小**排列！！！ - 可以使用 cmp - `priority_queue<T, vector<T>, less<T> >` - 預設為 `less<T>`，可以使用 `greater<T>` </font> ---- ```cpp struct cmp { bool operator() (int &a, int &b) { return a > b; // 跟前面的反過來，要小心 } }; priority_queue<int, vector<int>, cmp> pq; ``` ---- ### stringstream #### 字串分割、轉換好幫手 ```cpp [] #include <sstream> stringstream ss; int a, b; ss << "12 53"; // ss 寫入 "12 53" ss >> a >> b; // 從 ss 讀出，a = 12, b = 53 ss.clear(); // 清除 flag ss.str("YYDS"); // 把 ss 的內容設定為 "YYDS" ``` ---- ### stringstream #### construct - `stringstream ss` - stringstream 宣告速度不快，所以請避免重複宣告，多資源回收～ ---- ### stringstream #### 寫入讀出 - `ss << "Hello";` - 寫入 - `ss >> s;` - 讀出 - 其實就跟 `cin` 、 `cout` 一樣啦 ---- ### stringstream #### `clear()` `ss.clear()` 它只會初始化 `ss` 裡的 `flag`，`buffer` 不會清空。 #### 不會清空！！！<!-- .element: class="fragment" data-fragment-index="1" --> ### 不會清空！！！<!-- .element: class="fragment" data-fragment-index="2" --> ## 不會清空！！！ <!-- .element: class="fragment" data-fragment-index="3" --> ---- ### stringstream #### `str()` - `ss.str("YYDS");` - 把 ss 的內容設成 "YYDS" - `ss.str();` - 回傳目前 ss 裡的字串 --- ## DSU ---- ### DSU 有些集合，他們互相交集為空集合， 則這些集合稱為並查集，又稱互斥集。 Note: 這些互相沒有交集的集合，彼此的聯集正好是整個宇集，也就是所有元素都恰好出現在某個集合內，不重複出現，那這些集合恰好可以用來表示點與點之間的集合關係。 ---- ### 例子 學校裡有一些幫派，每個人只會屬於一個幫派，若某人不加入別人，代表他自己就是一個單人幫派。 幫派之間會互相鬥爭，贏得一方可以把對方所有人納入自己的幫派，也就是把兩個幫派合併成一個。 這個例子可以用 DSU 來解決嗎？ ---- ### 老大 剛剛說的幫派是一群人組成的，我們只知道他是一個群體，但要怎麼表示這個群體最簡單呢？ 我們可以從這個幫派之中，隨便挑一個人來當老大，老大的作用就是用來代表這群體。 note: 但現在遇到了問題，如果幫派每打架一次，輸的那方所有人都要換成對方的老大，時間複雜度是 $\mathcal{O}(n)$ 為了方便，我們讓每個人心目中都各自存在一個老大。自己的老大是別人，表示你不是這個群體的代表，若自己的老大是自己，代表你就是這個幫派真正的老大，也就是代表這個幫派所有人的”關鍵人”。 我們只要透過不斷詢問老大的老大，直到問到有人的老大是自己後，才可以確定這個群體的代表人是誰。 ---- 但這樣會比較快嗎？ 最差狀況還是 $\mathcal O(n)$ 查詢 note: 最差的狀況，群體內每個人的老大都有另一個老大，除了最終的老大。 這樣為了找到代表此群體的最終老大，對最下面人來說，他要查詢的時間複雜度是 $\mathcal{O}(n)$。 我們稍後會介紹如何實做能解決這個不夠好的複雜度。 ---- ### 資料結構 - `parent[n] (boss[n])` 用來表示你的上層是誰，用 `parent[i] == i` 來偵測自己是否是最上層。 - `size[n]` 用來紀錄集合的大小，只有在 index 是最終老大時才有意義。 ---- ### 精簡版陣列 - `pa_sz[n]` ```cpp= if (parent[i] != i) pa_sz[i] = parent[i]; else pa_sz[i] = -size[i]; ``` Note: 這是精簡版，把上述兩個陣列融合。 仔細注意可以發現，parent 在不是最終老大時存的是別人的 index，而最終老大的判斷方法則是用 parent[i] == i。 若我們能區分是否是最終老大，則最終老大的 parent 值存什麼也不是那麼重要ㄌ，反正我知道他是最終老大就好。 舉例來說，我可以讓每個最終老大的 parent 值都存 -1。這樣也可以達成判斷的效果。 既然如此，我們讓 pa_sz[i]， 如果 i 不是最終老大，存的就是他的上層老大， 否則 i 已經是最終老大了，則讓 pa_sz[i] 存負的集合 size， 因為剛剛說過，size[i] 只有在 i 是最終老大時才是有效的 size。 我們只要判斷 parent 值是正，就知道他是最終老大， 若是負的，則取絕對值後就是這個集合的 size。 如此一來，我們只要用一個陣列就可以知道這個dsu的整體架構，且可以同時儲存他的大小。 ---- ### find - 用來尋找最終老大。剛剛說過，一個一個找，最差情況會花費 $\mathcal{O}(n)$ 的時間。 ```cpp= [|3|2,3|] int find(int index) { if(parent[index] == index) return index; return find(parent[index]); // 一路往上找 } ``` Note: 那找n次就會花費O(n^2) 太慢ㄌ ---- ### find 路徑壓縮 路徑壓縮就是在找老大的過程中 順便把路徑上所有點的老大也設成最終老大 ```cpp= [|3|2,3|] int find(int index) { if(parent[index] == index) return index; return parent[index] = find(parent[index]); // 路徑壓縮 } ``` Note: 路徑壓縮是什麼？原本要找很多層的人，在往上尋找的過程，順便把自己的老大設成比較高位的老大，最好是最終老大，因為這樣代表他下次呼叫 `find()` 時只需要花很少步或是一步就可以找到最終老大。 所以我們在 return 前把當前這個人的老大設成他老大的老大，若每個人都這樣設定，因為遞迴的中止條件是遇到最終老大，再 return 回來當其他人的老大，所以在執行一次`find()` 之後，當中詢問過的節點的老大都會設成最終老大，下次不管是問誰，只要路徑經過這些人，都可以馬上到達最終老大。 均攤複雜度是$\mathcal{O}(n\,\lg\,n)$，具體我不會估計，大概是每次壓縮平均只會壓縮 $\lg\,n$ 層。 ---- ### union 合併兩個集合a, b ```cpp= [|2,3|2-4] void Union(int a, int b) { int fa = find(a), fb = find(b); size[fa] += size[fb]; parent[fb] = fa; } ``` ---- ### 啟發式合併 把小的集合接在大的集合下面，之後find會更快 ```cpp= [|3|] void Union(int a, int b) { int fa = find(a), fb = find(b); if(size[fb] > size[fa]) swap(fa, fb); size[fa] += size[fb]; parent[fb] = fa; } ``` ---- ### 查詢時間複雜度 都沒有：$O(n)$ 路徑壓縮：$O(\lg n)$ 啟發式合併：$O(\lg n)$ 啟發式合併＋路徑壓縮：$O(\alpha(n))$ 反阿卡曼函數 ---- ### 課後練習 [Kattis - Ladice](https://open.kattis.com/problems/ladice) [Kattis - Association for Control Over Minds](https://open.kattis.com/problems/control) [Codeforces - Social Network](https://codeforces.com/contest/1609/problem/D) note: 大家要去練習才知道要怎麼實際應用喔 --- ## Heap ---- ### Heap 樹狀資料結構 - min heap - max heap ---- ### 功能介紹 - `push()` - 將元素加入 heap 中 - `top()` - 從 heap 中取出最小元素 - `pop()` - 將 heap 中最小的元素去除 ---- ### 如何實現？ 把資料擺成 Complete Binary Tree<!-- .element: class="fragment" data-fragment-index="1" --> 保證子樹一定不小於自己，但左右子樹大小不保證<!-- .element: class="fragment" data-fragment-index="2" --> ---- ### 示意圖  ---- ### 樹的儲存方法 - 根節點 `idx=0` - 對於所有節點，若節點編號為 `i`，則左節點編號為 `2*i+1`，且右節點編號為 `2*i+2`  ---- ### top ---- #### top - 獲得最小值  ---- ### push ---- #### push - 把 `0` 加入 heap 中  ---- #### push - 把 `0` 加入 heap 中  ---- #### push - 把 `0` 加入 heap 中  ---- #### push - 把 `0` 加入 heap 中  ---- #### push - 把 `0` 加入 heap 中  ---- ### pop ---- #### pop  ---- #### pop  ---- #### pop  ---- #### pop  ---- #### pop  ---- #### pop  ---- ### 複雜度分析 - top 的複雜度為 $\mathcal{O}(1)$ - push,pop 的複雜度借為 $\mathcal O(\lg\, n)$ ---- ### 實作 - [priority_queue](https://hackmd.io/@Lssh-Algorithm/Syn6N7izc#/1/35) ---- ### Problems [Kattis - Jane Eyre](https://open.kattis.com/problems/janeeyre) [Kattis - Continuous Median](https://open.kattis.com/problems/continuousmedian)