問題： 有一個長為N序列，有M個詢問：在區(qū)間[L,R]內(nèi)，出現(xiàn)了多少個不同的數(shù)字。（序列中所有數(shù)字均小于K）。題目會給出K。

莫隊算法就是滋磁解決這類問題的離線算法。（其實很簡單）

首先來看看暴力： 由于暴力還是比較水的，所以直接上：

這個復(fù)雜度顯然是 O(N2)$O ( N^2 )$ 的。有些題目的范圍可能到100000或者更大，那么顯然就不能了。

這里還有一種稍作改進的方法，比上述做法大多數(shù)情況要快些。

其實還算好理解的，如果不明白，隨便搞組數(shù)據(jù)手玩一下就明白了

不幸的是，雖然這個東西比我們的暴力要快，但是它的時間復(fù)雜度仍然是 O(N2)$O(N^2)$ 的。 但好消息是，這個東西可以算是莫隊算法的核心了。（你在逗我笑？？？？） 其實是真的 :）

莫隊算法是怎么做的呢？ 考慮到上述改進的辦法的效率低下主要是因為curL和curR兩個指針前前后后跑來跑去太多次。于是，我們的做法就是不要讓他們跑太多沒用的距離。 我們可以通過離線下所有的詢問，然后通過某種排序，讓兩個指針跑動的距離盡量變少。具體的做法是把N劃分成N??√$/sqrt{N}$段，每段長度都是N??√$/sqrt{N}$，然后在把所有詢問按照L端點排序，看各個詢問被劃分到哪一塊里。接著，對于各個劃分出的段，在各自的段里，將它包含的所有區(qū)間再按照R端點排序。 舉個例子：假設(shè)我們有3個長度為3的段（0-2,3-5,6-8）： {0, 3} {1, 7} {2, 8} {7, 8} {4, 8} {4, 4} {1, 2} 先根據(jù)所在段落的編號重排 {0, 3} {1, 7} {2, 8} {1, 2} | {4, 8} {4, 4} | {7, 8} 現(xiàn)在按R的值重排 {1, 2} {0, 3} {1, 7} {2, 8} | {4, 4} {4, 8} | {7, 8}

然后？還要然后嗎？就用剛剛那個算法來玩就好了。畢竟我們只是交換了一下詢問的順序而已，并沒有對算法做什么改動。

對于這個的復(fù)雜度嘛，其實是比較鬼畜的，就這么改了下順序，然后就變成了O(N?N??√)$O(N*/sqrt{N})$的

上面代碼所有查詢的復(fù)雜性是由4個while循環(huán)決定的。前2個while循環(huán)是curL的移動總量”，后2個while循環(huán)是curR的移動總量”。這兩者的和將是總復(fù)雜度。 有趣的是。先考慮右指針：對于每個塊，查詢是遞增的順序排序，所以右指針curR按照遞增的順序移動。在下一個塊的開始時，指針是盡量靠右的 ，將移動到下一個塊中的最小的R處。這意味著對于一個給定的塊，右指針移動的量是 O(N)$O(N)$。我們有O(N??√)$O(/sqrt{N})$個塊。所以總共是O(N?N??√)$O(N*/sqrt{N})$。 關(guān)于左指針：所有查詢的左指針都在同一段中，當(dāng)我們完成一個查詢到下一個查詢時，左指針會移動，但由于兩次詢問的L在同一塊中，此移動是 O(N??√)$O(/sqrt{N})$的。所以，左指針的移動總量是O(M?N??√)$O(M*/sqrt{N})$。 所以，總復(fù)雜度就是O((N+M)?N??√)$O((N+M)*/sqrt{N})$，就當(dāng)做是O(N?N??√)$O(N*/sqrt{N})$吧。 是不是很簡單的吶2333

接下來給幾個例題：

例題1：BZOJ3781 小B的詢問

Description

小B有一個序列，包含N個1~K之間的整數(shù)。他一共有M個詢問，每個詢問給定一個區(qū)間[L..R]，求Sigma(c(i)^2)的值,其中i的值從1到K，其中c(i)表示數(shù)字i在[L..R]中的重復(fù)次數(shù)。小B請你幫助他回答詢問。

Input

第一行，三個整數(shù)N、M、K。 第二行，N個整數(shù)，表示小B的序列。 接下來的M行，每行兩個整數(shù)L、R。

Output

