首先这题不需要离散化，而是动态开点。
如果是序列整体 \(\text{mex}\) 考虑权值线段树。
每个结点维护其值域区间中有没有数没出现过。
然后就从根结点开始，优先考虑左子树，
直到叶子结点或该子树为空，此时答案就是该结点值域区间的左端点。
现在考虑区间 \(\text{mex}\)。
我们让每个叶子结点维护该权值最后一次出现的位置，非叶子结点维护这个值域区间最早的最后出现的位置。
考虑离线。
把询问按照 \(r\) 排序，然后从 \(1\) 到 \(n\) 依次插入每个数，每次插入完第 \(i\) 个数就考虑 \(r = i\) 的询问。
于是在权值线段树上找最小的最后出现的位置 \(< l\) 的，因为 \(r\) 以后的数没有被插入，无需考虑其对答案的影响。
具体过程类似，从根结点优先考虑左子树，如果左子树最早的最后出现位置 \(< l\)，就说明左子树有至少一个满足要求的权值。
于是一直找直到子树为空或遇到叶子。
考虑在线。
可持久化出 \(n\) 棵主席树，询问就直接在第 \(r\) 棵上面查找。
注意一个 trick：答案一定在 \([0,n]\) 内。
考虑最坏情况，所有数恰好占满了从 \(0\) 开始的一段长度为 \(n\) 的区间，即 \([0,n)\)。
此时答案为 \(n\)。
其他情况答案都在 \(n\) 以下。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
using namespace std;
const int N = 2e5;
int n,m;
int a[N + 5],rt[N + 5];
struct node
{
int last;
int lson,rson;
} seg[(N << 5) + 10];
inline int copy_node(int p)
{
static int tot = 0;
seg[++tot] = seg[p];
return tot;
}
void change(int x,int k,int &p,int tl,int tr)
{
p = copy_node(p);
if(tl == tr)
{
seg[p].last = k;
return ;
}
int mid = tl + tr >> 1;
if(x <= mid)
change(x,k,ls(p),tl,mid);
else
change(x,k,rs(p),mid + 1,tr);
seg[p].last = min(seg[ls(p)].last,seg[rs(p)].last);
}
int query(int x,int p,int tl,int tr)
{
if(!p || tl == tr)
return tl;
int mid = tl + tr >> 1;
if(seg[ls(p)].last < x)
return query(x,ls(p),tl,mid);
else
return query(x,rs(p),mid + 1,tr);
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i),change(min(a[i],n + 1),i,rt[i] = rt[i - 1],0,n + 1);
int l,r;
while(m--)
{
scanf("%d%d",&l,&r);
printf("%d\n",query(l,rt[r],0,n + 1));
}
}