企业官网建设流程全解析

1. 引言

莫队算法（Mo’s Algorithm）是一种用于高效处理离线区间查询问题的优雅算法。它由莫涛在 2009 年提出，通过巧妙地调整查询顺序，将时间复杂度从 O(n²) 优化至 O(n√n) 级别，成为解决大量静态区间查询问题的利器。

本文将系统性地介绍基础莫队算法的核心思想、实现步骤、复杂度分析，并通过经典例题（如区间内不同数字的个数）进行实战演练，帮助读者彻底掌握这一算法。

2. 算法核心思想

莫队算法的核心在于“分块”与“离线处理”。

2.1 问题模型

我们通常面对的问题是：给定一个长度为 n 的序列 a[1…n]，以及 m 个离线查询，每个查询询问区间 [l, r] 的某个属性（如不同元素个数、区间和、众数等）。我们需要高效地回答所有查询。

2.2 暴力法的瓶颈

最直接的方法是对于每个查询，扫描整个区间 [l, r] 进行计算。总时间复杂度为 O(mn)，在 n 和 m 达到 10⁵ 级别时完全不可行。

2.3 莫队的优化思路

莫队算法观察到：相邻查询的区间往往有大量重叠部分。如果我们能从一个查询的答案 [l, r] 快速推导出下一个查询的答案 [l’, r’]，就能避免大量重复计算。

具体做法：

1. 将序列分成大小为 B 的块（通常 B = √n）。
2. 将所有查询按左端点所在的块编号为第一关键字排序，右端点为第二关键字排序。
3. 按此顺序依次处理查询，通过移动当前区间的左右指针 l, r 来“滑”到目标区间，并维护当前答案。

3. 算法实现步骤

3.1 数据结构准备

structQuery{intl,r,id;// 查询区间 [l, r] 和查询编号};intn,m;// 序列长度，查询个数inta[MAXN];// 原序列Query q[MAXM];// 查询数组intblock_size;// 块大小intans[MAXM];// 存储每个查询的答案intcur_ans;// 当前区间 [cur_l, cur_r] 的答案intcnt[MAXV];// 计数数组，用于维护当前区间内每个值的出现次数（以统计不同数字为例）

3.2 排序函数

boolcmp(constQuery&a,constQuery&b){// 按左端点所在块排序，块号相同则按右端点排序intblock_a=a.l/block_size;intblock_b=b.l/block_size;if(block_a!=block_b)returnblock_a<block_b;// 奇偶化排序优化：奇数块右端点升序，偶数块右端点降序，减少指针移动return(block_a&1)?(a.r<b.r):(a.r>b.r);}

3.3 区间移动操作（以统计不同数字个数为例）

voidadd(intpos){// 将位置 pos 的元素加入当前区间if(cnt[a[pos]]==0)cur_ans++;// 之前没出现过，不同数字数+1cnt[a[pos]]++;}voiddel(intpos){// 将位置 pos 的元素从当前区间移除cnt[a[pos]]--;if(cnt[a[pos]]==0)cur_ans--;// 该数字出现次数归零，不同数字数-1}

3.4 主算法流程

voidmo(){block_size=sqrt(n);// 设置块大小sort(q,q+m,cmp);// 对查询排序intcur_l=1,cur_r=0;// 当前维护的区间，初始为空区间 [1, 0]cur_ans=0;for(inti=0;i<m;i++){intl=q[i].l,r=q[i].r;// 移动左指针 cur_l 到目标 lwhile(cur_l>l)add(--cur_l);while(cur_l<l)del(cur_l++);// 移动右指针 cur_r 到目标 rwhile(cur_r<r)add(++cur_r);while(cur_r>r)del(cur_r--);ans[q[i].id]=cur_ans;// 记录答案}}

4. 复杂度分析

4.1 时间复杂度

• 左指针移动：对于每个查询，左指针最多移动 O(√n) 次（因为左端点在同一个块内）。共有 m 个查询，所以总移动次数为 O(m√n)。
• 右指针移动：对于每个块，右指针单调移动，总移动次数为 O(n)。共有 O(√n) 个块，所以总移动次数为 O(n√n)。
• 总复杂度：O((n+m)√n)。当 n 和 m 同阶时，约为 O(n√n)。

4.2 空间复杂度

• 需要存储原序列、查询和答案数组，以及辅助计数数组，总空间复杂度为 O(n + m + max_value_range)。

5. 经典例题：区间不同数字个数

问题描述：给定一个长度为 n 的序列，m 次询问，每次询问区间 [l, r] 内有多少个不同的数字。

解决方案：这正是基础莫队的模板题。我们使用上面给出的代码框架，add和del函数维护当前区间内每个数字的出现次数cnt[]以及不同数字的个数cur_ans。

完整代码示例：

#include<bits/stdc++.h>usingnamespacestd;constintMAXN=30005;constintMAXM=200005;constintMAXV=1000005;intn,m,block_size;inta[MAXN],ans[MAXM],cnt[MAXV],cur_ans;structQuery{intl,r,id;}q[MAXM];boolcmp(constQuery&a,constQuery&b){intblock_a=a.l/block_size;intblock_b=b.l/block_size;if(block_a!=block_b)returnblock_a<block_b;return(block_a&1)?(a.r<b.r):(a.r>b.r);}voidadd(intpos){if(cnt[a[pos]]==0)cur_ans++;cnt[a[pos]]++;}voiddel(intpos){cnt[a[pos]]--;if(cnt[a[pos]]==0)cur_ans--;}intmain(){scanf("%d",&n);for(inti=1;i<=n;i++)scanf("%d",&a[i]);scanf("%d",&m);for(inti=0;i<m;i++){scanf("%d %d",&q[i].l,&q[i].r);q[i].id=i;}block_size=sqrt(n);sort(q,q+m,cmp);intcur_l=1,cur_r=0;cur_ans=0;for(inti=0;i<m;i++){intl=q[i].l,r=q[i].r;while(cur_l>l)add(--cur_l);while(cur_l<l)del(cur_l++);while(cur_r<r)add(++cur_r);while(cur_r>r)del(cur_r--);ans[q[i].id]=cur_ans;}for(inti=0;i<m;i++)printf("%d\n",ans[i]);return0;}