M行，每行一個整數(shù)，其中第i行的整數(shù)表示第i個詢問的答案。

Sample Input

6 4 3 1 3 2 1 1 3 1 4 2 6 3 5 5 6

Sample Output

6 9 5 2

HINT

對于全部的數(shù)據(jù)，1<=N、M、K<=50000

很裸的吧~

例題2：SDOI2009 HH的項鏈 洛谷1972

Description

HH有一串由各種漂亮的貝殼組成的項鏈。HH相信不同的貝殼會帶來好運，所以每次散步 完后，他都會隨意取出一段貝殼，思考它們所表達的含義。HH不斷地收集新的貝殼，因此， 他的項鏈變得越來越長。有一天，他突然提出了一個問題：某一段貝殼中，包含了多少種不同 的貝殼？這個問題很難回答。。。因為項鏈實在是太長了。于是，他只好求助睿智的你，來解 決這個問題。

Input

第一行：一個整數(shù)N，表示項鏈的長度。 第二行：N個整數(shù)，表示依次表示項鏈中貝殼的編號（編號為0到1000000之間的整數(shù)）。 第三行：一個整數(shù)M，表示HH詢問的個數(shù)。 接下來M行：每行兩個整數(shù)，L和R（1 ≤ L ≤ R ≤ N），表示詢問的區(qū)間。

Output

M行，每行一個整數(shù)，依次表示詢問對應(yīng)的答案。

Sample Input

6 1 2 3 4 3 5 3 1 2 3 5 2 6

Sample Output

2 2 4

HINT

對于20%的數(shù)據(jù)，N ≤ 100，M ≤ 1000； 對于40%的數(shù)據(jù)，N ≤ 3000，M ≤ 200000； 對于100%的數(shù)據(jù)，N ≤ 50000，M ≤ 200000。

還是很裸的2333

例題3：2009國家集訓(xùn)隊 小Z的襪子 清橙OJ1206

Description

HH有一串由各種漂亮的貝殼組成的項鏈。HH相信不同的貝殼會帶來好運，所以每次散步 完后，他都會隨意取出一段貝殼，思考它們所表達的含義。HH不斷地收集新的貝殼，因此， 他的項鏈變得越來越長。有一天，他突然提出了一個問題：某一段貝殼中，包含了多少種不同 的貝殼？這個問題很難回答。。。因為項鏈實在是太長了。于是，他只好求助睿智的你，來解 決這個問題。

Input

第一行：一個整數(shù)N，表示項鏈的長度。 第二行：N個整數(shù)，表示依次表示項鏈中貝殼的編號（編號為0到1000000之間的整數(shù)）。 第三行：一個整數(shù)M，表示HH詢問的個數(shù)。 接下來M行：每行兩個整數(shù)，L和R（1 ≤ L ≤ R ≤ N），表示詢問的區(qū)間。

Output

M行，每行一個整數(shù)，依次表示詢問對應(yīng)的答案。

Sample Input

6 1 2 3 4 3 5 3 1 2 3 5 2 6

Sample Output

2 2 4

HINT

對于20%的數(shù)據(jù)，N ≤ 100，M ≤ 1000； 對于40%的數(shù)據(jù)，N ≤ 3000，M ≤ 200000； 對于100%的數(shù)據(jù)，N ≤ 50000，M ≤ 200000。

樣例解釋

詢問1：共C(5,2)=10種可能，其中抽出兩個2有1種可能，抽出兩個3有3種可能，概率為(1+3)/10=4/10=2/5。 詢問2：共C(3,2)=3種可能，無法抽到顏色相同的襪子，概率為0/3=0/1。 詢問3：共C(3,2)=3種可能，均為抽出兩個3，概率為3/3=1/1。 注：上述C(a, b)表示組合數(shù)，組合數(shù)C(a, b)等價于在a個不同的物品中選取b個的選取方案數(shù)。

這道題倒是有些需要想想。 但是有一個神奇的事情：C(N,M)=N!M!?(N?M)!$C(N,M) = /frac{N!}{M!*(N-M)!}$ 那么C(N,2)呢？ 這不就是一個∑N?1i=1i$/sum_{i=1}^{N-1}i$嘛？ （有沒有感覺自己被續(xù)了一秒）

其實莫隊還可以套上樹狀數(shù)組或者在一棵樹上搞的，但是這篇文章就簡單先介紹下啦~ 要是俺有空就出莫隊的續(xù)集，嘿嘿~