区间 mex / Rmq Problem
题目描述
给定长度为 n 的非负整数序列 A1,…,An 和 q 次查询。每次给定区间端点 l,r,求该区间内没有出现过的最小非负整数。
对一个非负整数集合 S,记这个值为 mex(S)。每次查询的结果即为 $\operatorname{mex}\left(\{A_l,A_{l+1},\ldots,A_r\}\right)$。
输入格式
从标准输入读取。第一行两个正整数 n,q。第二行包含 n 个非负整数,依次为 A1,…,An。接下来 q 行每行两个整数 l,r,表示一次查询。
输出格式
向标准输出写入。按查询顺序输出 q 行,每行一个非负整数。
样例 1
7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7
3
0
3
2
4
样例说明
| 区间 |
区间中出现的数 |
mex |
| [1,3] |
0,2,1 |
3 |
| [2,3] |
2,1 |
0 |
| [1,4] |
0,2,1,0 |
3 |
| [3,6] |
1,0,1,3 |
2 |
| [2,7] |
2,1,0,1,3,2 |
4 |
数据范围
| 数据比例 |
n,q 的上限 |
| 10% |
100 |
| 30% |
10000 |
| 50% |
50000 |
| 100% |
200000 |
所有数据满足 0≤Ai≤200000,1≤l≤r≤n。