莫队算法解决区间元素唯一性问题-平芜编程栈

1. 题目背景与需求分析

P3901 "数列找不同"是洛谷平台上的一道经典信奥练习题，主要考察选手对基础算法和数据结构的掌握程度。题目要求我们判断一个数列中是否存在重复元素，这是计算机科学中非常基础但又极其重要的问题类型。

这类问题在实际编程中有着广泛的应用场景，比如：

数据库系统中检查主键唯一性
网络爬虫去重处理
大数据分析中的重复记录检测

题目给出的输入格式通常为：

第一行：两个整数n和q，表示数列长度和查询次数 第二行：n个整数表示数列 接下来q行：每行两个整数l和r，表示查询区间

输出要求对每个查询，判断区间[l,r]内所有元素是否互不相同，是则输出"Yes"，否则输出"No"。

2. 暴力解法与复杂度分析

2.1 最直观的暴力解法

对于初学者来说，最容易想到的解法是双重循环暴力检查：

for (int i = l; i <= r; i++) { for (int j = i+1; j <= r; j++) { if (a[i] == a[j]) { return false; } } } return true;

这种解法的时间复杂度是O(q*n²)，当n和q较大时（比如都达到1e5），这种解法显然会超时。

2.2 暴力解法的优化空间

我们可以通过引入哈希表来优化内层循环：

unordered_set<int> s; for (int i = l; i <= r; i++) { if (s.count(a[i])) { return false; } s.insert(a[i]); } return true;

这样时间复杂度降为O(q*n)，但对于大规模数据仍然不够高效。

3. 高效解法：离线处理与莫队算法

3.1 莫队算法简介

莫队算法是一种优雅的离线处理区间查询问题的算法，特别适合解决这类"区间内元素是否唯一"的问题。其核心思想是通过合理地安排查询顺序，利用前一次查询的结果来加速当前查询的处理。

算法步骤：

对查询进行分块排序
维护一个当前区间和元素出现次数的统计
通过移动区间左右指针来处理查询

3.2 具体实现步骤

首先我们需要定义块大小和排序规则：

int block_size = sqrt(n); struct Query { int l, r, idx; bool operator<(const Query &other) const { if (l / block_size != other.l / block_size) return l < other.l; return (l / block_size) & 1 ? r < other.r : r > other.r; } };

然后实现莫队算法的核心逻辑：

vector<int> cnt(MAX_N, 0); int current_ans = 0; void add(int pos) { if (cnt[a[pos]] == 1) current_ans--; cnt[a[pos]]++; if (cnt[a[pos]] == 1) current_ans++; } void remove(int pos) { if (cnt[a[pos]] == 1) current_ans--; cnt[a[pos]]--; if (cnt[a[pos]] == 1) current_ans++; }

3.3 完整代码实现

#include <bits/stdc++.h> using namespace std; const int MAX_N = 1e5 + 5; int a[MAX_N]; int block_size; struct Query { int l, r, idx; bool operator<(const Query &other) const { if (l / block_size != other.l / block_size) return l < other.l; return (l / block_size) & 1 ? r < other.r : r > other.r; } }; vector<bool> mo_s_algorithm(vector<Query> queries) { vector<bool> answers(queries.size()); sort(queries.begin(), queries.end()); int cur_l = 0, cur_r = -1; unordered_map<int, int> freq; int distinct = 0; for (Query q : queries) { while (cur_l > q.l) { cur_l--; if (freq[a[cur_l]] == 1) distinct--; freq[a[cur_l]]++; if (freq[a[cur_l]] == 1) distinct++; } while (cur_r < q.r) { cur_r++; if (freq[a[cur_r]] == 1) distinct--; freq[a[cur_r]]++; if (freq[a[cur_r]] == 1) distinct++; } while (cur_l < q.l) { if (freq[a[cur_l]] == 1) distinct--; freq[a[cur_l]]--; if (freq[a[cur_l]] == 1) distinct++; cur_l++; } while (cur_r > q.r) { if (freq[a[cur_r]] == 1) distinct--; freq[a[cur_r]]--; if (freq[a[cur_r]] == 1) distinct++; cur_r--; } answers[q.idx] = (distinct == (q.r - q.l + 1)); } return answers; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin >> n >> q; block_size = sqrt(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<Query> queries(q); for (int i = 0; i < q; i++) { cin >> queries[i].l >> queries[i].r; queries[i].l--; queries[i].r--; queries[i].idx = i; } vector<bool> ans = mo_s_algorithm(queries); for (bool b : ans) { cout << (b ? "Yes" : "No") << "\n"; } return 0; }

4. 算法优化与性能分析

4.1 时间复杂度分析

莫队算法的时间复杂度主要取决于：

排序时间：O(q log q)
处理查询时间：O(n√n)

总时间复杂度为O(n√n + q log q)，这在n和q都达到1e5时是完全可行的。

4.2 常数优化技巧

在实际编码比赛中，以下几个优化技巧可以帮助提升运行速度：

使用快读快写：

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 - '0'; ch = getchar(); } return x * f; }

使用数组代替unordered_map：

int freq[MAX_N] = {0};

调整块大小：

block_size = n / sqrt(q); // 根据查询次数动态调整块大小

4.3 替代方案比较

除了莫队算法，这道题还可以用以下方法解决：

线段树：维护区间内元素是否唯一的信息
前缀和+哈希：记录每个元素最后出现的位置
分块：将数列分成若干块，预处理块内信息

但综合比较，莫队算法在这类问题上实现简单且效率较高，特别适合编程竞赛场景。

5. 常见错误与调试技巧

5.1 边界条件处理

在实现莫队算法时，最容易出错的是边界条件的处理：

区间下标从0开始还是从1开始
移动指针时先移动左指针还是右指针
初始时cur_l和cur_r的设置

建议在纸上画出区间移动的示意图，确保逻辑正确。

5.2 数据范围问题

需要注意题目给出的数据范围：

数列元素的大小范围
n和q的最大值
内存限制

特别是当使用哈希表时，要注意避免超内存。

5.3 调试输出技巧

在调试时可以添加一些输出语句：

void debug_print(int l, int r) { cout << "Current [" << l << "," << r << "]: "; for (int i = l; i <= r; i++) { cout << a[i] << " "; } cout << endl; cout << "Frequency: "; for (auto &p : freq) { if (p.second > 0) { cout << p.first << ":" << p.second << " "; } } cout << endl; }