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
Sample Output 1
0 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
Sample Output 2
0 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
Sample Output 3
1 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 |