基礎演算法 - HackMD

# 基礎演算法 by pooh 喔然後我有寫講義，可以點超連結已經會的人就會被我亂點喔(pyting聽到了嗎) ---- ## 自我介紹 - 第7屆資讀負責人(1 based) - 最弱的那一個 - 因為不會基礎演算法所以來當基礎演算法講師 - 實作很醜 - Ina 的鐵粉 <img align = "right" src="https://hackmd.io/_uploads/S1pDIq9d0.jpg" class="rounded" style="width: 100px; height: 100px"> - 沒有特殊經歷 - 有問題都可以問我，我會盡量回答 ---- ## 有關例題我的例題應該都會分基礎題跟思考題這兩塊，初學基本題寫完基本上就蠻夠的了，思考題是一些奇怪的變化，建議有基礎後再看會有一些不一樣的想法 (然後可能有被嗆過是毒瘤的也都會在那，不用太執著都要會寫)。至於空的時間我應該會拿一些我比較喜歡，想法又不難的題目來講。然後大部分的例題在講義內都有範例程式碼，但不建議抄，因為我code風很醜。 --- ## 大概內容 - 複雜度小複習 - [前綴和與差分](https://hackmd.io/@theworkingpooh/TIPLPrefixSum) - [二分搜](https://hackmd.io/@theworkingpooh/Binary_Search) - [雙指針與單調stuff](https://hackmd.io/@theworkingpooh/TwoPointers) - [分治(& 簡報限定的一點點倍增)](https://hackmd.io/@theworkingpooh/TIPLDevideandConquer) - [雜湊](https://hackmd.io/@theworkingpooh/TIPLHash) - 我的天哪 :arrow_up: 是超連結嗎，我可以偷捲接下這三節的內容嗎 --- ## 複雜度小複習我們都想要設計有效率又正確的演算法。畢竟暴力誰都會吧(痾WAWAWA，好好暴力超難的) 要怎麼預估一個程式能不能在給定的時間與記憶體限制內跑完呢? 痾靠複雜度跟經驗 ---- ## 好啊，阿要怎麼估通常我們會在意的是他執行起來會需要多少次操作或占多少空間。更具體的說，我們一般注重的是執行次數或占的空間與某些係數的關係 (也就是複雜度)。魚切應該有跟你們稍微講過複雜度了，所以我這邊就直接上一些範例。 ---- ### 範例 (偷from Pacybwoah) ```cpp= [1-7|4-6] int n; cin >> n; long long ans = 0; for (int i = 1; i <= n; i++){ ans += i; } cout << ans; ``` $\text{time:} O(n) \backslash \text{space:} O(1)$ ---- ### 範例 (偷from Pacybwoah) ```cpp= [1-8|4-7] long long n; vector <int> arr; cin >> n; for(int i = 0, a; i < n; i++){ cin >> a; arr.push_back(a); } cout << arr[n - 1]; ``` $\text{time:} O(n) \backslash \text{space:} O(n)$ ---- ### 範例 (偷from Pacybwoah) ```cpp= [1-8|4-7] long long n; int count = 0, five = 5; cin >> n; while (five <= n){ count += n / five; five *= 5; } cout << count; ``` $\text{time:} O(\log n) \backslash \text{space:} O(1)$ ---- ## 常數常數也是引響執行速度的關鍵之一，雖然好的複雜度常數不要太大通常都會過，但還是要好好注意。然後不同 judge 的速度也都不一樣，一個在 atcoder 會過的東西換到 zerojudge 上面很有可能會吃爆 TLE 在像 atcoder 這種 judge 你可以當一秒 $5 \times 10^8$ 在算，因為他真的很星爆，但換到 TIOJ 可能只能當 $2 \times 10^8$ 喔然後輸入輸出優化要開，雖然我可能平常練題都不開的。 ---- ### 大概要多好 | $N$ | 複雜度 | | --------------- | ----------------------------- | | $10^9, 10^{18}$ | $O(1), O(\log N)$ | | $10^6$ | $O(N), O(N \log N)$ | | $10^5$ | $O(N \sqrt{N}), O(N\log^2 N)$ | | $3 \times 10^3$ | $O(N^2), O(N^2 \log N)$ | | $4 \times 10^2$ | $O(N^3)$ | | $20$ | $O(2^N), O(N2^N)$ | | $7$ | $O(N!)$ | --- # 前綴和與差分 ---- ## 引導問題 [CSES - Static Range Sum Queries](https://cses.fi/problemset/task/1646) 給你一個整數序列 $A : A_1, A_2, \dots , A_N$，有 $Q$ 筆詢問 $(l, r)$，要求回答 $\sum_{i=l}^{r} A_i$。 $N, Q \le 2 \times 10^5$ 暴力?  $O(NQ)$ 大爆炸 ---- ### 優化? 考慮維護 $pre$，定義 $pre_{x} = \sum_{i=1}^{x} A_i$ 發現 $\sum_{i=l}^{r} A_i = \sum_{i=1}^{r} A_i - \sum_{i=1}^{l - 1} A_i$ $pre_{r} - pre_{l - 1}$ $O(N+Q)$ ---- ### 看code ```cpp= [1-22|13-16|17-20] #include <bits/stdc++.h> #define uwu return 0; using namespace std; const int SIZE = 2e5 + 5; long long pre[SIZE]; int n, q, l, r; int main(){ cin >> n >> q; for (int i = 1; i <= n; i++){ cin >> pre[i]; pre[i] += pre[i - 1]; } while(q--){ cin >> l >> r; cout << pre[r] - pre[l - 1] << '\n'; } uwu } ``` ---- ## 多一維呢? [CSES - Forest Queries](https://cses.fi/problemset/task/1652/) 給你一個 $N \times N$ 的二維表格 $A$，每一格 $A_{i,j} \in \{0, 1\}$，給 $Q$ 筆詢問 $(i_1, j_1, i_2, j_2)$，要求回答 $\sum_{i = i_1}^{i_2}\sum_{j = j_1}^{j_2} A_{i,j}$。 $N \le 10^3$ $Q \le 2 \times 10^5$ ---- ### 先看看一維的可以做到$O(N^2 + QN)$，$2 \times 10^8$ 有點危險 (你可以試試看啦) ---- ### 二維前綴和? $pre_{x, y} = \sum_{i = 1}^{x}\sum_{j = 1}^{y} A_{i,j}$ 會做嗎? 會吧變成$O(N^2 + Q)$(天哪!大發現欸) ---- ### 看code ```cpp= [1-34|22-26|28-32] #include <bits/stdc++.h> #define uwu return 0; using namespace std; const int SIZE = 1e3 + 5; int imap[SIZE][SIZE]; int main(){ int n, q; cin >> n >> q; char in_c; for (int i = 1; i <= n;i++){ for (int j = 1; j <= n;j++){ cin >> in_c; if(in_c == '*') imap[i][j] = 1; } } for (int i = 1; i <= n;i++){ for (int j = 1; j <= n;j++){ imap[i][j] += imap[i - 1][j] + imap[i][j - 1] - imap[i - 1][j - 1]; } } int sx, sy, ex, ey; while(q--){ cin >> sx >> sy >> ex >> ey; cout << imap[ex][ey] - imap[sx - 1][ey] - imap[ex][sy - 1] + imap[sx - 1][sy - 1] << '\n'; } uwu } ``` ---- ## 反過來呢? (差分) 反過來的問題: 給你一個正整數陣列 $A : A_1, A_2, \dots, A_N$，一開始 $\forall A_i = 0$，接著做 $Q$ 筆操作 $(l, r, x)$，把 $i = l, l + 1, \dots ,r$ , $A_i := A_i +x$，最後要求輸出操作後的 $A$。 暴力?  $O(NQ)$ 又大爆炸 ---- ### 優化? 考慮維護$\text{diff}_i = A_i - A_{i - 1}$ 每次修改只會改到兩個人! 而$\text{diff}$的前綴和就是$A$ ---- ### 看code ```cpp= [1-24|14-18|19-22] #include <bits/stdc++.h> #define uwu return 0; using namespace std; const int SIZE = 2e5 + 5; int N, Q; int detla[SIZE]; int main(){ cin >> N >> Q; for(int l, r, x; Q--;){ cin >> l >> r >> x; delta[l] += x; delta[r + 1] -= x; } for(int i = 1; i <= N; i++){ delta[i] += delta[i - 1]; cout << delta[i] << ' '; } uwu } ``` ---- ### 再多變化? - 二維差分 - 高維前綴和 & 高維差分 (SOS dp & mobius，以後的事) - 區間操作轉單點操作 - 前綴積 & 有好的反元素的東東 - 搭配後綴 ---- ## 例題 - 基礎題 - ABC 333 E - ARC 059 B - AGC 023 A - CSES - Subarray Sum I & II - CSES - Range Xor Queries - TIOJ 2063 (練實作) - TIOJ 2305 ---- ## 例題 - 思考題 - ABC 255 E - ABC 143 F (天才題) - AGC 008 B - AGC 015 C (要對圖論有一點基本知識) --- # 二分搜 ---- ## 真的有人想玩金庫密碼嗎? 隨便點兩個看起來很電的人來玩 ---- ## 原理是什麼? 你知道某個人不是答案，你就知道他之後/之前的不是答案! 找一個有**單調性**的東西時很好用的方法 ---- ### 啥鬼二分搜能解決的是: 有一個函數$f(x)$滿足$\forall x_1 \ge x_2，f(x_1) \ge f(x_2)$，問$f(x) = a$的解或$f(x) \le a$的最大$x$，$f(x) \ge a$的最小$x$ ---- ### 更聽不懂了我們在做啥? 知道答案在$[l, r]$，設$m = \frac {l + r} 2$ 檢查答案在$m$的左邊還右邊答案的可能區間就變一半了實作? ---- ### 還記得STL? [`sort()`](https://en.cppreference.com/w/cpp/algorithm/sort),[`lower_bound()`](https://cplusplus.com/reference/algorithm/lower_bound/), [`upper_bound()`](https://cplusplus.com/reference/algorithm/upper_bound/) 對於set或multiset記得用`st.lower_bound()` 練練看: [Codeforces Edu. - Binary Search Step 1](https://codeforces.com/edu/course/2/lesson/6/1/practice) 喔然後叫餘切教你們 ranges ---- ### 自己寫? 我通常是左閉右閉，也就是答案可能的範圍在$[L,R]$，所以你就要判斷你現在是什麼狀況視情況+/-1 ```cpp= int L = 0, R = MAX, M; while(L < R){ M = (L + R) / 2; //注意是向0取整，所以要換成 L = M 的要變 M = (L + R + 1) / 2 if(eval(M)) R = M; //or L = M; else L = M + 1;//or R = M - 1; } ans = L; ``` 注意的是有負數的話`/2`要改`>>=1`，因為後者是向下取整，前者是向 0 ---- ### 跳躍式? ```cpp= int pos = 0, jump = (1 << (__lg(MAX) + 1)); while(jump){ while(eval(pos + jump)){ pos += jump; } jump >>= 1; } ans = pos; ``` 主要是少維護一點東西跟結構很漂亮，但我其實不常寫。 ---- ### 實數上? ```cpp= int t = RUN_TIME; double L = 0, R = MAX, M; while(t--){ M = (L + R) / 2; if(eval(M)) L = M; // R = M else R = M; // L = M } ans = L ``` RUN_TIME用$\log(\varepsilon^{-1} C)$估，反正50高機率夠，你真的怕就用100 ---- ### 複雜度? 二分搜每次都會把值域縮小一半，因此在要求精度為$\varepsilon$(通常是1，也就是對整數去搜的時候)，值域為$C$，判斷答案在前還是後的時間是$O(eval)$的狀況下，因為 eval $\log(\varepsilon^{-1} C)$次就可達到要求精度，因此總時間複雜度為$O(eval \times \log(\varepsilon^{-1} C))$ ---- ## 對答案二分搜二分搜還可以搜答呦(sodayo~) 很常題目都有那種所謂找出最大的OO或最小的OO，而且答案可不可行也有單調性，就可以對答案二分搜。 ---- ### 上例題? [Codeforces Edu. - Binary Search Step 2](https://codeforces.com/edu/course/2/lesson/6/2/practice) [Codeforces Edu. - Binary Search Step 3](https://codeforces.com/edu/course/2/lesson/6/3/practice) 有些東西還沒教跟有些實作有點煩 ---- ### Step 2 pB 首先你會發現答案跟切的段數的關係，接著觀察到有單調性，因此就可以做對答案二分搜! ---- ### Code ```cpp= [1-44|34-40|13-19] #include <bits/stdc++.h> #define uwu return 0; using namespace std; const int RUN_TIME = 50; const double MAX = 1e7; int n, k; vector<int> vec; bool eval(double db){ int cnt = 0; for(auto i:vec){ cnt += floor(i / db); } return cnt >= k; } int main(){ cin >> n >> k; int a; while(n--){ cin >> a; vec.push_back(a); } int T = RUN_TIME; double L = 0, R = MAX, M; while(T--){ M = (L + R) / 2; if(eval(M)) L = M; else R = M; } cout << setprecision(9) << L << '\n'; uwu } ``` ---- ## 找峰假設我們知道在值域內有一個單峰函數，且這個單峰函數峰前遞增峰後遞減，那我們要怎麼找這個峰呢? 痾你可能會微分，但我不會。 ---- ### 二分搜? 你可能會想到可以對差分做二分搜，或著是你可以做三分搜。前者應該比較簡單，所以我著重在後者。 ---- 基本作法就是改成每次戳兩個點，這樣值域可以縮小三分之一，為什麼請看下面 ![image](https://hackmd.io/_uploads/Hyd8x13t6.png) ---- ### 好欸看code ```cpp! int L = 0, R = MAX, M1, M2; while(L < R){ M1 = L + (R - L) / 3; M2 = R - (R - L) / 3; if(eval(M1) < eval(M2)) R = M2 - 1; else L = M1 + 1; //因為現在 eval M1 大於等於 eval M2，所以一定不是低谷，所以可以+1確保可以縮到一個點 } ``` ---- ### 例題? 你可以寫寫看step 2 pC 或著是 ||闖關p2|| ---- ### long tree 比一比好好分析分析可以發現一件事，三種方法雖然都號稱(真的是啦)是$eval \times \log C$，但他們常數還是有差的，分別是: $\log C$ (一階微分) $< 2 \log C$ (一項的差分) $< 2\times \log_{1.5} 2\times \log C$ (三分搜)，可以發現三分搜常數真的最爛的。但你在互動題上可以黃金比例搜，就不會輸了 ---- ## 分數規劃每個數字有兩個權重 $a_i, b_i$，教你在 $N$ 個數字內取 $k$ 個數字使得他們的 $\frac {\sum a_i} {\sum b_i}$ 最大或最小，e.g. 最大平均或最大費瑞和 ---- ### 為啥不能亂拿一通例如一直取 $\frac a b$ 最大的，但這個是爛的，隨便看一個例子就知道: $\frac {48763} {1}, \frac {1} {2}, \frac {7} {8}$ 選兩個，貪心取的話會選$\frac {48763 + 7} {1 + 8} \approx 5419$，但其實最後的答案是$\frac {48763 + 1} {1 + 2} \approx 16255$，所以貪心很爛QAQ ---- ### 怎解? 我們把問題變成 $\frac {\sum a_i} {\sum b_i} \ge x$ 可不可行，二分搜最大的 $x$，但要怎麼判斷呢? 移項! 把 $\frac {\sum a_i} {\sum b_i} \ge x$ 移項，得到 ${\sum a_i} \ge x \times {\sum b_i}$ ，減過去就是 ${\sum (a_i - x \times b_i)} \ge 0$ ，因此你先把 ${\sum (a_i - x \times b_i)}$ 最大的 $k$ 項選出來再看有沒有大於 0 就好了!! ---- ## 上例題 [Codeforces Edu. - Binary Search Step 4](https://codeforces.com/edu/course/2/lesson/6/4/practice) ---- ## 尋找第 k 大值痾就跟上面差不多 [Codeforces Edu. - Binary Search Step 5](https://codeforces.com/edu/course/2/lesson/6/5/practice) ---- ## 偷懶很多可以貪心或數學 $O(1)$ 或 $O(N)$ 這一類算出來的題目，真的好難想QAQ，但多帶一個 $\log C$ 通常不會被卡，所以可以體會到二分搜的妙用。 ---- ## 搜毒有很多個東西裡面有一個是爛掉的，並且讓你詢問一個區間內是否有爛掉的，請你找到爛掉的那一個是誰，這時對答案二分搜就會是一個很好的選擇。 ---- ### Hamming Code 但如果今天他要求你先把你要檢查的組別先分好的話，那又該怎麼辦呢? Hamming Code 的作法是把二進制下第$i$位是1的分在一組，這樣一樣可以在$\lceil logn \rceil$次詢問內找到有問題的位置，而且在正常的組別編號下，把有問題的組別當成1寫成二進位制寫出來的數字就會是有問題的位置! ---- ## 例題 - 基本題(一) - ABC 248 D - ABC 337 E - ABC 339 C - ABC 341 D - ABC 364 D - Atcoder Typical 90 - 001 - CF 1927 D ---- ## 例題 - 基本題(二) - CSES Array Division - CSES Factory Machine - TIOJ 1044 - TIOJ 1208 (pbds教了吧) - TIOJ 1945 - TIOJ 2240 (我想看到有人跟我一樣被卡精度) ---- ## 例題 - 思考題 - ABC 107 D (神題) - ABC 236 E (要會一點dp) - ARC 179 C (痾學實作法) - AGC 006 D (天才題) - CF 1491 F (天才題) - TIOJ 1337 - TIOJ 1406 - TIOJ 1597 (要會最短路，會卡常) ---- ## 例題 - 偷看別人的blog [超多好題的blog](https://yozen0405.github.io/wiki/search/binary_search/) ---- ## 例題 - CF Edu. Binary Search 刷了可能可以讓你成為下一屆的基礎演算法講師，因為這樣就不用再找例題了 --- # 雙指針 & 單調的東東 ---- ## 雙指針? 雙指針顧名思義就是兩個指針(好像廢話)，這兩根指針可以是在樹上，序列上， Linked List 上，函數上等。根據不同性質與需求可以創造出許多不一樣的用法，下面舉例一些常見的用法，名字大部分是我自己亂取的。 ---- ### 先講簡單的先講在這的 [CF edu. Two Pointers](https://codeforces.com/edu/course/2/lesson/9) 有些怪trick，我很喜歡 ---- ### 經典題給定兩個由小到大排序好的陣列，長度分別為 $n,m$，請你在 $O(n+m)$ 內把他合併成一個排序好的陣列。 ---- ### 怎解? 在兩個陣列的開頭各放置一個指針，每次比較哪一個指針指的數較小，將該指針指的數放入陣列並向後移動，因為兩個指針分別移動了 $n$ 次與 $m$ 次，因此可以在 $O(n+m)$ 內把他合併成一個排序好的陣列。 ---- ### 看code ```cpp= vector<int> merge_sorted_vector(vector<int> v1, vector<int> v2){ int p1 = 0, p2 = 0; vector<int> ret; while(p1 < v1.size() || p2 < v2.size()){ if(p2 == v2.size() || (p1 < v1.size() && v1[p1] < v2[p2])) ret.push_back(v1[p1++]); else ret.push_back(v2[p2++]); } return ret; } ``` ---- ### 為啥? 這個做法的前提是因為他已經是排序好的陣列了，因此若現在這一格比對方的指針指的還大，那後面的也都會比較大，因此不會發生逆續的狀況。 [驗code 裸題 - CF edu. Two Pointers step 1 pA](https://codeforces.com/edu/course/2/lesson/9/1/practice/contest/307092/problem/A) ---- ### 上例題 [CF edu. Two Pointers step 1](https://codeforces.com/edu/course/2/lesson/9/1/practice) 全部都是這個類型的 ---- ## 一定要兩個陣列嗎? 痾不一定，而且也不一定要同向出發，可以看 [CF edu. Two Pointers step 2](https://codeforces.com/edu/course/2/lesson/9/2/practice), [CF edu. Two Pointers step 3](https://codeforces.com/edu/course/2/lesson/9/3) ---- ### 同向出發通常這種問題會是 "最長" 或 "最短" 的具有某種性質的區間長度 / 滿足該性質的區間數量，利用一旦某個長度符合這個性質，哪麼包含他的區間 / 被他包含的區間一定也符合這種性質。 ---- ### 看例題 [CF edu. Two Pointers step 2 pA](https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/A) 給你一個皆為正整數的陣列，要你找到長度最長，和不超過給定值的區間長度。 ---- ### 怎解? 前綴和+二分搜?  $O(N\log N)$ 會過但不是最好 ---- ### 觀察一下對於每個給定左界，他最好的右界是遞增的，也就是說我們可以用兩個指針代表左右界，對於每次將左指針向右移一格時，右指針就一路往右走走到和超過給定值為止，兩個指針都各移動 $N$ 的距離，時間複雜度為 $O(N)$ ---- #### 看code ```cpp= [1-35|19-21|23-30] #include <bits/stdc++.h> #define uwu return 0; using namespace std; const int SIZE = 1e5 + 5; int n; long long s; long long a[SIZE], pre[SIZE]; int main(){ cin >> n >> s; for (int i = 1; i <= n;i++){ cin >> a[i]; } for (int i = 1; i <= n;i++){ pre[i] = pre[i - 1] + a[i]; } int posl = 0, posr = 0, ans = 0; while(posr != n){ posr++; while(pre[posr] - pre[posl] > s){ posl++; } ans = max(posr - posl, ans); } cout << ans << '\n'; uwu } ``` ---- ### 反向出發通常這種問題會是要求找到一組滿足條件的數對或著問滿足條件的數對數量，而通常是利用在某個左界前面的都不用考慮或著在某個右界後都不用考慮這類的性質去做。我不知道為啥 CF edu. Two Pointers 一題這種都沒有。 ---- ### 看例題 [CSES - Sum of Two Values](https://cses.fi/problemset/task/1640/) 首先考慮 sort 過的狀況，那麼對於一個給定左界，我們可以二分搜另一個值，總時間複雜度 $O(N\log N)$ 但注意到左界遞增的話另一個值的位置遞減，那其實可以用雙指針維護欸，時間複雜度變 $O(N)$。 ---- ### 看 code ```cpp= [1-35|24-33] #include <bits/stdc++.h> #define uwu return 0; using namespace std; #define fs first #define sc second int main(){ int n, x, a; cin >> n >> x; vector<pair<int, int>> vec; for (int i = 1; i <= n;i++){ cin >> a; vec.push_back({a, i}); } sort(vec.begin(), vec.end()); int posl = 0, posr = n - 1; while(posl < posr){ while(vec[posl].fs + vec[posr].fs > x) posr--; if(posl > posr) break; if(vec[posl].fs + vec[posr].fs == x){ cout << vec[posl].sc << ' ' << vec[posr].sc << '\n'; uwu } posl++; } cout << "IMPOSSIBLE\n"; } ``` ---- ### 我在唬爛嗎當然一開始有 sort ，所以總時間複雜度還是 $O(N\log N)$ ，而拿 unordered_map 則可以有會更慢的 $O(N)$ (因為 unordered_map 很爛)，但是你可以拿一樣的技巧去做[CSES - Sum of Three Values](https://cses.fi/problemset/task/1641/)，這題用unordered_map $O(N^2)$ 會被卡常，但用雙指針也可以做 $O(N^2)$ 而且會過。 ---- ### 怪 trick - 多個陣列壓到一個 - two stack queue (cot 很堅持他要叫 Slide Window Aggrigation) - 龜兔 (這個可能沒有很怪，只是現在應該還沒什麼用) - :arrow_up: 講義都有寫，我有空再講 ---- ## Sliding Window Sliding Window 其實就是雙指針，因此我其實不太知道他被獨立出一個名詞的意義在哪 ---- ## 單調OO 在你做 Sliding Window 的時候，你可能會發現一些資訊是你完全用不到的，這個時候就用單調OO。 ---- ### 經典題 [TIOJ 1176](https://tioj.ck.tp.edu.tw/problems/1176) - Cows 題敘寫的不是很好懂，但意思大概是要你找右邊第一個比他大的離他多遠 ---- ### 觀察一下如果存在一個 $l < r$ 且符合 $a_l > a_r$，則不但 $l$ 的答案不會是 $r$ ，對於所有的 $l' < l$ ，這些 $l'$ 的答案也不會是 $r$ 。因此每個人都可以把他前面比他小的人幹掉，每個人都會進去stack一次，被幹掉最多一次，所以總共花的時間是$O(N)$。 ---- ### 看 code ```cpp= [1-41|26-34] #include <bits/stdc++.h> #define uwu return 0; using namespace std; #define fs first #define sc second const int SIZE = 1e6 + 5; int h[SIZE], ans[SIZE]; int main(){ int N; cin >> N; for (int i = 0; i < N; i++){ cin >> h[i]; } stack<pair<int, int>> monotonic_stack; monotonic_stack.push({INT32_MAX, N - 1}); for (int i = N - 1; i >= 0;i--){ while(monotonic_stack.top().fs < h[i]){ monotonic_stack.pop(); } ans[i] = monotonic_stack.top().sc - i; monotonic_stack.push({h[i], i}); } for (int i = 0; i < N;i++){ cout << ans[i] << '\n'; } uwu } ``` ---- ## 離線區間最值對於固定右界的區間最值問題我們可以用單調對列解決，再用二分搜救可以在單調對列上找到要的值了，複雜度$O(N + Q \log N)$。到離線技巧時我會再講 ---- ### 找出 $x$ 為最值的區間這可能是很多思考題的梗對於每個人，他前面那個人跟把他 pop 掉的人圍起來的區間就是他是最值的區間了欸! 痾我有時間應該會挑一題來講 ---- ## 例題 - 基本題 - ABC 352 D - ABC 354 C - ABC 359 E - CSES - Nearest Smaller Value - CSES - Sum of Three Values - TIOJ 1368 - TIOJ 1618 ---- ## 例題 - 思考題(一) - ABC 134 E - ABC 341 G (要有一點||數型結合||的概念) - ARC 067 F (我會一直推這一題給你，至少還會再看到三次，在||分治||，||線段樹||, ||dp優化||) - ARC 072 F (天才題) - ARC 062 D (大好題) ---- ## 例題 - 思考題(二) - AGC 005 B (這裡最簡單的一題) - Atcode Typical 90 - 089 (思考好題，難度偏高，要會算逆序數對跟dp的概念) - CSES - Static Range Minimum Queries (講離線時我會再講) - TIOJ 1225 ---- ## 例題 - 偷看別人的blog [超多好題的blog](https://yozen0405.github.io/wiki/search/two_pointer/) ---- ## 例題 - CF Edu. Two Pointer 刷了可能可以讓你成為下一屆的基礎演算法講師，因為這樣就不用再找例題了 --- # 分治 (我好愛分治喔) ---- ## 分治是啥分治就是把一個問題換成很多小問題的組合，再用很好的複雜度合併這裡應該是我會講的最開心的，我太嗨記得提醒我 ---- ### 經典的例子 - Merge Sort 基本上最經典的$O(N\log N)$的 sort 就是 Merge Sort，Merge Sort 的精隨在我們可以用$O(N)$將兩個已經排序好的 array 合併，因此我們每次進行以下操作: 1. 將現在這個 array 分成兩個 array 2. 將兩個 array 分別排序 3. 將兩個排序好的 array 合併 ---- ### 看 code ```cpp= [1-25|5-8|2-3|14-19] void merge_sort(int L, int R){ if(L == R) return; int M = (L + R) / 2; merge_sort(L, M); merge_sort(M + 1, R); int posl = L, posr = M + 1; vector<int> tmp; while(posl <= M || posr <= R){ if(posl > M || (posr <= R && arr[posl] >= arr[posr])) tmp.push_back(arr[posr++]); else tmp.push_back(arr[posl++]); } for (int i = 0; i <= R - L;i++){ arr[i + L] = tmp[i]; } return; } ``` ---- ### 複雜度? 注意到最多遞迴$\log N$層(因為每次長度變一半)，每一層加起來總共操作到 $N$ 個人，所以是$O(N \log N)$ ---- ### 好難想? 為了方便我們估複雜度，我們可以用主定理。 :::danger Master Theorem: 對於一個未知複雜度$T(n)$ $T(n) = aT(\lceil \frac n b \rceil ) + O(n^d)$ 則$T(n) = \begin{cases} O(n^d), \ \text{for} \ d > \log_b(a) \\ O(n^d\log n), \ \text{for} \ d = \log_b(a) \\ O(n^{\log_b(a)}), \ \text{for} \ d < \log_b(a) \end{cases}$ ::: ---- ### 痾不是萬能 [這裡有一篇證明](https://www.cs.cornell.edu/courses/cs3110/2012sp/lectures/lec20-master/mm-proof.pdf) 有興趣自己看然後有一個更推廣的定理叫做[Akra-Bazzi method](https://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method)，可以更好的解釋後面加的有帶 log 的，但一般我們都當常數提出來再直接乘上去，反正一定比較小。 ---- ### 舉個堅果 #### 二分搜 $T(N) = T(\frac N 2) + O(1)$ 主定理告訴我們是$O(\log N)$ #### Merge Sort $T(N) = 2T(\frac N 2) + O(N)$ 主定理告訴我們是$O(N\log N)$ ---- ### 只有這樣? 痾分治真的很厲害，我可能到現在都還不是很熟，所以來看例題! ---- ### [ABC 293 E](https://atcoder.jp/contests/abc293/tasks/abc293_e) - 模D底下等比級數直接用等比級數公式的話 $\sum_{i=0}^{X-1} A^i = \frac {A^x - 1} {A - 1}$，在$A-1$對$M$有模逆元時可以用擴展歐幾里得用 $O(\log N)$求得。但沒有模逆元時怎麼辦? ---- ### 稍作觀察可以發現$A^0+A^1+A^2+\dots+A^{X-1}$ 1. 在 $X = 1$ 的時候很好處理 2. 在 $X$ 是奇數時，可以拆成 $(1+A^{\frac X 2})(A^0+A^1+A^2+\dots+A^{\frac X 2 - 1})$ 3. 在 $X$ 是偶數時，可以拆成 $1 + A(A^0+A^1+A^2+\dots+A^{X - 2})$ 因此我們只要能很快地算出$A^n$就可以了，而有一個很棒的東西叫做快速冪 ---- ### 快速冪他是一種很巨的 pow，叫做 gpow 在計算$A ^ n$時我們一樣可以用分治思想 1. 當$n = 1$時很好處理 2. 當$n$是偶數時，$A ^ n = A^{n \over 2} \times A^{n \over 2}$ 3. 當$n$是奇數時，$A ^ n = A^{{n - 1} \over 2} \times A^{{n - 1} \over 2} \times A$ 因此我們可以直接遞迴下去計算，套用主定理可以知道: $T(n) = T(\frac n 2) + O(1)$，總時間複雜度$O(\log n)$ ---- ### 看code ```cpp= [1-14|] long long quick_pow(long long base, long long pw){ if(pw == 0) return 1 % M; if(pw == 1) return base % M; long long ret = quick_pow(base, pw / 2); ret *= ret; ret %= M; if(pw & 1){ ret *= base; ret %= M; } return ret; } ``` ---- ### 迭代式一般快速冪是把次方換成二進制，將是$1$的位數代表的二的次方乘起來，例如: $42_{10} = 101010_{2}$，所以$A^{42} = A^{32} \times A^{8} \times A^{2}$ 用迭代式來實作: ```cpp= long long quick_pow(long long base, long long pw){ long long ret = 1; while(pw){ if(pw & 1){ ret *= base; ret %= M; } base *= base; base %= M; pw >>= 1; } return ret; } ``` ---- ### 回到題目你現在可以$O(\log n)$的時間算完$A^n$，因此你可以在$O(\log^2 n)$的時間內做完。下面是範例code :::spoiler AC code ```cpp= #include <bits/stdc++.h> #define uwu return 0; using namespace std; long long A, X, M; long long quick_pow(long long base, long long pw){ long long ret = 1; while(pw){ if(pw & 1){ ret *= base; ret %= M; } base *= base; base %= M; pw >>= 1; } return ret; } long long solve(long long pw){ if(pw == 1) return 1 % M; if(pw & 1) return (1 + ((A + quick_pow(A, (pw + 1) / 2)) % M) * solve(pw / 2)) % M; return (((1 + quick_pow(A, pw / 2)) % M) * solve(pw / 2)) % M; } int main(){ cin >> A >> X >> M; cout << solve(X) << '\n'; } ``` ::: ---- ### 有必要嗎可以注意到遞迴式的快速冪跟 solve 根本在做一模一樣的事，因此只要把他一起遞迴做就好了。 :::spoiler 一個log AC code ```cpp= #include <bits/stdc++.h> #define uwu return 0; using namespace std; long long A, X, M; #define fs first #define sc second pair<long long, long long> solve(long long pw){ if(pw == 1) return {1 % M, A % M}; pair<long long, long long> ret = solve(pw / 2); if(pw & 1) return {(1 + ((A + ret.sc * A) % M) * ret.fs) % M, (((ret.sc * ret.sc) % M) * A) % M}; return {(((1 + ret.sc) % M) * ret.fs) % M, ((ret.sc * ret.sc) % M)}; } int main(){ cin >> A >> X >> M; cout << solve(X).fs << '\n'; } ``` ::: 時間複雜度$O(\log n)$ ---- ### [TIOJ 1080](https://tioj.ck.tp.edu.tw/problems/1080) - 逆序數對逆序數對算是非常經典的問題，一般常見的作法有三個(BIT + 離散化、分治、pbds)，~~建議三個都寫寫看才能體會pbds的好~~ ---- ### 小小觀察兩塊都已經排序好的陣列接在一起，我們可以$O(n)$算。也可以排序。詳細的步驟是: 1. 將現在這個 array 分成兩個 array 2. 將兩個 array 分別排序並算出個別逆序數對數 3. 將兩個排序好的 array 合併並算出這兩個 array 造成的逆序數對數主定理$T(n) = 2T(\frac n 2) + O(n)$，總時間複雜度也是$O(n\log n)$ ---- ### 看code ```cpp= [1-46|16|11-12|20-27] #include <bits/stdc++.h> #define uwu return 0; using namespace std; const int SIZE = 1e5 + 5; int arr[SIZE]; long long solve(int L, int R){ if(L == R) return 0; int M = (L + R) / 2; long long posl = L, posr = M + 1, cnt = solve(L, M) + solve(M + 1, R); vector<int> tmp; while(posl <= M || posr <= R){ if(posl > M || (posr <= R && arr[posl] > arr[posr])) tmp.push_back(arr[posr++]); else{ tmp.push_back(arr[posl++]); cnt += posr - (M + 1); } } for (int i = 0; i <= R - L;i++){ arr[i + L] = tmp[i]; } return cnt; } int main(){ cin.tie(0), ios::sync_with_stdio(0); int n, T = 0; while(cin >> n && n){ for (int i = 1; i <= n;i++){ cin >> arr[i]; } T++; cout << "Case #" << T << ": " << solve(1, n) << '\n'; } uwu } ``` ---- ## 還有啥 - 平面最近點對 - 按位分治 - 分的位置不固定的分治 - 高維問題 - 最佳位置單調的分(治) - 利用前/後綴 min/max 的單調性 :arrow_up: 的東西有點多，而且不簡單我講義有放，有空再講重點是分治是拿來簡化事情的好方法 ---- ## 倒過來做? 還有一個東西叫做倍增，我自己覺得是分治換個方法做而已。例如 : [TOJ 510](https://toj.tfcis.org/oj/pro/510/) 對於每一個位置去維護他被洗 $2^i$ 次的結果，那們我們可以用$O(N \log K)$ 的時間獲得這個表格，再花$O(\log K)$就可以組出答案了! ---- ### 看code ```cpp= [1-46|24-28|32-38] #include <bits/stdc++.h> #define uwu return 0; using namespace std; const int SIZE = 3e5 + 5, LOG_K = 62; int N; long long pos[LOG_K][SIZE], card_to_pos[SIZE], last_pos[SIZE], ans[SIZE]; long long K; int main(){ cin >> N; for (int i = 1, a; i <= N; i++){ cin >> a; card_to_pos[a] = i; } for (int i = 1, a; i <= N; i++){ cin >> pos[0][i]; } cin >> K; for (int i = 1; i < LOG_K; i++){ for (int j = 1; j <= N; j++){ pos[i][j] = pos[i - 1][pos[i - 1][j]]; } } for (int i = 1; i <= N; i++){ last_pos[i] = i; } for (int i = 0; i < LOG_K; i++){ if(K & (1LL << i)){ for (int j = 1; j <= N; j++){ last_pos[j] = pos[i][last_pos[j]]; } } } for (int i = 1; i <= N; i++){ ans[last_pos[card_to_pos[i]]] = i; } for (int i = 1; i <= N; i++){ cout << ans[i] << ' '; } uwu } ``` 很多分治題也可用倍增做喔 ---- ## 例題 - 基本題 - ABC 179 E (倍增的，沒放code，可以去atcoder上偷看) - ABC 241 E (倍增的，沒放code，可以去atcoder上偷看) - ABC 247 E - ABC 350 F - ABC 351 F - CF 1311 F - CSES - Exponentiation - NEOJ 789 ---- ## 例題 - 有時間一定會講題 - TIOJ 1500 - ABC 281 F - CF 1400 E - 2012 CERC D - TIOJ 1918 - NEOJ 127 - NEOJ 788 ---- ## 例題 - 思考題(一) - ABC 248 Ex. (我有時間講就會變經典題) - ABC 282 Ex. (跟上面那題一樣) - ARC 063 F (銀牌題，實作量微大) - AGC 031 C (要怎麼這麼會構造阿) - AGC 044 D (實作題) - Atcoder Dwango V pB (痾比較簡單的) - CF 102920 L (很值得想而且是想的到的神題) ---- ## 例題 - 思考題(二) - CF 888 G (不簡單) - OJDL 7162 (備課陳在我備課時影響我啦) - NTUCPC OJ 183 (痾對，他只有分治跟stl) - TIOJ 1283 (痾反正到dp優化的時候還是會講) - TIOJ 2027 (要會 trie) - ZJ c260 (痾數學題) - ZJ i341 (becaido 出來負責) ---- ## 例題 - 有人在唬爛題 - ABC 348 G (我在唬爛) - ARC 067 F (我在唬爛) - CF 1976 F (我在唬爛) - TIOJ 1064 (cotorz 在唬爛) - TIOJ 1175 (這題是從 pixelcat orz 寫的分治講義上的，我個人覺得~~聽他在唬爛~~) ---- ## vir OI 暴雷區 :::spoiler Baltic OI BOI 2017 Toll BOI 2020 Joker ::: :::spoiler JOISC JOISC 2019 Minerals ::: :::spoiler 江蘇OI JSOI 15 最大公约数 ::: --- # 雜湊 (沒人想當負責人叫我這種雜魚出來湊) ---- ## Hash 是啥 ![image](https://hackmd.io/_uploads/BkWeSwCq6.png =400x) Hash 是毒  ---- ### 認真講把一個大東西 (任何東西，可能是一條邊，一個字串，一個大數甚至是一棵樹) 變成一個小東西(通常是一個long long 或一段序列)，因為小東西比較好比較或性質比較好，所以就很讚。 ---- ### 舉個杏仁 [ABC 339 F](https://atcoder.jp/contests/abc339/tasks/abc339_f) 問題 : 大數很難乘法與比較 ---- ### 怎解? 變比較不owoovo的數因此你就想，我現在只要求兩個好性質，一個是可以比較，一個是可以乘法，因此你的要求就是一個函式 $f(S)$ 滿足 : 1. $S_1 = S_2 \implies f(S_1) = f(S_2)$ 2. $S_1 \times S_2 = S_3 \implies g(f(S_1),f(S_2)) = f(S_3)$ ($g$是一個好的函數) 對大質數取模! :::spoiler AC code ```cpp!= #include <bits/stdc++.h> #define uwu return 0; using namespace std; const __int128 MOD = (1LL << 56) - 55, SIZE = 1e3 + 5; unsigned long long pow_mod[SIZE]; void init(){ pow_mod[0] = 1; for (int i = 1; i < SIZE;i++){ pow_mod[i] = (pow_mod[i - 1] * 10) % MOD; } return; } __int128 str_to_ll(string str){ reverse(str.begin(), str.end()); __int128 ret = 0; for (int i = 0; i < str.size();i++){ ret += (str[i] - '0') * pow_mod[i]; ret %= MOD; } return ret; } int N; vector<__int128> num; unordered_map<__int128, long long> umap; string in_s; int main(){ init(); cin >> N; for (int i = 0; i < N;i++){ cin >> in_s; num.push_back(str_to_ll(in_s)); umap[num.back()]++; } long long ans = 0; for (int i = 0; i < N;i++){ for (int j = 0; j < N;j++){ ans += umap[(num[i] * num[j]) % MOD]; } } cout << ans << '\n'; uwu } ``` ::: ---- ### 還能幹嘛? 快速比對! 壓縮狀態! 這些都是一些比較一開始用不太到的了，只要稍微有點概念以後會常用到的。 ---- ## 例題 - 混在一起應該都算思考題? - ABC 238 G - ABC 295 D - CSES - Special Substring - NEOJ 793 - OJDL 7212 - TIOJ 1321 - TIOJ 1891 --- ## 大家明天魔鏡加油 ![image](https://hackmd.io/_uploads/rytpophuC.png =300x)