NTUCPC Speed Run! #1 比賽已結束，感謝大家的參與！題目連結
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
IOICamp 2025 PreExam 進行中！ IOICamp 官網、PreExam 連結
程式解題社網站 程式解題社網站上線了！
207 . Bert 的數字集合
TopCoder
Tags
Description
Bert 有 $n$ 個數字，分別為 $a_1, a_2, \ldots, a_n$。而 Bert 是一位非常好奇的小孩，因此他會想要問你 $m$ 筆詢問，對於第 $i$ 筆詢問會給出 $l_i, r_i$，請你告訴 Bert $a_l, a_{l+1}, \ldots, a_r$ 所組成的數字集合其 mex 是多少。令 $S$ 是一個數字集合，則 $mex(S)$ 為集合 $S$ 沒有出現過的最小非負整數，像是 $\text{mex}(\lbrace 0, 1, 2, 4 \rbrace) = 3$。
Input Format
第一行分別給定兩個數字 $n, m$，代表接下來有 $n$ 個數字、$m$ 筆詢問。
第二行給定 $n$ 個數字，分別為 $a_1, a_2, \ldots, a_n$。
接下來 $m$ 行，每行一筆詢問會給定 $l_i, r_i$，代表想詢問的區間。
- $1\leq n, m \leq 2 \times 10^ 5$
- $0\leq a_i \leq 2 \times 10^ 5$
- $1\leq l_i \leq r_i \leq n$
Output Format
對於每筆詢問，給出 $a_l, a_{l+1}, \ldots, a_r$ 所組成的數字集合其 mex 是多少，一筆詢問請輸出一行。
Sample Input 1
10 8
4 4 4 1 1 0 3 2 2 4
8 9
1 10
2 10
6 9
1 4
7 9
1 2
6 9
4 4 4 1 1 0 3 2 2 4
8 9
1 10
2 10
6 9
1 4
7 9
1 2
6 9
Sample Output 1
0
5
5
1
0
0
0
1
5
5
1
0
0
0
1
Sample Input 2
10 8
2 2 3 0 2 0 4 1 3 0
8 9
1 10
2 10
6 9
1 4
7 9
1 2
6 9
2 2 3 0 2 0 4 1 3 0
8 9
1 10
2 10
6 9
1 4
7 9
1 2
6 9
Sample Output 2
0
5
5
2
1
0
0
2
5
5
2
1
0
0
2
Sample Input 3
10 8
0 2 0 1 3 2 1 2 0 0
8 9
1 10
2 10
6 9
1 4
7 9
1 2
6 9
0 2 0 1 3 2 1 2 0 0
8 9
1 10
2 10
6 9
1 4
7 9
1 2
6 9
Sample Output 3
1
4
4
3
3
3
1
3
4
4
3
3
3
1
3
Hints
Problem Source
IOICamp 2021 Day2 pG
Subtasks
| No. | Testdata Range | Constraints | Score |
|---|---|---|---|
| 1 | 0~2 | 範例測資 | 0 |
| 2 | 0~46 | 無額外限制 | 100 |