分塊，然后撿到莫隊

文章目錄

• 分塊算法
• 普通莫隊

前言

HDU多校連續兩天都遇到了莫隊的題，于是蒟蒻緩慢地開始學習莫隊算法

初見莫隊，只知道是個離線區間工具，以為會有點復雜。但其實基礎的莫隊很好理解，就是一種讀完之后感覺很普通的離線的分塊算法（雖然，我還是不可能想得到就是了）

分塊算法

為了引入莫隊，不妨先看一個分塊的經典例題（不想看可以通過目錄跳過）

洛谷P3870 開關

簡化題意：一個01序列，要求可以進行動態區間取反和區間查詢（有幾個1）。

序列和詢問的數據規模都是$1e5$，暴力遍歷區間的復雜度是$O(nm)$，顯然無法接受。

考慮分塊，將長度為$n$的序列切割成$\sqrt{n}$個固定的區間，每個區間長度$\sqrt{n}$. 那么我們設想，對于每次詢問/修改，我們直接維護區間的狀態就好了，對各個分塊維護一個$ans$數組，由于區間最多$\sqrt{n}$個，所以復雜度就會降到$O(m\sqrt{n})$.

但是很快就發現，每次詢問和修改不一定都恰好落在我們分好的區間邊界上。例如，我們的劃分是$(1,3),(4,6),(7,10)$，但某次詢問的操作區間是$(2,9)$，那么，就會有$(2,3)$和$(7,9)$這兩個我們沒有劃出來的區間。

怎么辦？暴力計算！由于每個區間的長度最多$\sqrt{n}$，因此當詢問區間的起始區間和結尾區間不完整時，我們大可以對這兩個區間暴力維護答案。因此最終的復雜度仍然是$O(m\sqrt{n})$.

有的人可能會問：為什么分塊的長度要是 $\sqrt{n}$ 呢？

不妨分析：假設分塊的長度是$x$，那么塊的數量就是$n/x$. 每次詢問過程中，我們都需要處理開頭區間，結尾區間，以及在中間的剩下的完整的區間。這些完整的區間操作都是$O(1)$的，而他們的數量規模導致了這些區間的操作總復雜度在$O(n/x)$. 又我們可能還需要暴力地操作一頭一尾，所以我們還需要$O(x)$的時間去完成。那么總時間就會使$O(max(n/x,x))$. 顯然，這里$x$取$\sqrt{n}$可以讓每次詢問的復雜度最小。

分析完了，現在我們需要考慮，如何具體地進行答案維護與暴力。

由于分塊的過程中有部分暴力，對塊的操作與對單個元素的操作是并存的。為了讓整塊操作與散塊操作不沖突，我們可以為每個區間打上tag，tag為0表示該區間正常計算，tag為1表示該區間全部取反計算。那么每次整塊操作時，我們只需要關心tag，對tag取反即可。而散塊操作時，我們不需要關心tag，只需要對每個位置分別取反即可。最后維護出每個塊的$ans$.

而在詢問時，如果這個區間的tag是0，說明區間沒有被整個取反，那么我們直接取其$ans$作為答案；如果tag是1，那么區間被取反，所以我們也要對$ans$取反，以$n?ans$作為答案。

代碼（注釋詳解）

（由于也才沒學多久，沒看過板子，代碼屬于自己亂搞，可能有很多冗余繁雜的地方，但應該相對好理解）

#include <bits/stdc++.h> #define fors(i, a, b) for(int i = (a); i <= (b); ++i) #define lson k<<1 #define rson k<<1|1 #define pb push_back #define lowbit(x) ((x)&(-(x))) #define mem(a) memset(a, 0, sizeof(a)) #define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0) #define int long long const int inf = 0x3f3f3f3f; const double dinf = 1e100; typedef long long ll; //const ll linf = 9223372036854775807LL; // const ll linf = 1e18; const int N = 10005, M = 100005; using namespace std; struct node{int l, r, ans, tag; }a[N]; int st[M] = {0}; // 開燈狀態，用于散塊暴力 signed main() {DDLC_ESCAPE_PLAN_FAILED;int n, m; // 燈的數目和操作數目cin >> n >> m;int now = 1;int num = 0;fors(i, 1, n){if(now >= n + 1) break;num++;a[i].l = now;a[i].r = min(n, now + (int)sqrt(n));now = a[i].r + 1;a[i].ans = a[i].tag = 0; // 開燈數目和tag} // 分塊操作int p, l, r;while(m--){cin >> p >> l >> r;if(p){ // queryint i = 1;while(i <= num && a[i].l < l) i++;if(i > num || a[i].l > l) i--;// 找到左端散區間a[i]int ans = 0; // 總答案if(a[i].l != l) // 注意這個if語句避免了把最左邊的整塊當散塊{fors(j, l, min(a[i].r, r)){if(st[j] ^ a[i].tag) ans++;}i++;}while(i <= num && a[i].r <= r){ans += a[i].ans;i++;}if(i <= num){fors(j, a[i].l, r){if(st[j] ^ a[i].tag) ans++;}}cout << ans << endl;}else{ // switchint i = 1;while(i <= num && a[i].l < l) i++;if(i > num || a[i].l > l) i--;// 找到左端散區間a[i]int tmp = 0; // 修改后，散區間凈增加多少個打開的燈if(a[i].l != l) // 注意這個if語句避免了把最左邊的整塊當散塊{fors(j, l, min(a[i].r, r)){if(st[j] ^ a[i].tag) tmp--; // 如果區間的tag和其中某點不同，說明燈本來開著，使tmp-- else tmp++; // 否則tmp++st[j] = 1 - st[j];}a[i].ans += tmp;i++;}//-----while(i <= num && a[i].r <= r){a[i].ans = a[i].r - a[i].l + 1 - a[i].ans; // 反轉ansa[i].tag = 1 - a[i].tag; // 反轉tagi++;}//-----整塊修改if(i <= num){tmp = 0;fors(j, a[i].l, r){if(st[j] ^ a[i].tag) tmp--; // 如果區間的tag和其中某點不同，說明燈本來開著，使tmp-- else tmp++; // 否則tmp++st[j] = 1 - st[j];}a[i].ans += tmp;}}}return 0; }

