[10月考试] F

题目描述

给定长度为 $n$ 的序列 $a_n$，保证 $a_i$ 为非负整数。

$m$ 次询问，每次给定区间 $l,r$，求出 $a_l,a_{l+1},\dots ,a_r$ 的 $mex$。

对于一个序列，定义其 $mex$ 为不在序列中出现的最小非负整数。

例如序列 $1,2,5,7$ 的 $mex$ 为 $0$，序列 $3,0,1,2,5$ 的 $mex$ 为 $4$。

对于所有数据，$n,m\le 1000$，$1\le l\le r\le n$，$0\le a_i\le 1000$。

输入格式

输入共 $m+2$ 行。

第 $1$ 行输入 $2$ 个正整数 $n,m$。

第 $2$ 行输入 $n$ 个非负整数 $a_1,a_2,\dots ,a_n$。

接下来 $m$ 行，每行输入 $2$ 个正整数 $l,r$ 代表一次询问。

输出格式

输出共 $m$ 行，每行输出 $1$ 个非负整数，代表一次询问的答案。

样例 #1

样例输入 #1

5 3
1 3 2 0 4
1 5
2 4
1 3

样例输出 #1

5
1
0

提示

对于 $30\%$ 的数据，$n,m\le 5$。

对于 $60\%$ 的数据，$n,m\le 100$，$a_i\le 5$。

对于所有数据，$n,m\le 1000$，$1\le l\le r\le n$，$0\le a_i\le 1000$。

题目解析

这道题要求我们对给定序列区间 [l, r] 求其 mex（即不在该区间内的最小非负整数）。mex 是序列中不包含的最小整数。例如，给定一个序列 1, 2, 3, 4，其 mex 为 0，因为 0 是最小的且不在这个序列中。

解题思路

1. 暴力解法：

   • 对每一个查询区间 [l, r]，我们可以直接扫描区间 [l, r]，找到其中所有的数，记录这些数。
   • 然后从 0 开始，找到最小的一个没有出现在区间内的数，返回这个数作为 mex。

   由于题目中的 n 和 m 最大为 1000，所以暴力方法的时间复杂度是 O(n * m)，每次查询的时间复杂度是 O(n)。最坏情况下，总时间复杂度为 O(n * m)，在最坏情况下（n = 1000, m = 1000）是可以接受的。

具体实现

1. 读取输入数据。

2. 处理每个查询，对于每个查询区间 [l, r]，我们：

   • 利用一个数组 count 来记录区间中各个数值的出现情况。

   • 找到最小的非负整数 mex，它不在区间内出现。

#include
#include
#include
using namespace std;

int main() {
int n, m;
cin >> n >> m;

vector<int> a(n);
for (int i = 0; i < n; i++) {cin >> a[i];
}// 处理每次查询
for (int i = 0; i < m; i++) {int l, r;cin >> l >> r;l--; r--;  // 转换为0-index// 用一个set来记录区间内的所有数set<int> nums_in_range;for (int j = l; j <= r; j++) {nums_in_range.insert(a[j]);}// 找到mexint mex = 0;while (nums_in_range.count(mex)) {mex++;}cout << mex << endl;
}return 0;
}

代码解析

1. 输入处理：
   • 首先读取 n 和 m。
   • 然后读取长度为 n 的序列 a。
2. 查询处理：
   • 对于每个查询区间 [l, r]，我们通过 set<int> nums_in_range 来记录该区间中所有不同的元素。
   • 通过遍历区间 [l, r]，将区间中的所有数插入到 nums_in_range 中（set 会自动去重）。
3. 计算 mex：
   • 从 0 开始查找最小的没有出现的数，即 mex。我们使用 count 方法来检查 mex 是否出现在 set 中，直到找到一个不在其中的 mex。
4. 输出结果：
   • 对于每次查询，输出对应的 mex 值。

时间复杂度

• 对于每个查询，扫描区间的时间复杂度是 O(r - l + 1)，而构建 set 的时间复杂度是 O(r - l + 1)。
• 查找 mex 的时间复杂度是 O(mex)，但是 mex 最大也不会超过区间中最大数值 + 1，所以它的时间复杂度是 O(n)（理论上最多为 n）。
• 因此，每个查询的时间复杂度为 O(n)，总时间复杂度为 O(n * m)，这是可以接受的。

简单算法思路

1. 遍历查询区间：对于每一个查询，我们需要遍历区间 [l, r]，将该区间内的所有数保存到一个集合中。
2. 计算 mex：mex 是从 0 开始，找到最小的一个不在集合中的数。

优化：直接使用一个数组来记录该区间内数字的出现情况，而不使用 set。

#include
#include
using namespace std;

int main() {
int n, m;
cin >> n >> m;

vector<int> a(n);
for (int i = 0; i < n; i++) {cin >> a[i];
}// 处理每次查询
for (int i = 0; i < m; i++) {int l, r;cin >> l >> r;l--; r--;  // 转换为0-index// 用一个数组记录区间内的数是否出现过bool appeared[1001] = {false};// 标记区间内的数for (int j = l; j <= r; j++) {appeared[a[j]] = true;}// 找到最小的没出现的数即为mexint mex = 0;while (appeared[mex]) {mex++;}cout << mex << endl;
}return 0;
}

代码解析

1. 输入处理：
   • 首先读取 n 和 m。
   • 然后读取长度为 n 的序列 a。
2. 查询处理：
   • 对于每个查询区间 [l, r]，我们创建一个布尔数组 appeared，该数组用于标记区间内出现的数字。数组大小为 1001，涵盖了所有可能出现的数字（0 到 1000）。
3. 计算 mex：
   • 对于每个区间 [l, r]，我们将区间内的每个数对应的 appeared 数组位置标记为 true。
   • 然后从 0 开始，查找最小的没有被标记为 true 的数字，那个数字就是 mex。
4. 输出结果：
   • 对于每次查询，输出对应的 mex 值。

时间复杂度分析

• 对于每个查询，我们需要扫描区间 [l, r]，这需要 O(r - l + 1) 的时间。最大时，区间长度为 n。
• 对于每个查询，我们还需要检查 appeared 数组的 mex 值，最多需要检查 1001 个位置，时间复杂度是 O(1001)，即常数时间。
• 所以每个查询的时间复杂度为 O(n)，总时间复杂度为 O(n * m)。