NKOJ 4254 区间MEX 在线段树中

P4254区间MEX问题解析

问题描述

现在给定一个长度为n的数列，其中每个元素的编号从1到n，第i个元素的值为Ai。当前存在m个类似(L,R)的查询请求，需要针对每个区间[L,R]计算其mex值。具体而言，mex值指的是在该区间内未出现的最小非负整数。

输入格式

首行包含两个整数n和m
第二行由n个以空格分隔的整数构成，代表数列A
接下来的m行中，每行包含两个整数L和R，表示一次查询请求

输出格式

输出共m行，每行对应一个整数，表示相应查询的答案。

样例输入

7 5
0 2 1 0 1 3 2
1 3
2 3
1 4
3 6
2 7

样例输出

3
0
 3
 2
 4

提示

数据范围满足：1<=n,m<=200000
数列中的元素Ai满足：0<=Ai<=200000
查询区间满足：1<=L<=R<=n

---

若无法直接处理，则可采用离线算法。首先将所有查询按照左端点进行排序。

定义S[i]为区间[1,i]对应的MEX值，可