莫隊算法（區間處理）

0x00 概論

莫隊算法主要是用于離線解決 通常不帶修改隻有查詢的一類區間問題。

以前遇到區間問題的時候一般都是用線段樹解決，當然能用線段樹解決的問題也在多數。線段樹的主要思路就是通過一個左半拉序列

 和一個右半拉序列

 來維護它們的父親（也就是兩條序列接合在一起的完整序列）

，通過層層遞歸下去進而完成對整體序列的維護。但在有些時候可能會遇到如下的問題：

給定一個大小為N的數組，數組中所有元素的大小a[i]<=N。你需要回答M個查詢。每個查詢的形式是L，R。 你需要回答在範圍[ L，R ]中至少重複3次的數字的個數。

假設此時我們已經分别維護好了左右兩邊序列中每個數字重複的個數，然後開始向上維護，我們就會發現。。。

。。。

我們依然要把每個數字在左右序列中出現的次數加起來才能完成對一個父節點的維護……換而言之，我們并不能在

或者某個很短的時間内完成對線段樹單一節點的維護（如果神犇能夠無視這一句話請無視這一句話……）。

。。。

這時我們發現如果我們已知一個區間

的情況，我們可以在

的時間内确定

的情況（隻需開一個數組記錄每一個數出現的次數，然後将

的出現次數加一即可）。這樣我們可以在

的時間内完成對所有區間的掃描。

// 這裡有一段N^2的僞代碼
           

接着我們發現，我們不僅可以确定

，還可以确定

，

和

。這個時候，就可以用到莫隊算法啦。

0x01 莫隊算法

莫隊的精髓就在于，離線得到了一堆需要處理的區間後，合理的安排這些區間計算的次序以得到一個較優的複雜度。

再次假設我們已知區間

，需要計算的區間為

，由于

和

分别隻能單步轉移，是以需要的時間複雜度為

。相當于把兩個區間分别看成是平面上的兩個整點

和

，兩點之間的轉移開銷為兩點之間的曼哈頓距離。連接配接所有點的最優方案為一棵樹，那麼整體的時間複雜度就是這棵樹上所有曼哈頓距離之和。

于是乎最優的複雜度肯定是這棵樹是最小生成樹的時候，也就是曼哈頓距離最小生成樹。

但這麼打貌似代碼複雜度有點大。。而且在實際的轉移中肯定會出現分支，需要建邊（結構是一棵樹），那麼有沒有什麼賽艇的替代品可以少敲代碼并在一重循環裡完成暴力轉移呢？

當然是有的，我們先對序列分塊，然後以詢問左端點所在的分塊的序号為第一關鍵字，右端點的大小為第二關鍵字進行排序，按照排序好的順序計算，複雜度就會大大降低。

• 分塊相同時，右端點遞增是

  

  的，分塊共有

  

  個，複雜度為

  

• 分塊轉移時，右端點最多變化

  

  ，分塊共有

  

  個，複雜度為

  

• 分塊相同時，左端點最多變化

  

  ，分塊轉移時，左端點最多變化

  

  ，共有

  

  個詢問，複雜度為

  

所有總時間複雜度就是

0x02 樹上莫隊

樹上莫隊有一種樹分塊的做法這裡不講（因為我不會。。。），有興趣可以看看vfk的部落格WC 2013 糖果公園 park 題解。

還有一種就是先把一棵樹變成一條序列，然後直接用莫隊做就可以了，比如說下面這棵樹

我們把它整理成括号序的形式為：521134432665(也就是在dfs周遊樹的時候，将每個結點進棧時記錄一次，出棧時記錄一次)。

如果要詢問

之間的資訊，需要分類讨論：

• 如果

  

  是

  

  的祖先，所求資訊即為

  

  最後出現位置之間的資訊。
• 如果

  

  不是

  

  的祖先，所求資訊即為

  

  最先出現的位置以及

  

  最後出現的位置之間的資訊再加上

  

  上的資訊。

注意有些節點可能會在括号序中出現兩次，說明這個節點在這段過程中入棧後又彈出了，不能計入所求資訊（處理的話開個數組異或一下就好了）。

比如說要求

之間的資訊，這一段資訊為 括号序 4326 再加上

。

然後把剩下的事情交給莫隊……

0x03 帶修改的莫隊

對三元組

進行排序，表示在詢問

之前已經進行了

次修改操作， 同理知道了

 ，我們就可以知道

 ，

 ，

 ，

 ，

 ，

 的情況，分塊大小設為

，總時間複雜度為

。

（證明略）

0x04 草叢裡的莫隊

待更，這個版本插了真眼也看不到。（攤手）

0x05 題目&代碼

Problem 2038. -- [2009國家集訓隊]小Z的襪子(hose)

大意是詢問區間内任意選兩個數為同一個數的機率并化為最簡分數。

設在某一區間内共有顔色

，每雙襪子的個數為

答案為

化簡

即

是以隻需要用莫隊處理每個區間内不同數字的平方和就好了

#include <bits/stdc++.h>
using namespace std; const int Maxn = 50005; typedef long long ll; inline ll sqr(const ll &x) { return x * x; } inline ll gcd(const ll &a, const ll &b) { if (!b) return a; else return gcd(b, a % b); } inline char get(void) { static char buf[1000000], *p1 = buf, *p2 = buf; if (p1 == p2) { p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin); if (p1 == p2) return EOF; } return *p1++; } inline void read(int &x) { x = 0; static char c; for (; !(c >= '0' && c <= '9'); c = get()); for (; c >= '0' && c <= '9'; x = x * 10 + c - '0', c = get()); } int belong[Maxn]; // 每個點的分塊預處理 ll ans1[Maxn], ans2[Maxn]; struct Cmd { int l, r, id; friend bool operator < (const Cmd &a, const Cmd &b) { if (belong[a.l] == belong[b
           

轉載于:https://www.cnblogs.com/Renyi-Fan/p/8137905.html