207 . Bert 的數字集合

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

Caido
主唱太拼命了

User's AC Ratio

88.9% (8/9)

Submission's AC Ratio

82.4% (14/17)

Tags

ioicamp ioicamp-2021

Description

Bert 有 n 個數字，分別為 a1,a2,…,an。而 Bert 是一位非常好奇的小孩，因此他會想要問你 m 筆詢問，對於第 i 筆詢問會給出 li,ri，請你告訴 Bert al,al+1,…,ar 所組成的數字集合其 mex 是多少。令 S 是一個數字集合，則 mex(S) 為集合 S 沒有出現過的最小非負整數，像是 mex({0,1,2,4})=3。

Input Format

第一行分別給定兩個數字 n,m，代表接下來有 n 個數字、m 筆詢問。

第二行給定 n 個數字，分別為 a1,a2,…,an。

接下來 m 行，每行一筆詢問會給定 li,ri，代表想詢問的區間。

  • 1≤n,m≤2×105
  • 0≤ai≤2×105
  • 1≤li≤ri≤n

Output Format

對於每筆詢問，給出 al,al+1,…,ar 所組成的數字集合其 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

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 2000 524288 65536 1 2
1 2000 524288 65536 1 2
2 2000 524288 65536 1 2
3 2000 524288 65536 2
4 2000 524288 65536 2
5 2000 524288 65536 2
6 2000 524288 65536 2
7 2000 524288 65536 2
8 2000 524288 65536 2
9 2000 524288 65536 2
10 2000 524288 65536 2
11 2000 524288 65536 2
12 2000 524288 65536 2
13 2000 524288 65536 2
14 2000 524288 65536 2
15 2000 524288 65536 2
16 2000 524288 65536 2
17 2000 524288 65536 2
18 2000 524288 65536 2
19 2000 524288 65536 2
20 2000 524288 65536 2
21 2000 524288 65536 2
22 2000 524288 65536 2
23 2000 524288 65536 2
24 2000 524288 65536 2
25 2000 524288 65536 2
26 2000 524288 65536 2
27 2000 524288 65536 2
28 2000 524288 65536 2
29 2000 524288 65536 2
30 2000 524288 65536 2
31 2000 524288 65536 2
32 2000 524288 65536 2
33 2000 524288 65536 2
34 2000 524288 65536 2
35 2000 524288 65536 2
36 2000 524288 65536 2
37 2000 524288 65536 2
38 2000 524288 65536 2
39 2000 524288 65536 2
40 2000 524288 65536 2
41 2000 524288 65536 2
42 2000 524288 65536 2
43 2000 524288 65536 2
44 2000 524288 65536 2
45 2000 524288 65536 2
46 2000 524288 65536 2
Submit
Back to Top