莫隊學習筆記（一）

本文參考自：https://www.cnblogs.com/ouuan/p/MoDuiTutorial.html

普通莫隊

簡介

莫隊是一種基于分塊思想的離線算法，用于解決區間問題，适用範圍如下：

隻查詢不修改
允許離線處理（在開始時就需要知道問題的所有輸入資料，而且在解決一個問題後就要立即輸出結果）
在一直詢問 [l.r] 答案的情況下可以O(1)得到[l,r+1]，[l-1,r]，[l+1.r]的答案。

滿足以上的三個條件就可以在O(n m \sqrt{m} m

+mlogm) 的時間複雜度下得到每個查詢的解。

算法思想

莫隊的精髓就在于通過對詢問進行排序，并把詢問的結果作為下一次胥本為求解的基礎，使得暴力求解的複雜度得到保證。

上文中“适用範圍”的第三點“在已知詢問 [l,r] 答案的情況下可以 O(1) 得到 [l,r−1]，[l,r+1]，[l−1,r]，[l+1,r] 的答案”即是“把詢問的結果作為下一個詢問求解的基礎”的方法。

例題：[國家集訓隊]小Z的襪子

再該題中，用 cnt[i] 表示目前處理的區間内的顔色為 i 的襪子出現的次數，用 len 表示目前處理的區間的長度，用 x 表示新增的那隻襪子的顔色。

以已知區間 [l,r] 的答案求解區間[l,r+1]為例。分别處理分子和分母：

分子為任選兩隻襪子的組合總數，原先是 l e n ∗ ( l e n − 1 ) 2 \frac{len*(len-1)}{2} 2len∗(len−1)，現在是 l e n ∗ ( l e n + 1 ) 2 \frac{len*(len+1)}{2} 2len∗(len+1)，增加了 len。
分子為兩隻襪子顔色相同的組合總數，比原來增加了 cnt[i]，即新增的這隻襪子和原來就在目前區間内的顔色相同的襪子組合。

是以，顔色為 x 的襪子加入序列的函數：

//fz代表分子，fm代表分母
void add(int x)
{
    fz += cnt[x];
    ++cnt[x];
    fm += len;
    ++len;
}

顔色為 x 的襪子移除序列的函數：

void del(int x)
{
    --cnt[x];
    fz -= cnt[x];
    --len;
    fm -= len;
}

于是，我們就可以得到一個暴力的算法：用 l 和 r 分别記錄目前區間的兩個端點，然後用下面這段代碼來更新得到答案（q[i].l，q[i].r 代表正在處理的詢問的兩個端點，col[p]代表第 p 隻襪子的顔色）

while(l>q[i].l)
		add(col[--l]);
	while(r<q[i].r)
   		add(col[++r]);
    while(l<q[i].l)
        del(col[l++]);
    while(r>q[i].r)
        del(col[r--]);

然而，這個算法的時間複雜度是O(nm)，和暴力完全一樣甚至跑的更慢。

但是，先前我們提到的莫隊的精髓就在于對詢問的進行查詢，使得暴力求解的複雜度得到保證。

我們把整個區間[1,n]分成若幹塊，以查詢的左端點作為第一關鍵字，以查詢的右端點大小作為第二關鍵字，對其進行排序，那麼：

對于同一塊的詢問，l 指針每次最多移動塊的大小，r 指針的移動則是單調的，總共移動最多 n 。
對于不同塊的詢問，l 每次換塊時最多移動兩倍塊的大小， r 每次換塊時最多移動 n 。

總結：（用 B 表示塊的大小）l 指針每次移動 O(B)，r 指針每塊移動 O(n) 。

是以：

l 的移動次數最多為詢問數×塊的大小，即 O(mB) 。
r 的移動次數最多為塊的個數×總區間大小，即 O(n2/B) 。

是以，總移動次數為 O(mB+n2/B) 。

沒錯，這就是一個雙勾函數，是以 B = n 2 m \frac{n^2}{m} mn2即 n m \frac{n}{\sqrt{m}} m

n時複雜度最小，為O(n m \sqrt{m} m

)。

剩下的最後一個問題：初始的目前區間是什麼？

隻要任意指定一個空區間就好了，如 l=1，r=0 。

是以莫隊算法可以概括為：

記錄詢問
以 n m \frac{n}{\sqrt{m}} m

n為塊的大小，以查詢的左端點所在塊為第一關鍵字，以詢問的右端點大小為第二關鍵點，對詢問進行排序。
暴力處理每一個詢問
輸出答案

總的複雜度：O(n m \sqrt{m} m

+ mlogm)

