[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)。