<style> .reveal .slides { text-align: left; font-size:28px; } </style> # Sqrt-Decomposition ---- - Sqrt-Decomposition on Math - Sqrt-Decomposition the Case - Sqrt-Decomposition on Sequence - Mo's Algorithm ---- ## 根號題的數值 | 複雜度 | 題目範圍 | 實際大小 | | -------- | -------- | -------- | | $\sqrt{n}$ | $10^9\sim 10^{14}$ | $3\cdot 10^4\sim 10^7$ | | $n\sqrt{n}$ | $5\cdot 10^4\sim 3\cdot10^5$ | $10^7\sim 1.6\cdot 10^8$ --- ## 數論分塊 --- [UVa11526 H(n)](https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=2521) 數論分塊可以在 $O(\sqrt{n})$ 的複雜度計算一些除法向下取整的總和的式子 $f(n)$ $f(n) = \sum_{i=1}^{n}\limits {\lfloor\frac{n}{i}\rfloor}$ 以 $n = 13$ 為例 | <center>$i$</center> | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | | ---- | - | - | - | - | - | - | - | - | - | - | - | - | - | | $\lfloor\frac{n}{i}\rfloor$ | 13 | 6 | 4 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | ---- ## 範圍 $f(n) = \sum_{i=1}^{n}\limits {\lfloor\frac{n}{i}\rfloor}$ $1\le n \le 10^{12}$，顯然不能線性跑過去計算 ---- ## 先講結論 $\forall i = 1...n$，最多只有 $2\sqrt{n}$ 種不同的 ${\lfloor\frac{n}{i}\rfloor}$ ----  可以發現當 $i\ge \sqrt{n}$ 時，$\lfloor\frac{n}{i}\rfloor$ 的值都 $\le \sqrt{n}$ ，也就是只有 $\sqrt{n}$ 種 再加上所有 $i<\sqrt{n}$ 的，可以發現 $\lfloor\frac{n}{i}\rfloor$ 只有 $\sqrt{n}$ 種 ---- 最多只有 $2\sqrt{n}$ 個不同的值，因此只需要枚舉每個數字$\times$出現的次數 總和即為答案，以 $n=13$ 為例 | <center>$i$</center> | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | | ---- | - | - | - | - | - | - | - | - | - | - | - | - | - | | $\lfloor\frac{n}{i}\rfloor$ | 13 | 6 | 4 | 3 | 2 | 2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | $\sum_{i=1}^{n}\limits {\lfloor\frac{n}{i}\rfloor} = 13\times 1+6\times 1+4\times 1+3\times 1+2\times 2+1\times7$ ---- ## 枚舉數字與出現次數 可以發現對於相同的 $\lfloor\frac{n}{i}\rfloor$ 為連續的，因此只須找到每個 $\lfloor\frac{n}{i}\rfloor$ 的區間即可 而每個 $\lfloor\frac{n}{i}\rfloor$ 的右界位置在 $\lfloor\frac{n}{\lfloor\frac{n}{i}\rfloor}\rfloor$ 以 $\lfloor\frac{13}{i}\rfloor = 2$ 為例，出現的區間在 $i=5\sim 6$ ---- ## 過程 因此我們只需從 $i = 1$ 開始，找到每個 $\lfloor\frac{n}{i}\rfloor$ 的右界計算總和， 再從下一個 $\lfloor\frac{n}{i}\rfloor$ 繼續加入答案中 ```cpp= for(long long i = 1, r; i <= n; i = r+1){ r = n / (n/i); // 右界 ans += (n/i) * (r-i+1); // (n/i) * 次數 } ``` 而最多只有 $2 \sqrt{n}$ 個不同的 $\lfloor\frac{n}{i}\rfloor$，總複雜度 $O(\sqrt{n})$ --- ## 根號題 --- 分 case 處理 類似於數論分塊，依照題目分成兩種 case 處理 $K = \sqrt{n}$，分成 - $i\le K$ - $i > K$ 兩個不同的範圍有不同的性質，根據性質分別做不同的計算 在圖論的題目中，也有許多會用到此性質分 case 處理 ---- ## 經典題 有 $n$ 個正整數 $a_1, a_2, a_3...,a_n$， 且 $a_1+a_2+a_3+...+a_n=k$ 問是否可以選一些數字 $a_i$ 總合為 $x$ $1\le n, k, x\le 2\cdot 10^5$ ---- ## 經典 DP 題 ? <span>Subset sum !<!-- .element: class="fragment" data-fragment-index="1" --></span> <span>但複雜度呢?<!-- .element: class="fragment" data-fragment-index="2" --></span> <span>n 個數字總和最大為 k<!-- .element: class="fragment" data-fragment-index="3" --></span> <span>O(nk)<!-- .element: class="fragment" data-fragment-index="4" --></span> <span>:(<!-- .element: class="fragment" data-fragment-index="4" --></span> ---- ## 實際上 把 $a_i$ 分成兩種 case: - $a_i\le \sqrt{k}$，這種 case 的 $a_i$ 種類不超過 $\sqrt{k}$ 種 - $a_i > \sqrt{k}$，這種 case 的 $a_i$ 不超過 $\sqrt{k}$ 個 ($a_1+a_2+a_3+...+a_n=k$) ---- ## $a_i\le \sqrt{k}$ 這種 case 的 $a_i$ 種類不超過 $\sqrt{k}$ 種 此種情況可以統計每個數字出現次數，去做有限背包問題 每種物品花 $O(k)$ 的時間做有限背包 $\to O(\sqrt{k}\times k\times \log{a_i})$ ---- ## $a_i> \sqrt{k}$ 由於題目限制 $a_1+a_2+a_3+...+a_n=k$ 這種 case 的 $a_i$ 不超過 $\sqrt{k}$ 個 不超過 $\sqrt{k}$ 個物品做背包問題 $\to O(\sqrt{k}\times k)$ ---- 如此一來兩種 case 的複雜度分別為 $$ \begin{cases} O(k\sqrt{k}\times\log{a_i}) & a_i\le \sqrt{k}\\ O(k\sqrt{k}) & a_i> \sqrt{k} \end{cases} $$ 而在 $a_i\le \sqrt{k}$ 的 case 複雜度比較高，因此可以把 k 設小一點 平衡一下複雜度 ---- 除此之外，$a_1+a_2+a_3+...+a_n=k$ 這種序列最多只會有 $\sqrt{k}$ 種不同的 $a_i$ $(1+2+3+...+\sqrt{k} = k$) 此性質也可以用在一些特殊的題目上 ---- ## 例題2 --- Count triangles in a graph 給一張 $n$ 個點 $m$ 條邊的簡單無向圖， 求圖上有幾個三角形 (大小為 3 的環) $1\le n, m\le 10^5$ 經典圖上分 case 題 ---- 對於每個點 $v$，找出包括在幾個三角形內 有以下兩種計算方式: - $O(m)$ 跑過所有邊，找出包括 $v$ 的三角形 - $O(d^2)$ 跑過 $v$ 的所有邊 pair，找出連接邊 pair 的第三條邊 ($d$ 為 $v$ 的 degree) 算出每個點所在三角形數量 /3 即為答案 ---- 一樣，用根號分 case 有甚麼條件可以分呢? ---- ## degree ! 對於 degree $\ge\sqrt{m}$ 的點，我們稱之為重點 $<\sqrt{m}$ 的點稱之為輕點 ---- ## 分 case 處理 - $O(m)$ 跑過所有邊，找出包括 $v$ 的三角形 degree $\ge\sqrt{m}$ 的點不超過 $\sqrt{m}$ 個 對於這些點可以用這種方法處理，複雜度 $O(m\sqrt{m})$ - $O(d^2)$ 跑過 $v$ 的所有邊 pair，找出哪些 pair 可以形成三角形 degree $<\sqrt{m}$ 的點，degree 很小可以暴力 $O(d^2)$ 計算 ---- ## 實作細節 - 對於重點，$O(m)$ 跑過所有邊，找出包括 $v$ 的三角形 可以先 $O(m)$ 跑過所有邊紀錄 $v$ 連到哪些點 接著再 $O(m)$ 跑過一次所有邊，判斷哪些邊的點兩端點 $(x, y)$ 都有被記錄到(被 $v$ 連到) ```cpp= bool vis[MXN]; for(int i : heavy){ for(int j = 0; j < m; j++){ if(edges[j].first == i) vis[edges[j].second]=1; if(edges[j].second == i) vis[edges[j].first]=1; } for(int j = 0; j < m; j++){ ans += vis[edges[j].first] && vis[edges[j].second]; } for(int j = 0; j < m; j++){ if(edges[j].first == i) vis[edges[j].second]=0; if(edges[j].second == i) vis[edges[j].first]=0; } } ``` ---- ## 實作細節 - 對於輕點，$O(d^2)$ 跑過 $v$ 連到的任兩條邊連出去的點 x 和 y， 找出哪些 pair$(x, y)$ 有連邊可以形成三角形 如何找出所有 $(x, y)$ 是否有連邊? ---- ## 離線處理 ! 我們只需要知道有幾個 $(x, y)$ 有連邊即可加入答案 ---- 對於每個點，紀錄有連到哪些邊 再跑過每個詢問點 $x$ 是否有連到 $y$ ```cpp= void addQuery(int x, int y){ query[x].push_back(y); } void calc(){ for(int i = 0; i < n; i++){ for(int j : edge[i]) vis[j] = 1; for(int j : query[i]) ans += vis[j]; for(int j : edge[i]) vis[j] = 0; } } ``` ---- ## 結論 很多圖上根號分 case 的題目， 由於邊的數量都是有上限的，可以用 degree 大小來區分， 因此以外看到圖上計算每個節點與相鄰點之間關係的題目， 都可以想一下是否可以分 case 處理 --- ## 序列分塊 一種資料結構 用於區間操作，區間詢問之類的問題 ---- 將序列分成每塊大小為$\lfloor \sqrt{n} \rfloor$，而總共$\lceil \frac{n}{ \lfloor \sqrt{n} \rfloor } \rceil$塊 以 $n=10$ 為例 每塊大小為$\lfloor \sqrt{n} \rfloor = 3$，總共 $\lceil \frac{n}{ \lfloor \sqrt{n} \rfloor } \rceil = 4$ 塊  ```cpp= //分塊結構 //求區間總和 struct blk{ vector<int> local; //每塊的全部元素 int global; //儲存每塊的總和 int tag; //儲存整塊一起更新的值 blk(){ //初始化 local.clear(); //清空區間元素 tag = global = 0; //將區間總和先設為0 } }; ``` ---- ### 預處理 (求區間總和)  ```cpp= vector<blk> b; void build(){ int len=sqrt(n),num=(n+len-1)/len; for(int i=0;i<n;i++){ //第i個元素分在第 i/len 塊 cin>>x; //存入區間中 b[i/len].local.push_back(x); //更新區間總和 b[i/len].global += x; } } ``` ---- ### 區間加值 區間 1~9 加值 5  #### 最左塊 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 最左邊那塊每格暴力跑過去加值 #### 中間每塊 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 在中間每格的 TAG 加值 #### 最右塊 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 最右邊那塊每格暴力跑過去加值 ---- ### 區間加值 <div style="font-size:30px"> 假設區間 1~9 加值 5  會發現最右邊那塊裡面每格都有選到 但是為了方便實作，因此最右邊那格會直接暴力加 </div> ---- <div style="font-size:30px"> ### 區間加值 (求區間總和) </div> <div style="margin-left:-120px"> ```cpp= void update(int ql,int qr,int v){ int blk_l=ql/len,blk_r=qr/len,ret=0; if(blk_l == blk_r){ //如果都在同一塊直接一個一個跑過去就好 for(int i=ql;i<=qr;i++) b[blk_l].local[i%len]+=v; b[blk_l].global+=(qr-ql+1)*v; return; } for(int i=ql;i<(blk_l+1)*len;i++){ //最左的那一塊 b[blk_l].local[i%len]+=v; b[blk_l].global+=v; } for(int i=blk_l+1;i<blk_r;i++){ //中間每塊 b[i].tag+=v; b[i].global+=v*len; } for(int i=blk_r*len;i<=qr;i++){ //最右的那一塊 b[blk_r].local[i%len]+=v; b[blk_r].global+=v; } } ``` </div> ---- ### 詢問 (假設要求區間總和) 做法與區間加值相同，分最左、中間每塊、最右 以詢問區間 2-8 為例  ---- ### 詢問 (求區間總和) <div style="margin-left:-120px"> ```cpp= int query(int ql,int qr){ int blk_l=ql/len,blk_r=qr/len,ret=0; if(blk_l == blk_r){ //如果都在同一塊直接一個一個跑過去就好 for(int i=ql;i<=qr;i++) ret+=b[blk_l].local[i%len]+b[blk_l].tag; return ret; } for(int i=ql;i<(blk_l+1)*len;i++) //最左的那一塊 ret+=b[blk_l].local[i%len]+b[blk_l].tag; for(int i=blk_l+1;i<blk_r;i++) //中間每塊的總和 ret+=b[i].global; for(int i=blk_r*len;i<=qr;i++) //最右的那一塊 ret+=b[blk_r].local[i%len]+b[blk_r].tag; return ret; } ``` </div> ---- ## 複雜度分析 - 建表 $O(n)$， 一個一個跑過去就好 - 更新 最左的那塊裡面最多跑過 $\sqrt{n}$ 格 中間跑過最多 $\sqrt{n}$ 大塊 最右的那塊裡面最多跑過 $\sqrt{n}$ 格 複雜度 $O(\sqrt{n})$ - 詢問 同上 複雜度 $O(\sqrt{n})$ ---- ### 結論 分塊看起來複雜度比線段樹差 但分塊用迴圈實作常數比較小(線段樹遞迴常數較大) 實際上大部分題目都還是可以過的 $n = 2 \cdot 10^5 ， n \sqrt{n} = 89,442,719$ 熟悉之後，實作複雜度不比線段樹高 而且能解出更多線段樹解不出來的題目 --- ## 莫隊算法(mo's algorithm) 是2009年中國國家代表隊「莫濤」所提出來的 一種運用到分塊概念的離線演算法 ---- ## 使用條件 用於序列的區間詢問 對於詢問的 $[l,r]$ 區間，如果已經計算好區間內的答案 並且能在 $O(1)$ 或者 $O(\log N)$ 的複雜度內，計算轉移到區間的答案 $[l,r+1], [l,r-1], [l+1,r], [l-1,r]$ (即 $[l,r]$ 左界或右界移動一格) 則可以在$O(N\sqrt{N})$的複雜度內求出所有詢問的答案 ---- ### 引入問題 [SPOJ-DQUERY](https://www.spoj.com/problems/DQUERY/) 給你一個大小為 $n(n\le3 \cdot 10^4)$ 的序列 $a (1\le a_i\le10^6)$ $q(q\le200000)$ 筆詢問，每次問你區間 $[l,r]$ 內，有幾個不同的數字 如果每次都直接暴力找，最差複雜度 $O(NQ) \rightarrow$ TLE ---- ## 作法 將所有詢問分塊之後各自排序，依序暴力從前一個詢問區間計算完答案轉移到下一個詢問區間求出答案 將所有詢問依照先依照左界 $l$ 去分塊， $\frac{l}{\lfloor\sqrt{n}\rfloor}$ 一樣的在同一塊，而同一塊的分別再各自用右界 $r$ 去排序 ```cpp= int n,k = sqrt(n); //每塊大小為k struct query{ int l,r,id; //詢問的左界右界 以及 第幾筆詢問 friend bool operator<(const query& lhs,const query& rhs){ return lhs.l/k==rhs.l/k ? lhs.r<rhs.r : lhs.l<rhs.l; } //先判斷是不是在同一塊 不同塊的話就比較塊的順序，否則比較右界r }; ``` ---- ### 排序詢問 假設序列長度為 $10 (i \in 0 \sim 9)$ ， 每格大小為 $\lfloor\sqrt{10}\rfloor = 3$ 詢問有 [4, 8], [2, 3], [9, 9], [0, 7], [1, 2], [6, 9], [7, 8] 將詢問排序 (先比較塊的順序，再比較右界大小) [1, 2], [2, 3], [0, 7], [4, 8], [7, 8], [6, 9], [9, 9] ---- ### 暴力轉移 從前一個區間轉移到下一個區間，每次移動一格 以 區間 [0, 7] 轉移到區間 [4, 8] [0, 7] $\to$ [0, 8] $\to$ [1, 8] $\to$ [2, 8] $\to$ [3, 8] $\to$ [4, 8] 一次 新增/刪除 一個元素 ---- ## 暴力轉移 ```cpp= int num = 0; int cnt[1'000'005], ans[30'005]; vector<query> q; void add(int index){ ... } //新增元素到區間內並更新數量 num void sub(int index){ ... } //從區間內移除元素並更新數量 num void solve(){ sort(q.begin(),q.end()); for(int i=0,l=0,r=-1;i<n;i++){ while(l>q[i].l) add(--l); while(r<q[i].r) add(++r); //記得要先做新增元素的 while(l<q[i].l) sub(l++); //再做移除元素的 while(r>q[i].r) sub(r--); ans[q[i].id] = num; //移到區間後儲存答案 } } ``` ---- #### 計算新增/刪除元素 不同題目新增/移除元素做法不同，以例題來說 給你一個大小為 $n(n\le3 \cdot 10^4)$ 的序列 $a (1\le a_i\le10^6)$ 每次問你區間 $[l,r]$ 內，有幾個不同的數字 ? 直接開一個值域大小的陣列 cnt[1000005]，計算每個數字出現的次數 新增元素 add(x) 直接 cnt[x]+=1，並且判斷是不是原本為 0 ，若為 0 則個數 +1 移除元素 sub(x) 則為 cnt[x]-=1，移除後判斷是否變為 0 ，若為 0 則個數 -1 每次更新複雜度 $O(1)$ ---- #### 計算新增/刪除元素 ```cpp= void add(int x){ ++cnt[x]; if(cnt[x] == 1) ++num; } void sub(int x){ --cnt[x]; if(cnt[x] == 0) --num; } ``` ---- ## 複雜度分析 $n$ 為序列總長度， $q$ 為詢問比數， $p$ 為移動一格的複雜度 #### 左界 :::info 在同一塊裡，每次移動量最多為 $\sqrt{n}$， 不同塊之間距離總和最多為 $n$ 因此移動總量為 $q\sqrt{n} + n$ ::: #### 右界 :::info 每塊裡面是遞增的，因此每塊裡面最多移動 $n$，有 $\sqrt{n}$ 塊 而不同塊之間最多移動 $n$ ::: 移動加起來為 $q\sqrt{n} + n\sqrt{n} + n$ 複雜度為 $O(p(q+n)\sqrt{n})$ ---- ## 其他優化 排序的時候，在同一塊的詢問區間會用右界排序 而把相鄰分塊的右界大小關係交替 (小於$\to$大於$\to$小於$\to$大於) 就能省去一些常數的時間   ```cpp= bool operator<(const query &lhs, const query &rhs){ if(lhs.l/k!=rhs.l/k) return lhs.l/k<rhs.l/k; return ((lhs.l/k)&1?lhs.r<rhs.r:lhs.r>rhs.r); // 奇數塊右界遞增，偶數塊右界遞減之類 } ``` --- ## 常數優化 通常分塊、根號的題目的分塊大小會用常數決定， 常見的大小會設成 400, 450, 500 等等 ```cpp= const int k = 400; ``` 而不是由輸入的大小決定 ```cpp= int k = sqrt(n); ``` 使用常數宣告的方法常數通常會比較小 很多時候分塊 TLE 的時候也會直接調整分塊大小來避免一些特別產的測資 大家可以測試看看分塊大小不同的速度差別 ---- ## 作業 deadline: 2 week https://vjudge.net/contest/591312