莫隊算法
給定一長度為 $n$的數列，有 $q$個詢問，問區間 $l,r$內眾數出現幾次? 有幾個眾數?
!可以離線
這題目乍看下是要刻一個比較特殊的線段樹，但是真的需要嗎?
首先，我們把問題reduce成
給定一長度為 $n$的數列，有兩個索引 $l,r$，有 $q$個操作，使 $l$變大或變小1、使 $r$變大或變小1，問每次操作區間 $l,r$內眾數出現幾次? 有幾個眾數?
這個問題看起來就簡單多了。
設app[x], cnt[c], maxcur為 $x$出現幾次、出現 $c$次的有幾種數字、目前的眾數是出現幾次。
每次移動雙指標時，都去維護app[x], cnt[c], maxcur，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
34void sub(int x)
{
--cnt[app[x]];
--app[x];
++cnt[app[x]];
if (cnt[maxcur] == 0)
--maxcur;
}
void add(int x)
{
--cnt[app[x]];
++app[x];
++cnt[app[x]];
maxcur = max(maxcur, app[x]);
}
//~~
while(q--)
{
//~~
if (op == "L l")
add(arr[--l]); //左指標左移
else if (op == "L r")
sub(arr[l++]); //左指標右移
else if (op == "R l")
sub(arr[r--]); //右指標左移
else if (op == "R r")
add(arr[++r]); //右指標右移
cout << maxcur << ' ' << cnt[maxcur] << '\n';
}
這樣的複雜度是$O(q)$。完美解決。
但是這個問題跟原始問題比起來，差在一個 移動是連續的；一個是 左界右界亂跳。
那我們不妨讓原始題目的詢問左右界排序成連續的樣子。
依照左界大小將詢問排序，再依照剛剛的做法去做，但是這樣會有一個問題
右界怎麼辦?
如果有很多筆操作，左界都相同，但是右界差距極大，這樣複雜度最差是$O(n^2)$
有沒有一種辦法去同時把左界排序又能維護好右界遞增呢?
有，但是左右界都需要犧牲一點單調性。
利用分塊的思想，將$n$個元素切成$K$塊，接著將所有詢問按照$L_i$所在的區塊排序，如果在同一個區塊，就再對
$R_i$做排序。
複雜度分析:
因為分塊的特性，在同一塊的左界不會移動超過$\frac{N}{K}$次，而左界屬於不同塊的操作，移動次數最多也不會超過N次。所以左界移動複雜度是$O(\frac{NQ}{K})$。
對於右界因為$R_i$是遞增，所以對於同一塊複雜度最多$O(N)$，對不同塊因為交界最多$K$次，每次最多也$O(N)$，所以維護右界複雜度為$O(NK)$。
取$K=\sqrt N$，複雜度為 $O(Q\sqrt N +N \sqrt N)$奇偶優化:
每一塊的$R_i$都是遞增，因此在遇到交界處時會有一個”大斷層”，導致右界必須移動許多次，但是如果反過來變成奇數塊遞增，而偶數塊遞減，就會讓右界的移動接近連續
實做判斷區塊是否為偶數進行遞增或遞減排序。code:
因為有點長，所以貼連結: Mo’s alogrithm