莫队学习笔记（一）

本文参考自：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] 掉进兔子洞