今天不知道要學什麼 所以就找了一個還沒學過的演算法 而分塊法 和莫隊算法 是我還沒有碰過的演算法 所以就來學一下這兩個演算法吧
分塊算法 Square Root Decomposition (又稱根號算法) 分塊法是個什麼樣的演算法呢?
其實他跟線段樹的概念非常相似 線段樹的作法是將一個陣列劃分為 的長度去詢問
而分塊法則是分為 塊
由於線段樹分為 的長度 因此詢問時則是 而分為 的分塊法則是在 的時間完成詢問 一般的線段樹會需要 或 的空間儲存區間的值 而分塊則是需要額外的 的空間儲存 如何建立分塊呢?
1 2 3 for (int i = 0 ;i < n;i++){ block[i/k] = }
而在詢問時 我們會有兩個步驟
(一) 將不再分塊範圍的值用暴力法詢問 (二) 詢問區間的分塊
1 2 3 4 5 6 7 8 9 10 11 for (int i = l;i <= r;i++){ if (i/k!=l/k) break ; } for (int i = r;i >= l;i--){ if (i/k!=r/k) break ; } for (int i = l/k+1 ;i < r/k;i++){ }
可能看完程式碼還是不太懂 現在就讓我們來看看例題吧
分塊法 例題 一、區間最小值 Range Minimum Query (RMQ)
給予 個數字的陣列 以及 個詢問
每次詢問
請輸出 中的最小值
線段樹 (Segment Tree) 與稀疏表(Sparse Table) 的經典題 而我們也可以嘗試使用分塊法來完成這樣的題目
可以去 Zerojudge d539 丟丟看自己的解(不過是區間最大值)
程式碼
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 #include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std ;const int N = 5e5 +5 ;int k;int a[N];int block[N];int query (int l, int r) { int ans = INT_MAX; for (int i = l;i <= r;i++){ if (i/k!=l/k) break ; ans = min(ans,a[i]); } for (int i = r;i >= l;i--){ if (i/k!=r/k) break ; ans = min(ans,a[i]); } for (int i = l/k+1 ;i < r/k;i++) ans = min(ans,block[i]); return ans; } signed main () { fastio int n; cin >> n; k = sqrt (n); for (int i = 0 ;i < n;i++) cin >> a[i]; for (int i = 0 ;i <= n;i++) block[i/k] = min(block[i/k],a[i]); int m; cin >> m; while (m--){ int l, r; cin >> l >> r; l--,r--; cout << query(l,r) << "\n" ; } }
二、帶修改的區間最小值 前面做過區間最小值的題目了 但是題目不可能那麼單純只出區間最小值吧 線段樹能做到的修改 分塊當然也行 如果是單點修改 修改 位置的值 我們就直接修改陣列中 位置和他所在的分塊的值 複雜度
1 2 3 4 void modify (int i, int x) { arr[i] += x; block[i/k] += x; }
但是如果是區間修改 呢 我們直接修改區間的值呢? 僅僅是修改一次 整個複雜度會被提高到 所以我們又要利用到線段樹用過的概念 「懶惰標記」
1 2 3 4 5 6 7 8 9 10 11 12 13 14 void modify (int l, int r, int x) { for (int i = l/k+1 ;i < r/k;i++){ block[i] += k*x, lz_tag[i] += x; } for (int i = l;i <= r;i++){ if (i/k!=l/k) break ; a[i] += x; } if (l/k==r/k) return ; for (int i = r;i >= l;i--){ if (i/k!=r/k) break ; a[i] += x; } }
分析上面的程式碼 我們在區間加值時 最多會執行 次 (區間內不完全包住的塊總和最多兩塊) 因此時間複雜度為 而在詢問時 我們也要將懶惰打下去(最左和最右的兩塊)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 int query (int l, int r) { int ans = INT_MAX; if (lz_tag[l/k]){ for (int i = (l/k)*k; i < (l/k+1 )*k;i++){ a[i] += lz_tag[l/k]; } lz_tag[l/k] = 0 ; } if (lz_tag[r/k]){ for (int i = (r/k)*k; i < (r/k+1 )*k;i++){ a[i] += lz_tag[r/k]; } lz_tag[r/k] = 0 ; } for (int i = l;i <= r;i++){ if (i/k!=l/k) break ; ans = min(ans,a[i]); } for (int i = r;i >= l;i--){ if (i/k!=r/k) break ; ans = min(ans,a[i]); } for (int i = l/k+1 ;i < r/k;i++) ans = min(ans,block[i]); return ans; }
這樣我們就完成區間加值了
複雜度:
三、更多例題代補 代補
莫隊算法 Mo’s Algorithm 莫隊算法是由2009年中國國家代表隊的隊長「莫濤」所提出來的 一種處理區間問題的離線處理演算法 時間複雜度也非常好
什麼是莫隊算法 首先,我們先來看看一個問題
給予 項的陣列以及 個詢問 每次詢問 問在區間內 共有幾個不同的數字
我們如何去思考這個問題呢
如果我們用暴力的方式去處理這個問題 詢問的複雜度會是
如果我們有 次詢問 複雜度就會是
這樣子的時間無法過這個題目 那我們換個想法 我們有兩個指針
我們知道 這個區間的答案
我們可以在 或 的時間找到 答案
我們用這兩個指針加加減減去找到詢問的區間的答案: 用一個陣列 紀錄每個數字的出現次數
當 的時候 就代表多了一個數字
利用這個想法 我們可以寫出下面這樣的程式
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 const int N = 1e5 +5 ;int arr[N], cnt[N], tmp;void add (int pos) { if (!cnt[arr[pos]]) tmp++; cnt[arr[pos]]++; } void sub (int pos) { cnt[arr[pos]]--; if (!cnt[arr[pos]]) tmp--; } signed main () { fastio int n; cin >> n; for (int i = 0 ;i < n;i++) cin >> arr[i]; int q; cin >> q; int l = 0 , r = -1 ; for (int i = 0 ;i < q;i++){ int ql,qr; cin >> ql >> qr; while (l < ql) sub(l++); while (l > ql) add(--l); while (r < qr) add(++r); while (r > qr) sub(r--); cout << tmp << "\n" ; } }
不過你會發現 這樣子的程式
當詢問很多時 指針會一直來來回回的
時間複雜度也不會很好 大概是 吧
因此 莫隊算法就是建立在這個的基礎上去優化這種解法
我們可以經由排序來使這個演算法在 的時間完成所有詢問
如何使用莫隊算法 我們將 筆詢問 分別依照 所在的分塊進行排序 如果 所在的分塊相等 則依照 進行排序 只要這樣做之後就能使原本 的解法降低為 了
因為每一個分塊的詢問都依照 進行排序了
因此最多只要 就能完成所有答案了
程式碼
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 const int N = 1e6 +5 ;int k;int a[N], cnt[N], bid[N], l = 1 , r = 0 , tmp= 0 ; struct query { int l,r, id; bool operator < (const query b){ return (l/k == b.l/k ? r < b.r : l/k < b.l/k); } }; void add (int pos) { if (!cnt[a[pos]]) tmp++; cnt[a[pos]]++; } void sub (int pos) { --cnt[a[pos]]; if (!cnt[a[pos]]) tmp--; } signed main () { fastio int n; cin >> n; k = sqrt (n)+1 ; for (int i = 1 ;i <= n;i++) cin >> a[i]; int m; cin >> m; vector <query> Q; int ans[m]; for (int i = 0 ;i < m;i++){ int ql, qr; cin >> ql >> qr; Q.push_back({ql,qr,i}); } sort(Q.begin(),Q.end()); for (auto q : Q){ while (l < q.l) sub(l++); while (l > q.l) add(--l); while (r < q.r) add(++r); while (r > q.r) sub(r--); ans[q.id] = tmp; } for (auto x : ans) cout << x << "\n" ; }
這樣就完成區間共幾個不同數字的詢問了
可以去SPOJ-DQUERY 解解看這題
莫隊算法 例題 一、區間眾數 Zerojudge題目連結
這題要知道的是眾數的出現次數以及眾數有幾個 我們可以用一個陣列 紀錄每個數字的出現次數 然後再用另外一個陣列紀錄出現次數的次數 這樣我們就可以在 時間維護我們的答案了
程式碼
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 #include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std ;const int N = 1e5 +5 ;int k;struct query { int l,r,id; bool operator < (query b){ return (l/k == b.l/k ? r < b.r : l/k < b.l/k); } }; int a[N], cnt[N], cntcnt[N], ans;void add (int val) { cntcnt[cnt[val]]--; cnt[val]++; cntcnt[cnt[val]]++; if (cntcnt[cnt[val]] == 1 ) ans = max(cnt[val],ans); } void sub (int val) { cntcnt[cnt[val]]--; cnt[val]--; cntcnt[cnt[val]]++; if (ans==cnt[val]+1 &&cntcnt[cnt[val]+1 ]==0 ) ans = cnt[val]; } signed main () { fastio int n,m; cin >> n >> m; k = sqrt (n); for (int i = 1 ;i <= n;i++) cin >> a[i]; vector <query> Q; for (int i = 0 ;i < m;i++){ int l,r; cin >> l >> r; Q.push_back({l,r,i}); } int ans1[m], ans2[m]; sort(Q.begin(),Q.end()); int l = 1 , r = 0 ; cntcnt[0 ] = n; for (query q : Q){ while (l < q.l) sub(a[l++]); while (l > q.l) add(a[--l]); while (r < q.r) add(a[++r]); while (r > q.r) sub(a[r--]); ans1[q.id] = ans, ans2[q.id] = cntcnt[ans]; } for (int i = 0 ;i < m;i++) cout << ans1[i] << " " << ans2[i] << "\n" ; }
二、Codeforces 617E - XOR and Favorite Number 題目連結
這題要維護的是區間的XOR值為他所給的數字
我們都知道XOR的性質是 則
然後XOR和加法一樣 求區間和我們會使用前綴和 要求區間XOR也可以使用前綴XOR來求解
程式碼
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 #include <bits/stdc++.h> #define int long long #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std ;const int N = 1e5 +5 ;int k;struct query { int l, r, id; bool operator < (query b){ return (l/k == b.l/k ? r < b.r : l/k < b.l/k); } }; int arr[N], pref[N], cnt[1 <<20 ], tmp, num;void add (int val) { tmp += cnt[val ^ num]; cnt[val]++; } void sub (int val) { cnt[val]--; tmp -= cnt[val ^ num]; } signed main () { fastio int n,m; cin >> n >> m >> num; k = sqrt (n); for (int i = 1 ;i <= n;i++){ cin >> arr[i]; pref[i] = pref[i-1 ]^arr[i]; } vector <query> Q; int ans[m]; for (int i = 0 ;i < m;i++){ int l,r; cin >> l >> r; l--; Q.push_back({l,r,i}); } sort(Q.begin(),Q.end()); int l = 1 , r = 0 ; for (auto q : Q){ while (l < q.l) sub(pref[l++]); while (l > q.l) add(pref[--l]); while (r < q.r) add(pref[++r]); while (r > q.r) sub(pref[r--]); ans[q.id] = tmp; } for (auto x : ans) cout << x << "\n" ; }
Codeforces 877F - Ann and Books 題目連結
給予 本書(數學或經濟)以及一個 值
問一個區間有幾個子區間的數學書比經濟多 本
這題跟上面那題XOR有異曲同工之妙 基本兩題就差在XOR與加法而已
這題我們可以把經濟的書以負的做計算去做前綴和 左界的更新與右界的更新也有點不同 然後剩下的作法與上一題一模一樣 不過這題不同點是 的值很大 沒有辦法使用陣列來維護 如果使用 map 來維護 還是會因為 太大而TLE
因此 這題我們要用到離散化的技巧
程式碼
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 #pragma GCC optimize(2) #include <bits/stdc++.h> #define int long long #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std ;const int N = 3e5 +5 ;int k;struct query { int l,r,id; bool operator < (query b){ return (l/k == b.l/k ? r < b.r : l/k < b.l/k); } }; int arr[N], pref[N], tmp, num, up[N], down[N];int cnt[N];void addl (int i) { tmp += cnt[up[i]]; cnt[arr[i]]++; } void addr (int i) { tmp += cnt[down[i]]; cnt[arr[i]]++; } void subl (int i) { cnt[arr[i]]--; tmp -= cnt[up[i]]; } void subr (int i) { cnt[arr[i]]--; tmp -= cnt[down[i]]; } signed main () { fastio int n; cin >> n >> num; k = sqrt (n); for (int i = 1 ;i <= n;i++){ cin >> arr[i]; if (arr[i]==2 ) arr[i] = -1 ; } for (int i = 1 , a; i <= n;i++){ cin >> a; arr[i]*=a; } for (int i = 1 ;i <= n;i++){ pref[i] = pref[i-1 ] + arr[i]; } vector <int > v; for (int i = 0 ;i <= n;i++){ v.push_back(pref[i]); v.push_back(pref[i]+num); v.push_back(pref[i]-num); } sort(v.begin(),v.end()); v.resize(unique(v.begin(),v.end())-v.begin()); for (int i = 0 ;i <= n;i++){ arr[i] = lower_bound(v.begin(),v.end(),pref[i]) - v.begin() + 1 ; up[i] = lower_bound(v.begin(),v.end(),pref[i]+num) - v.begin() + 1 ; down[i] = lower_bound(v.begin(),v.end(),pref[i]-num) - v.begin() + 1 ; } int m; cin >> m; int ans[m]; vector <query> Q; for (int i = 0 ;i < m;i++){ int l,r; cin >> l >> r; l--; Q.push_back({l,r,i}); } sort(Q.begin(),Q.end()); int l = 0 , r = -1 ; for (auto q : Q){ while (l < q.l) subl(l++); while (l > q.l) addl(--l); while (r < q.r) addr(++r); while (r > q.r) subr(r--); ans[q.id] = tmp; } for (auto x : ans) cout << x << "\n" ; }
四、更多例題代補 代補
帶修改莫隊 (10/4更) 既然有區間詢問 那我們當然也需要區間更新阿
莫隊算法當然也能夠做到區間更新
我們將上面的題目做一點小修改
給予 項的陣列以及 個詢問或操作
每次詢問 問在區間內 共有幾個不同的數字
每次操作給予 將陣列第 個位置的數字改為
如何做到這一點呢
當莫隊將詢問做排序之後 我們該如何考慮到修改呢? 這裡 我們可以將原本的 Query 增加一個變數 表示時間
在排序時 這個 也會是我們要考慮的一部分
我們會依照詢問的 所在的分塊做排序 若相同 則用 所在的分塊排序
若 所在的分塊相同 我們則依照 去做排序
1 2 3 4 5 6 7 8 9 10 11 12 13 14 struct query { int l, r, t, id; bool operator < (query b){ if (l/k==b.l/k){ if (r/k==b.r/k){ return t < b.t; } return r/k < b.r/k; } return l/k < b.l/k; } };
就像上面那樣做 然後我們在詢問時 也要多一個 的指針
1 2 3 4 5 6 while (l < q.l) sub(arr[l++]);while (l > q.l) add(arr[--l]);while (r < q.r) add(arr[++r]);while (r > q.r) sub(arr[r--]);while (t < q.t) modify(Q[i],M[++t]);while (t > q.t) modify(Q[i],M[t--]);
然後修改時 如果修改的位置在 以內
我們就要修改答案的值 不然就直接修改陣列中的值就可以了
這邊有個很重要的一點 就是分塊的大小不在是 了
我們必須將分塊的大小設為 才會有最佳的複雜度
而帶修改莫隊的複雜度為 也是已經把 的複雜度降低非常多了
而上面例題的程式碼我附在這裡 題目可以去 洛谷P1903 解解看
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 #include <bits/stdc++.h> #define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); using namespace std ;const int N = 2e5 +5e4 ;const int S = 1e6 +5 ;int k;struct query { int l, r, t, id; bool operator < (query b){ return (l/k==b.l/k ? (r/k == b.r/k ? t < b.t : r/k < b.r/k) : l/k < b.l/k); } } Q[N]; struct upd { int pos,x; } M[N]; int arr[N], cnt[S], ans[N], tmp;void add (int val) { if (!cnt[val]) tmp++; cnt[val]++; } void sub (int val) { cnt[val]--; if (!cnt[val]) tmp--; } void modify (query x, upd &y) { if (x.l <= y.pos && y.pos <= x.r){ sub(arr[y.pos]); add(y.x); } swap(arr[y.pos],y.x); } signed main () { fastio int n, m; cin >> n >> m; k = pow (n,(double )2 /(double )3 ); for (int i = 1 ;i <= n;i++) cin >> arr[i]; int tid = 0 , qid = 0 ; for (int i = 0 ;i < m;i++){ char q; cin >> q; if (q=='Q' ){ int l, r; cin >> l >> r; Q[qid] = {l,r,tid,qid}; qid++; }else { int x, val; cin >> x >> val; ++tid; M[tid] = {x,val}; } } sort(Q,Q+qid); int l = 1 , r = 0 , t = 0 ; for (int i = 0 ;i < qid;i++){ auto q = Q[i]; while (l < q.l) sub(arr[l++]); while (l > q.l) add(arr[--l]); while (r < q.r) add(arr[++r]); while (r > q.r) sub(arr[r--]); while (t < q.t) modify(Q[i],M[++t]); while (t > q.t) modify(Q[i],M[t--]); ans[q.id] = tmp; } for (int i = 0 ;i < qid;i++) cout << ans[i] << "\n" ; }
帶修改莫隊 例題 一、Codeforces 940F - Machine Learning 題目連結
給一個 項的陣列 以及 行 Query
有兩種 Query
(一)區間詢問 值 ( 是一陣列中最小未出現的非負整數)
(二)單點修改
這題也是很裸的帶修改莫隊 可以自己解看看
時間複雜度:
二、更多例題代補 代補
樹上莫隊 代補
心得 今天學了莫隊算法之後 覺得這個演算法真的很厲害
不但很好使用 也有很多應用:樹上莫隊、帶修改莫隊之類的
不過自己還沒學到那麼多
這篇文章也會持續隨著自己的學習更新