代碼：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 100000;
const double eps = 1e-6;
const int maxn = 50100;
int n,m,nm;
int fz,fm,len;
int col[maxn],cnt[maxn],ans[maxn][2];
struct In{
    int l,r,id;
    bool operator < (In &b){
        return l/nm==b.l/nm ? r<b.r : l<b.l;
    }
}q[maxn];
inline int gcd(int a,int b)
{
    return b==0 ? a : gcd(b,a%b);
}
inline void add(int x)
{
    fz += cnt[x];
    ++cnt[x];
    fm += len;
    ++len;
}
inline void del(int x)
{
    --cnt[x];
    fz -= cnt[x];
    --len;
    fm -= len;
}
int main(void)
{
    scanf("%d%d",&n,&m);
    nm = n / sqrt(m);
    for(int i=1;i<=n;i++){
        scanf("%d",&col[i]);
    }
    for(int i=0;i<m;i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    sort(q,q+m);
    int l=1,r=0;
    for(int i=0;i<m;i++){
        if(q[i].l==q[i].r){
            ans[q[i].id][0] = 0;
            ans[q[i].id][1] = 1;
            continue;
        }
        while(l>q[i].l)
            add(col[--l]);
        while(r<q[i].r)
            add(col[++r]);
        while(l<q[i].l)
            del(col[l++]);
        while(r>q[i].r)
            del(col[r--]);
        int g = gcd(fz,fm);
        ans[q[i].id][0] = fz / g;
        ans[q[i].id][1] = fm / g;
    }
    for(int i=0;i<m;i++){
        printf("%d/%d\n",ans[i][0],ans[i][1]);
    }
    return 0;
}

例題2：SPOJ DQUERY

Given a sequence of n numbers a1, a2, …, an and a number of d-queries. A d-query is a pair (i, j) (1 ≤ i ≤ j ≤ n). For each d-query (i, j), you have to return the number of distinct elements in the subsequence ai, ai+1, …, aj.

Input

Line 1: n (1 ≤ n ≤ 30000).
Line 2: n numbers a1, a2, …, an (1 ≤ ai ≤ 106).
Line 3: q (1 ≤ q ≤ 200000), the number of d-queries.
In the next q lines, each line contains 2 numbers i, j representing a d-query (1 ≤ i ≤ j ≤ n).

Output

For each d-query (i, j), print the number of distinct elements in the subsequence ai, ai+1, …, aj in a single line.

Example

Input

1 1 2 1 3

1 5

2 4

3 5

Output

題意

查詢[l,r]區間内元素的種類，序列長度<=30000，元素大小∈[1,106]，查詢次數<=2000000。

思路

一般來說，普通莫隊改變的是add和del函數，其餘基本是差不多的，這裡我們可以用 cnt[x] 表示元素 x 在序列裡的個數，sum 表示序列裡元素的種類，那麼 add 和 del 函數可以寫作：

void add(int x)
{
    if(cnt[x]==0)   sum++;
    cnt[x]++;
}
void del(int x)
{
    --cnt[x];
    if(cnt[x]==0)   sum--;
}

AC代碼：

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 100000;
const double eps = 1e-6;
const int maxn = 2000010;
int n,m,nm;
int sum;
int col[maxn],cnt[maxn],ans[maxn];
struct In{
    int l,r,id;
    bool operator < (In &b){
        return l/nm==b.l/nm ? r<b.r : l<b.l;
    }
}q[maxn];
inline void add(int x)
{
    if(cnt[x]==0)   sum++;
    cnt[x]++;
}
inline void del(int x)
{
    --cnt[x];
    if(cnt[x]==0)   sum--;
}
int main(void)
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&col[i]);
    }
    scanf("%d",&m);
    nm = n / sqrt(m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    sort(q,q+m);
    int l=1,r=0;
    for(int i=0;i<m;i++){
        while(l>q[i].l)
            add(col[--l]);
        while(r<q[i].r)
            add(col[++r]);
        while(l<q[i].l)
            del(col[l++]);
        while(r>q[i].r)
            del(col[r--]);
        ans[q[i].id] = sum;
    }
    for(int i=0;i<m;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}

例題3：P2709 小B的詢問

#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
#include<ctime>
#include<utility>
#include<map>
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int INF = 100000;
const double eps = 1e-6;
const int maxn = 2000010;
int n,m,k,nm;
int sum;
int col[maxn],cnt[maxn],ans[maxn];
struct In{
    int l,r,id;
    bool operator < (In &b){
        return l/nm==b.l/nm ? r<b.r : l<b.l;
    }
}q[maxn];
inline void add(int x)
{
    if(x>k||x<1)    return ;
    if(cnt[x]==0)   sum++;
    else    sum += (2*cnt[x]+1);
    cnt[x]++;
}
inline void del(int x)
{
    if(x>k||x<1)    return ;
    --cnt[x];
    if(cnt[x]==0)   sum--;
    else    sum -= (2*cnt[x]+1);
}
int main(void)
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%d",&col[i]);
    }
    nm = n / sqrt(m);
    for(int i=0;i<m;i++){
        scanf("%d%d",&q[i].l,&q[i].r);
        q[i].id = i;
    }
    sort(q,q+m);
    int l=1,r=0;
    for(int i=0;i<m;i++){
        while(l>q[i].l)
            add(col[--l]);
        while(r<q[i].r)
            add(col[++r]);
        while(l<q[i].l)
            del(col[l++]);
        while(r>q[i].r)
            del(col[r--]);
        ans[q[i].id] = sum;
    }
    for(int i=0;i<m;i++){
        printf("%d\n",ans[i]);
    }
    return 0;
}

莫隊學習筆記（一）

普通莫隊

簡介

算法思想

題意

思路

繼續閱讀

[ 莫隊哈夫曼樹 ] Codeforces700D Huffman Coding on Segment

CodeForces 220B : Little Elephant and Array 莫隊

[BZOJ 2038]小Z的襪子莫隊（Mo's Algorithm）模闆題

帶修改的莫隊算法

莫隊基本知識

BZOJ 3757 蘋果樹樹上莫隊

小Z的襪子

洛谷 P4396 [AHOI2013]作業（莫隊 + 分塊 + 根号均攤）

【模闆】莫隊

HH的項鍊

男神zyh的青睐

[國家集訓隊]數顔色|維護隊列

SP10707 COT2 - Count on a tree II

P2709 小B的詢問【莫隊】

【YNOI2016】【BZOJ4939】【LOJ6199】【洛谷P4688】掉進兔子洞（莫隊）（bitset）BZOJ傳送門LOJ傳送門洛谷傳送門解析：

[Ynoi2016] 掉進兔子洞