莫隊算法學習筆記（二）——帶修莫隊

莫隊算法，是一個十分優雅的暴。普通的莫隊可以輕松解決一些離線問題，但是，當遇上了一些有修改操作的問題，普通莫隊就無能為力了。于是，改進後的莫隊——帶修莫隊就這樣産生了。

前言：什麼是莫隊

莫隊算法，是一個十分優雅的暴力。

普通的莫隊可以輕松解決一些離線問題，但是，當遇上了一些有修改操作的問題，普通莫隊就無能為力了。

于是，改進後的莫隊——帶修莫隊就這樣産生了。

接下來，我們一起在普通莫隊的基礎之上，學會帶修莫隊這個強大無比的算法。

第一個問題：如何處理修改

既然是帶修莫隊，那麼第一個關鍵問題就是如何處理修改。

其實，我們可以增加一個變量，來記錄對于每一個詢問操作，在進行詢問之前一共進行了多少次修改，然後對于每一次詢問，隻要像普通莫隊的\(L\)指針和\(R\)指針一樣新增一個\(K\)指針來表示目前進行了多少次修改，而\(K\)指針的移動也與\(L\)指針和\(R\)指針是類似的。

模闆如下：

register int L=0,R=0,K=0,ans=0;
for(sort(q+1,q+q_num+1,cmp),i=1;i<=q_num;++i)
{
        while(K<q[i].k) Change(++K);
        while(K>q[i].k) Change(K--);
        while(R<q[i].r) Add(++R);
        while(L>q[i].l) Add(--L);
        while(R>q[i].r) Del(R--);
        while(L<q[i].l) Del(L++);
        res[q[i].pos]=ans;
}
           

而\(Change()\)函數、\(Add()\)函數和\(Del()\)函數裡面的内容自己視題意而定。

第二個問題：如何寫排序函數

現在加上了一個\(k\)變量來表示在每個詢問之前進行了幾次操作。

那麼，現在的排序函數\(cmp()\)應該怎麼寫呢？

首先，應該判斷\(l\)是否在同一塊内，如果相同，就傳回\(pos[x.l]<pos[y.l]\)。

然後，應該判斷\(r\)是否在同一塊内，如果相同，就傳回\(pos[x.r]<pos[y.r]\)。

最後，再比較\(k\)的大小，即傳回\(x.k<y.k\)。

inline bool cmp(Query x,Query y)
{
    if(pos[x.l]^pos[y.l]) return pos[x.l]<pos[y.l];//判斷l是否在同一塊内，如果相同，就傳回pos[x.l]<pos[y.l]
    if(pos[x.r]^pos[y.r]) return pos[x.r]<pos[y.r];//判斷r是否在同一塊内，如果相同，就傳回pos[x.r]<pos[y.r]
    return x.k<y.k;//比較k的大小，即傳回x.k<y.k
}
           

第三個問題：塊的大小

學過莫隊的人應該都知道，莫隊算法需要分塊。

那麼帶修莫隊塊的大小應該是多少呢？

我們就需要對這個算法的時間複雜度進行一波分析。

首先我們假設塊的大小為\(n^x\)（其中\(0<x<1\)），并假設\(m\)的大小與\(n\)差不多。

那麼我們分别考慮3個指針的移動：

• 對于\(L\)指針
  • 在塊内移動時，每一次移動的複雜度應為\(O(n^x)\)，由于共有\(m\)次詢問，是以總複雜度為\(O(n^{x+1})\)。
  • 到下一個塊時，每一次移動的複雜度應為\(O(n^x)\)，由于塊的大小為\(O(n^x)\)，是以總塊數為\(O(\frac n{n^x})\)，是以總複雜度為\(O(n)\)。
  \(∴L\)指針的總複雜度為\(O(n^{x+1})\)。
• 對于\(R\)指針
  • \(L\)和\(R\)全都在塊内移動時，每一次移動的複雜度應為\(O(n^x)\)，由于這樣的情況共有\(O((\frac n{n^x})^2)\)，即\(O(n^{2-2x})\)次，是以總複雜度為\(O(n^{2-x})\)。
  • \(L\)塊相同且\(R\)到下一塊時，每一次移動的複雜度應為\(O(n^x)\)，由于總塊數為\(O(\frac n{n^x})\)，即\(O(n^{1-x})\)，是以總複雜度為\(O(n^{2-x})\)
  • \(L\)指針移動到下一個塊時，每一次移動的複雜度應為\(O(n)\)，由于這樣的情況共有\(O(\frac n{n^x})\)，即\(O(n^{1-x})\)次，是以總複雜度為\(O(n^{2-x})\)。
  \(∴R\)指針的總複雜度為\(O(n^{2-x})\)。
• 對于\(K\)指針
  • \(L\)和\(R\)全都在塊内移動時，此時\(K\)指針應該是遞增的（因為排序時對于這樣的情況我們\(return\) \(x.k<y.k\)），是以總複雜度為\(O(n)\)。
  • \(L\)塊相同且\(R\)到下一塊時，每一次移動的複雜度應為\(O(n)\)，由于這樣的情況有\(O(n^{2-2x})\)次，是以總複雜度為\(O(n^{3-2x})\)。
  • \(L\)指針移動到下一個塊時，每一次移動的複雜度應為\(O(n)\)，由于這樣的情況共有\(O(n^{1-x})\)次，是以總複雜度為\(O(n^{2-x})\)。
  \(∴K\)指針的總複雜度為\(O(n^{max(2-x,3-2x)})\)。

綜上所述，算法的總時間複雜度應為\(O(n^{max(x+1,2-x,3-2x)})\)，那麼我們的目的就是找到一個\(x\)（\(0<x<1\)）使\(max(x+1,2-x,3-2x)\)最小。

此時的\(x\)應取\(\frac23\)，是以塊的大小就是\(O(n^{\frac23})\)。

第四個問題：時間複雜度

呃，我想這個問題應該已經在上個問題中解決了。

例題

敗得義無反顧，弱得一無是處