<style> .reveal .slides { text-align: left; } </style> <div style="font-size:30px"> # SQRT-Decomposition </div> Introduction to Competitive Programming 2022/03/30 ---- * 分塊 * 莫隊 --- <div style="font-size:30px"> ## 分塊(SQRT-Decomposition) 如其英文名，根號分解 一種資料結構 用於區間操作，區間詢問之類的問題 </div> ---- <div style="font-size:30px"> 將序列分成每塊大小為$\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$塊  <div style="margin-left:-60px"> ```cpp= //分塊結構 //假設要求區間總和 struct blk{ vector<int> local; //每塊的全部元素 int global; //儲存每塊的總和 int tag; //儲存整塊一起更新的值 blk(){ //初始化 local.clear(); //清空區間元素 tag = global = 0; //將區間總和先設為0 } }; ``` </div> </div> ---- <div style="font-size:30px"> ### 預處理 (假設要求區間總和) </div>  <div style="margin-left:-60px"> ```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; } } ``` </div> ---- ### 區間加值 <div style="font-size:30px"> 假設區間 1~9 加值 5 </div>  ##### 最左塊 <div style="font-size:30px"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 最左邊那塊每格暴力跑過去加值 </div> ##### 中間每塊 <div style="font-size:30px"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 在中間每格的 TAG 加值 </div> ##### 最右塊 <div style="font-size:30px"> &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 最右邊那塊每格暴力跑過去加值 </div> ---- ### 區間加值 <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> ---- <div style="font-size:30px"> ### 詢問 (假設要求區間總和) 做法與區間加值相同，分最左、中間每塊、最右 以詢問區間 2-8 為例  </div> ---- <div style="font-size:30px"> ### 詢問 (假設要求區間總和) </div> <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> ---- ## 複雜度分析 <div style="font-size:25px"> - 建表 $O(n)$， 一個一個跑過去就好 - 更新 最左的那塊裡面最多跑過 $\sqrt{n}$ 格 中間跑過最多 $\sqrt{n}$ 大塊 最右的那塊裡面最多跑過 $\sqrt{n}$ 格 複雜度 $O(\sqrt{n})$ - 詢問 同上 複雜度 $O(\sqrt{n})$ </div></div> ---- ### 結論 <div style="font-size:30px"> 分塊看起來複雜度比線段樹差 但分塊用迴圈實作常數比較小(線段樹遞迴常數較大) 實際上大部分題目都還是可以過的 $n = 2 \cdot 10^5 ， n \sqrt{n} = 89,442,719$ 熟悉之後，實作複雜度不比線段樹高 而且能解出更多線段樹解不出來的題目 </div> --- <div style="font-size:30px"> ## 莫隊算法(mo's algorithm) 是2009年中國國家代表隊「莫濤」所提出來的 一種運用到分塊概念的離線演算法 </div> ---- <div style="font-size:25px"> ## 使用條件 用於序列的區間詢問 對於詢問的 $[l,r]$ 區間，如果已經計算好區間內的答案 並且能在 $O(1)$ 或者 $O(lgN)$ 的複雜度內，計算轉移到區間的答案 $[l,r+1], [l,r-1], [l+1,r], [l-1,r]$ (即 $[l,r]$ 左界或右界移動一格) 則可以在$O(N\sqrt{N})$的複雜度內求出所有詢問的答案 </div> ---- <div style="font-size:30px"> ### 引入問題 [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 </div> ---- <div style="font-size:30px"> ## 作法 將所有詢問分塊之後各自排序，依序暴力從前一個詢問區間計算完答案轉移到下一個詢問區間求出答案 將所有詢問依照先依照左界 $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 }; ``` </div> ---- ### 排序詢問 <div style="font-size:25px"> 假設序列長度為 $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] </div> ---- ### 暴力轉移 <div style="font-size:25px"> 從前一個區間轉移到下一個區間，每次移動一格 以 區間 [0, 7] 轉移到區間 [4, 8] [0, 7] $\to$ [0, 8] $\to$ [1, 8] $\to$ [2, 8] $\to$ [3, 8] $\to$ [4, 8] 一次 新增/刪除 一個元素 </div> ---- <div style="font-size:25px"> ## 暴力轉移 </div> <div style="margin-left:-120px;"> ```cpp= int num = 0; int cnt[1'000'005], ans[30'005]; vector<query> q; void add(int index){ ... } //新增元素到區間內 void sub(int index){ ... } //從區間內移除元素 void solve(){ sort(q.begin(),q.end()); for(int i=0,l=-1,r=0;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; //移到區間後儲存答案 } } ``` </div> ---- #### 計算新增/刪除元素 <div style="font-size:25px"> 不同題目新增/移除元素做法不同，以例題來說 給你一個大小為 $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)$ </div> ---- #### 計算新增/刪除元素 <div style="font-size:35px"> ```cpp= void add(int x){ ++cnt[x]; if(cnt[x] == 1) ++num; } void sub(int x){ --cnt[x]; if(cnt[x] == 0) --num; } ``` </div> ---- <div style="font-size:22px"> ## 複雜度分析 $n$ 為序列總長度， $q$ 為詢問比數， $p$ 為移動一格的複雜度 - 左界 >在同一塊裡，每次移動量最多為 $\sqrt{n}$， 不同塊之間距離總和最多為 $n$ 因此移動總量為 $q\sqrt{n} + n$ - 右界 >每塊裡面是遞增的，因此每塊裡面最多移動 $n$，有 $\sqrt{n}$ 塊 而不同塊之間最多移動 $n$ 移動加起來為 $q\sqrt{n} + n\sqrt{n} + n$ 複雜度為 $O(p(q+n)\sqrt{n})$ </div> ---- ## 其他優化 <div style="font-size:25px"> 排序的時候，在同一塊的詢問區間會用右界排序 在同一塊的最後面右界會最大，而到了下一塊的右界 當換到下一塊的時候右界又回到最小開始，增加移動次數 而如果換不同塊的時候，右界大小關係交替(小於$\to$大於$\to$小於$\to$大於) 就能省去一些常數的時間 </div>  --- ### Question Time and Practice [Homework Link](https://vjudge.net/contest/486761) <div style="font-size: 30px"> 提交期限到下星期三 4/6 23:59 截止 </div>