#P3585. mex

    ID: 2786 传统题 2000ms 128MiB 尝试: 1818 已通过: 618 难度: 6 上传者: 标签>CF1900普及+/提高-mex 计算离线查询普通线段树线段树上二分By佚名提供

mex

题目描述

有一个长度为 nn 的数组 a1,a2,⋯ ,ana_1,a_2,\cdots,a_n。mm 次询问,每次询问一个区间内最小的没有出现过的自然数。

输入格式

第一行 n,mn,m。
第二行为 nn 个数。
从第三行开始,每行一个询问 l,rl,r。

输出格式

一行一个数,表示每个询问的答案。

5 5
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
1
2
3
0
3

数据规模与约定

对于 30%30\% 的数据:1≤n,m≤1031\le n,m\le 10^3;

对于 100%100\% 的数据:1≤n,m≤2×1051\le n,m\le 2\times 10^5,0≤ai≤1090\le a_i\le 10^9,1≤l≤r≤n1\le l\le r\le n。

题目来源

By 佚名提供