#P3339. Rmq Problem

    ID: 2527 传统题 2000ms 256MiB 尝试: 1740 已通过: 647 难度: 6 上传者: 标签>难度分类提高博弈论mex 计算离线与分治离线查询查询排序数据结构普通线段树线段树上二分CF1900数据结构优化DP

Rmq Problem

区间 mex / Rmq Problem

题目描述

给定长度为 nn 的非负整数序列 A1,…,AnA_1,\ldots,A_n 和 qq 次查询。每次给定区间端点 l,rl,r,求该区间内没有出现过的最小非负整数。

对一个非负整数集合 SS,记这个值为 mex⁡(S)\operatorname{mex}(S)。每次查询的结果即为 $\operatorname{mex}\left(\{A_l,A_{l+1},\ldots,A_r\}\right)$。

输入格式

从标准输入读取。第一行两个正整数 n,qn,q。第二行包含 nn 个非负整数,依次为 A1,…,AnA_1,\ldots,A_n。接下来 qq 行每行两个整数 l,rl,r,表示一次查询。

输出格式

向标准输出写入。按查询顺序输出 qq 行,每行一个非负整数。

样例 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][1,3] 0,2,10,2,1 33
[2,3][2,3] 2,12,1 00
[1,4][1,4] 0,2,1,00,2,1,0 33
[3,6][3,6] 1,0,1,31,0,1,3 22
[2,7][2,7] 2,1,0,1,3,22,1,0,1,3,2 44

数据范围

数据比例 n,qn,q 的上限
10%10\% 100100
30%30\% 1000010000
50%50\% 5000050000
100%100\% 200000200000

所有数据满足 0≤Ai≤2000000\le A_i\le200000,1≤l≤r≤n1\le l\le r\le n。