首頁 > 研究 > 正文

莫隊學習筆記_當前視點

2023-07-01 21:34:28來源：博客園  

引入問題

給出一個長度為 \(n\) 的數組 \(A\)，接下來 \(q\) 次詢問，每次詢問求 \([l,r]\) 中有多少組 \((i,j,k)\) 使得 \(a_i=a_j=a_k(i

保證 \(1\leq n\leq 10^5,1\leq A_i\leq n(1\leq i\leq n)\)。

莫隊的基礎思想——區間轉移

簡單分析問題，貌似并沒有可加性，所以分塊和線段樹肯定寄了。


(資料圖)

但是本題中相鄰區間轉移是 \(O(1)\)：

對于增加元素，設原有此元素 \(n\) 個，則增加三元組 \(\dfrac 1 2n(n-1)\) 個。對于刪除元素，設減去該元素后有此元素 \(n\) 個，則減少三元組 \(\dfrac 1 2n(n-1)\) 個。

莫隊算法是一種解決此類問題的離線算法，它基于以下思想：

我們不難考慮到一個暴力代碼，它的框架如下：

void del(LL x){cnt[a[x]]--;sum-=cnt[a[x]]*(cnt[a[x]]-1)/2;}void ins(LL x){sum+=cnt[a[x]]*(cnt[a[x]]-1)/2;cnt[a[x]]++;}LL l=1,r=0,sl,sr;for(int i=1;i<=q;i++){sl=b[i].l,sr=b[i].r;while(l

該代碼中出現的函數，ins(x)表示算上 \(x\) 這一項的貢獻，del(x)表示刪除 \(x\) 這一項的貢獻。

不難看出，這份代碼本質上是對于詢問區間的移動。

如果我們保證區間移動次數較少的話，時間復雜度也會比較優秀。

我們有什么思路呢？

時間復雜度優秀的秘密——分塊

我們取 \(B=\sqrt n\) 為塊長進行分塊，然后，按照左邊界所在的塊的編號給詢問區間排序，同一個塊則用右邊界排序。

不難得到如下代碼：

bool cmp(node x,node y){if(x.l/B==y.l/B)return x.r

我們來分析一下時間復雜度：

左邊界塊內移動，每次時間復雜度 \(O(\sqrt n)\)，有 \(q\) 次，時間復雜度為 \(O(q\sqrt n)\)。左邊界越塊移動，每次翻過一個塊的時間復雜度是 \(O(\sqrt n)\)，有 \(\sqrt n\) 次，時間復雜度為 \(O(n)\)。對于每個左邊界的塊，右邊界的移動整體來看都是 \(O(n)\) 的，有 \(\sqrt n\) 個塊，時間復雜度為 \(O(n\sqrt n)\)。

因此，莫隊的整體時間復雜度是 \(O(n\sqrt n)\)。

玄學優化——奇偶性優化

對于編號為奇數的塊，我們用右邊界從小到大排序，對于編號為偶數的塊，我們用右邊界從大到小排序。

這樣會快一點，因為不加優化之前來到新的塊右端點需要先回溯至這個塊里最小的右端點。

但是加了這個優化，有時我們可以從原先的最右邊從右往左依次處理新的塊的詢問，所以會快一點。

代碼實現
#include#define LL long longusing namespace std;const LL N=2e5+5;struct node{LL l,r,id;}b[N];LL n,q,B,a[N],cnt[N],ans[N],sum;bool cmp(node x,node y){if(x.l/B==y.l/B){if((x.l/B)&1)return x.ry.r;}return x.l/B

關鍵詞：

責任編輯：hnmd003

相關閱讀