BZOJ 3585 Mex

首先这题不需要离散化，而是动态开点。

如果是序列整体 mex 考虑权值线段树。
每个结点维护其值域区间中有没有数没出现过。

然后就从根结点开始，优先考虑左子树，
直到叶子结点或该子树为空，此时答案就是该结点值域区间的左端点。

现在考虑区间 mex。
我们让每个叶子结点维护该权值最后一次出现的位置，非叶子结点维护这个值域区间最早的最后出现的位置。

考虑离线。
把询问按照 r 排序，然后从 1 到 n 依次插入每个数，每次插入完第 i 个数就考虑 r=i 的询问。
于是在权值线段树上找最小的最后出现的位置 <l 的，因为 r 以后的数没有被插入，无需考虑其对答案的影响。
具体过程类似，从根结点优先考虑左子树，如果左子树最早的最后出现位置 <l，就说明左子树有至少一个满足要求的权值。
于是一直找直到子树为空或遇到叶子。

考虑在线。
可持久化出 n 棵主席树，询问就直接在第 r 棵上面查找。

注意一个 trick：答案一定在 [0,n] 内。
考虑最坏情况，所有数恰好占满了从 0 开始的一段长度为 n 的区间，即 [0,n)。
此时答案为 n。
其他情况答案都在 n 以下。

代码：

#include <cstdio>
#include <algorithm>
#define ls(p) seg[p].lson
#define rs(p) seg[p].rson
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));
    }
}