#P18892. [2026多校联测]可持久化线段树

[2026多校联测]可持久化线段树

题目描述

给出一个长度为 nn 的序列,现在给出 Q 次询问,每次询问给出一个区间 [l,r][l,r] ,你需要回答区间 [l,r][l,r] 中的数的 mex 是什么。

一个集合的 mex 定义为最小未出现的自然数,比如 mex(0,1,3)=2,mex(1,2,3)=0\text{mex}({0,1,3}) = 2,\text{mex}({1,2,3}) = 0。

请注意本题的数据范围。

输入格式

第一行两个整数 n,qn,q 表示序列长度和询问次数。

接下来一行 nn 个非负整数表示序列 aia_i。

接下来 qq 行,每行两个整数 li,ril_i,r_i 表示这一次询问的区间。

输出格式

输出 qq 行,每行一个非负整数,表示这次询问的答案。

样例 1 输入

5 2
4 3 0 1 2
2 4
1 5

样例 1 输出

2 
5

数据范围

对于 20%20\% 的数据,n≤3×102n \leq 3 \times 10^2。

对于 50%50\% 的数据,n≤5×103n \leq 5 \times 10^3。

对于 70%70\% 的数据,n≤5×104n \leq 5 \times 10^4。

对于 100%100\% 的数据,1≤n,q≤2×105,0≤ai<n1 \leq n,q \leq 2\times10^5,0 \leq a_i < n 且 aia_i 互不相同。