算法基础——莫队基础_莫队时间复杂度

知识点1: (普通)莫队的概念

(普通)莫队算法是一种优化的暴力算法，用于解决区间查询的离线算法，基于分块的思想，时间复杂度 $O(m\sqrt{n}+n\sqrt{n})$

什么时候使用莫队？

当对于一个查询 $[l,r]$，能够在 $O(1)$ 的时间内把 $[l,r]$ 的答案转移到相邻的区间 $[l,r-1]$，$[l,r+1]$ …此时可以考虑使用(普通)莫队算法

莫队的算法核心是分块和排序，即通过把询问离线化加以排序，把时间复杂度优化成 $O(m\sqrt{n}+n\sqrt{n})$

怎么排序呢？
双关键字排序

对于左端点对复杂度的贡献，设 $x_i$ 为第 $i$ 块中左端点的个数，最坏情况下，每个块贡献的复杂度 $O(x_i\sqrt{n})$，（即左端点，在每个块的两端滚来滚去），合并后：$$O(\sqrt{n}\sum _{i=0}^{\sqrt{n}}{x}_i)=O(m\sqrt{n})$$
对于右端点对复杂度的贡献，在每个分块中，右端点是非递减的，所以在每个块中的最坏复杂度是 $O(n)$，总的复杂度即为 $O(n\sqrt{n})$

所以总的时间复杂度即为：$O(m\sqrt{n}+n\sqrt{n})$

例题一

Acwing 2492
经典的莫队算法运用

题目

HH 有一串由各种漂亮的贝壳组成的项链。

HH 相信不同的贝壳会带来好运，所以每次散步完后，他都会随意取出一段贝壳，思考它们所表达的含义。

HH 不断地收集新的贝壳，因此他的项链变得越来越长。

有一天，他突然提出了一个问题：某一段贝壳中，包含了多少种不同的贝壳？

这个问题很难回答，因为项链实在是太长了。

于是，他只好求助睿智的你，来解决这个问题。

输入格式

第一行：一个整数 $N$，表示项链的长度。

第二行：$N$ 个整数，表示依次表示项链中贝壳的编号（编号为 $0$ 到 $1000000$ 之间的整数）。

第三行：一个整数 $M$，表示 $HH$ 询问的个数。

接下来 $M$ 行：每行两个整数，$L$ 和 $R$，表示询问的区间。

输出格式

$M$ 行，每行一个整数，依次表示询问对应的答案。

数据范围

$1\le N\le 50000$,
$1\le M\le 2\times 10^5$,
$1\le L\le R\le N$

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<vector>
#include<string>
#include<set>
#include<map>
#include<unordered_map>
#include<queue>

#define me(x,y) memset(x,y,sizeof x)
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define lowbit(x) -x&x
#define inf 0x3f3f3f3f
#define INF 0x7fffffff
#define cu(x) cout<<x<<"--"<<endl
#define ex exit(0)
#define pn puts("")

using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
typedef vector<int> vc;

inline int read()
{
	int x=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
	return x*f;
}

struct query
{
    int tag;
    int l,r;
};

const int N=5e4+10,M=2e5+10,C=1e6+10;
int n,m,siz,cnt;

int val[N];         //颜色总数
query ask[M];
int w[C];           //当前区间的颜色统计
int ans[M];

inline int get(int x)
{
    return (x-1)/siz;
}

bool operator<(const query&x1,const query& x2)
{
    if(get(x1.l)==get(x2.l))    return x1.r<x2.r;
    return get(x1.l)<get(x2.l);
}

inline void add(int x)
{
    int tag=val[x];
    if(!w[tag]) ++cnt;
    ++w[tag];
}

inline void del(int x)
{
    int tag=val[x];
    if(w[tag]==1)   --cnt;
    --w[tag];
}

int main()
{
    int i,j,l,r,k;
    
    scanf("%d",&n),siz=sqrt(n);
    for(i=1;i<=n;++i)
        scanf("%d",&val[i]);
    scanf("%d",&m);
    for(i=1;i<=m;++i)
    {
        scanf("%d%d",&l,&r);
        ask[i]={i,l,r};
    }
    
    sort(ask+1,ask+1+m);
    
    //i,j为当前的左右指针
    for(k=1,i=1,j=0;k<=m;++k)
    {
        l=ask[k].l,r=ask[k].r;
        
        while(j<r)  ++j,add(j);
        while(j>r)  del(j),--j;
        while(i<l)  del(i),++i;
        while(i>l)  --i,add(i);
        
        ans[ask[k].tag]=cnt;
    }
    
    for(i=1;i<=m;++i)
        printf("%d\n",ans[i]);

	return 0;
}

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108