那些可愛的根號算法>w<

--- title: 那些可愛的根號算法>w< tags: MDOI image: https://i.imgur.com/SyxOqpN.jpg slideOptions: theme: solarized transition: 'slide' slide: data-background="https://i.imgur.com/SyxOqpN.jpg" --- <style> body{ background-attachment: fixed; background-repeat: no-repeat; background: -webkit-linear-gradient(left, #ffffff,rgba(51,51,51,0.3)), url("https://i.imgur.com/SyxOqpN.jpg") center no-repeat fixed; }; </style>  那些可愛的根號算法>w< 作者: iceylemon ---- 根號算法 1. 找質數/因數 2. 數論分塊 3. 大小分塊 4. 序列分塊 5. 詢問分塊(定期重構) 6. 莫隊算法 7. 其他怪怪的東西 --- 大小分塊 小於 $\sqrt{N}$ 一個做法，大於 $\sqrt{N}$ 另一個做法 ---- 分析 * 小於 $\sqrt{N}$：通常是暴力 * 大於 $\sqrt{N}$：因為大於的數會有$O(N)$個，所以轉移或操作的複雜度平均要是$O(\sqrt{N})$以下。通常圍繞著$\sqrt{N}$跑。 ---- 例題 題目：非常多，到處都是 1. ABC 219G 2. LOJ 6089 --- 序列分塊 俗稱優雅的暴力，把一個序列分成若干塊處理 ---- 例題 給定一個陣列$A$，支援以下操作： 1. 區間加值 2. 區間查詢 ---- 分塊先備條件 1. **大段維護，局部暴力** 2. 局部暴力通常不成問題難在如何維護整塊的資訊 3. 除了維護單一塊內資訊，如何合併答案也很重要 ---- 慣用手法 1. 首先先把陣列分成若干塊，每塊大小為 $B$，不足的就讓它不足 2. (可選) 標記每一個位置是屬於哪一塊，通常 0-base 我們會使用 $\frac{i}{B}$ 來作為塊編號(向下取整) 3. 對於一個區間 $[L,R]$，最多會包含到兩個不完整的塊(左右)，局部處理這兩塊，剩下的用打tag的方式維護 4. 處理答案的合併 ---- 例題講解 1. 區間修改：不完整的塊一個一個修改，完整的塊打一個tag: 塊內元素*val 2. 區間查詢：同上，修改改成相加即可 ---- 複雜度 1. 不完整的塊一個一個修改：$O(2B)=O(B)$ 2. 完整的塊打一個tag: $O(N/B)$ 總複雜度：$O(Q(B+N/B))$，由算幾不等式可知取 $B=\sqrt{N}$最優，整體複雜度$O(Q\sqrt N)$ ---- 分塊可以做什麼 * 很多的區間問題，只要可以打tag維護通常都可 * 可以在塊內做二分搜，甚至可以塞資料結構 * 複雜度通常不好分析，但理論上他是好的 * 分塊本人就是一個**資料結構**，資料結構可以做的他都可以做 ex: DP 優化 ---- 值域分塊 值域分塊是一種資料結構 ---- 值域分塊 值域分塊是一種資料結構跟值域線段樹很像，就是對值域進行分塊每塊分別統整該塊的答案 ---- 題目? 他不太常出現，因為值域線段樹可以蓋掉大部分的CASE 但值域分塊還是有一些好用的地方：單點修很快有些題目用是要用值域分塊才可以過的 ---- 回家作業 1. hzwer 的分塊 9 講 LOJ 6277~6285 --- 詢問分塊 又叫定期重構。適用於有修改也有查詢的題目。顧名思義將詢問進行分塊，當處理完整個塊所有的詢問時，將你的陣列一次加上那些修改操作。在塊內時暴力查詢不修改。 ---- 詢問分塊 又叫定期重構。適用於有修改也有查詢的題目。顧名思義將詢問進行分塊，當處理完整個塊所有的詢問時，將你的陣列一次加上那些修改操作。在塊內時暴力查詢不修改。 **所以什麼是詢問分塊?** ---- 例題 給定一個陣列$A$，支援以下操作： 1. 區間加值 2. 區間查詢 ---- 例題講解 1. 每出現 $\sqrt{Q}$ 次修改操作就把 $A$ 加上那些修改重新算一遍。 2. 每次詢問最多只會有 $\sqrt{Q}$ 的未處理修改，直接暴力計算那些修改對該詢問的影響。複雜度：$O(N\sqrt{Q})$ ---- 回家作業 [[MDCPP B053]](http://mdcpp.mingdao.edu.tw/problem/B053) 大電神說都沒人解他很難過QQ --- 莫隊算法 莫隊算法是一個離線算法，可以處理一個range的區間問題。 ---- 品種 * 普通莫隊算法 * 帶修改莫隊 * 回滾莫隊 * 樹上莫隊 * 莫隊搭配bitset(?) ---- 使用時機 可以離線做當你有區間 $[L,R]$ 的答案時，可以快速算出區間 $[L,R-1],[L,R+1],[L-1,R],[L+1,R]$ 的答案 ---- 莫隊算法使用 1. 把序列分塊，塊大小 $B$ 2. 把詢問區間按照以下規則排序：左界按**所在的塊編號**排序，右界按**自己的編號**排序。 3. 用兩個指針l,r每次一格一格移動指針到下一個詢問(先移右指針再移左指針)，過程中同時維護答案 ---- ## 偽Py代碼 ```python= sort(Q) # 左界塊編號排序，右界自身編號排序 ans = 0 def add(x): # 把位置x加進去答案 def sub(x): # 把位置x從答案扣掉 l, r = 1, 0 for [L,R] in Q: while r < R: add(++ r) while r > R: sub(r --) while l > L: add(-- l) while l < L: sub(l ++) print(ans) ``` ---- 複雜度分析 1. 排序 $O(NlogN)$ 2. 當左界都在同一塊右界只會一直往右邊嚕。所以右界移動的格子數不超過 $O(N)$，而這種Case最多只會有 $O(N/B)$ 種=>$O(\frac{N^2}{B})$ 3. 左界都在同一塊內移動，所以一次最多移$O(B)$個位置，總共最多移$O(Q)$次整體複雜度$O(QB)$ 4. $O(NlogN+\frac{N^2}{B}+QB)$ 取$B=\frac{N}{\sqrt{Q}}$ ---- 題目 1. [區間眾數](https://zerojudge.tw/ShowProblem?problemid=b417) 2. [區間MEX](https://www.luogu.com.cn/problem/P4137) $O(N\sqrt{N})$ Hint: 6I6r6ZqKKyAi5YC85Z+f5YiG5aGKIiDntq3orbfmlbTloYros4foqIo= 請用base64解碼 [解碼器](http://www.mxcz.net/tools/zh-TW/base64.aspx) 3. [非常多題目](https://www.luogu.com.cn/training/2914) ---- 帶修改莫隊 可以帶修改的莫隊，我不會。大概是把**時間**這維加進去一起排序，然後做一些壞壞的事情。時間複雜度：$O(N^{5/3})$，coding 複雜度：O(玄學) ---- 回滾莫隊 可以回滾的莫隊。 ---- 回滾莫隊 可以回滾的莫隊。當你發現你只會作加法(減法)的時候就可以考慮 ---- 回滾莫隊 可以回滾的莫隊。當你發現你只會作加法(減法)的時候就可以考慮所以回滾是什麼？ ---- 名詞解釋 * 加法：把某些東西加進答案 * 減法：把某些東西從答案扣掉 * 回滾：英文叫做 rollback，就是回到之前的某一個狀態 ---- 作法 1. 一樣先做莫隊，用下面的方法改一下 2. 右界：如果左界在同一塊的話右界會遞增，所以右界只會有加法 3. 左界：因為左界永遠都在同一塊，所以不妨每一次都暴力算那一塊的答案，算完之後直接退回就好 ---- 題目 1. [區間MAX](https://zerojudge.tw/ShowProblem?problemid=d539) 2. CF EDU DSU PART3 P2 3. [區間MEX](https://www.luogu.com.cn/problem/P4137) 4. [JOISC 2014 D1 某一題](https://loj.ac/p/2874) ---- 樹上莫隊 在樹上做莫隊。但你要先會樹上分塊，請左轉選訓大電神。 ---- 假樹上莫隊 把樹壓平之後就變成序列問題了，直接莫隊 ---- 莫隊+bitset(?) 在做莫隊的時候轉移有時候可以套資料結構，就用bitset當資料結構就好了 ---- 莫隊+bitset(?) 在做莫隊的時候轉移有時候可以套資料結構，就用bitset當資料結構就好了我也沒打過，請右轉OI WIKI --- 其他怪怪的東西 根號可以出現在很多地方，偶爾就會在神奇的地方出現 1. YTP2021 pre 第8題可以暴力做(做過的詢問要記起來)，複雜度會是根號級別 2. NPSC 2019 國中組初賽 pB 是一個跟上一題一樣的題目。可以用大小分塊證明，詳見[2019資芽講義](https://www.csie.ntu.edu.tw/~sprout/algo2019/ppt_pdf/week10/root_method.pdf) 3. $K=\frac{N*(N + 1)}{2}$，$O(N)=O(\sqrt{k})$ 4. 若干個數相加為 $N$ => 最多只有 $\sqrt{N}$ 個相異數(轉有限背包問題) ----

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.