以此，我們了解了分塊的基礎知識。

普通莫隊

實際上，普通莫隊可能比上面那題還要好寫

例題：

[洛谷P2709 小B的詢問](P2709 小B的詢問 - 洛谷 | 計算機科學教育新生態 (luogu.com.cn))

需要維護每個數字出現的次數。

考慮將整個序列分成$\sqrt{n}$塊，對每個詢問，按照它們$l$（左邊界）的位置將這些詢問放入不同的塊內。例如，$n=9$，分成$(1,3),(4,6),(7,9)$三塊，然后詢問的區間分別是$(5,7),(1,4),(6,8)$.

那么$(1,4)$在第一塊內，$(5,7),(6,8)$在第二塊內。

最后維護兩個指針$l,r$，通過雙指針的移動保存$(l,r)$的答案。

分析復雜度：

在每一塊內，$l$最多移動$\sqrt{n}$次，但$r$就不確定了，每次詢問都可能移動$n$次。這樣的話就麻煩了，復雜度又回到了$O(nm)$. 如何解決呢？對每一塊內的詢問，我們將所有詢問按$r$升序排序。這樣就能保證$r$的移動規模在$O(n)$范圍內了。$l$的移動范圍很小，只有$$\sqrt{n}$$，所以我們對$r$排序，不對$l$排序。

那么，對于整個序列，$r$的移動也是$O(n)$的，這將與詢問次數無關。每次詢問，$l$的移動都是$O(\sqrt{n})$的，故整個復雜度是$O(m\sqrt{n})$.

代碼

#include <bits/stdc++.h> #define fors(i, a, b) for(int i = (a); i <= (b); ++i) #define lson k<<1 #define rson k<<1|1 #define pb push_back #define lowbit(x) ((x)&(-(x))) #define mem(a) memset(a, 0, sizeof(a)) #define DDLC_ESCAPE_PLAN_FAILED ios::sync_with_stdio(false), cin.tie(0) // #define int long long const int inf = 0x3f3f3f3f; const double dinf = 1e100; typedef long long ll; //const ll linf = 9223372036854775807LL; // const ll linf = 1e18; using namespace std; const int maxn = 5e4 + 10; int n, m, k; struct query {int l, r; ll ans;// 左右邊界；詢問結果int idx, blc; // 下標；屬于第幾個塊 }q[maxn]; int st[maxn]; // 原數組 bool cmp1(const query& x, const query& y) {if(x.blc != y.blc) return x.blc < y.blc;return x.r < y.r; }bool rearr(const query& x, const query& y){return x.idx < y.idx; } signed main() {DDLC_ESCAPE_PLAN_FAILED;cin >> n >> m >> k;fors(i, 1, n) cin >> st[i];fors(i, 1, m) cin >> q[i].l >> q[i].r, q[i].idx = i, q[i].blc = (q[i].l - 1) / (int)sqrt(n) + 1;sort(q + 1, q + 1 + m, cmp1);ll ans = 0; // 當前答案unordered_map<int, int> mp; // 存每個數的出現次數int l = 1, r = 0;fors(i, 1, m){while(l > q[i].l){l--;ans -= mp[st[l]] * mp[st[l]];mp[st[l]]++;ans += mp[st[l]] * mp[st[l]];}while(r < q[i].r){r++;ans -= mp[st[r]] * mp[st[r]];mp[st[r]]++;ans += mp[st[r]] * mp[st[r]];}while(l < q[i].l){ans -= mp[st[l]] * mp[st[l]];mp[st[l]]--;ans += mp[st[l]] * mp[st[l]];l++;}while(r > q[i].r){ans -= mp[st[r]] * mp[st[r]];mp[st[r]]--;ans += mp[st[r]] * mp[st[r]];r--;}q[i].ans = ans;}sort(q + 1, q + 1 + m, rearr);fors(i, 1, m) cout << q[i].ans << endl;return 0; }

總結

以上是生活随笔為你收集整理的分块算法：莫队（持续更新）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。