区间mex主席树
codeforces E. Complicated Computations
题目链接：http://codeforces.com/contest/1436/problem/E
注:此题的mex是在正整数中。

区间mex思路：
//...处的代码详见下方
insert(...,x,pos):
将x的值修改成pos,即x的下标最新为pos，因此每个节点记录该节点所表示的区间中出现的数的下标的最小值
(注:每个数的下标都是此时最新的下标)
query(root[r],...,l):
以root[r]为根的树中，找下标小于l的最小值，显然，此时不包含下标大于r的数。
如果一个数的最新下标小于我们的l，则说明这个数必然不在我们的[l,r]之间，那么这就是一个潜在的答案，
因此,在query中，只要[l,mid]之间的下标最小值小于l，说明答案必然在左边，反之在右边

主席树写法：
可以建完主席树之后再根据询问找答案。

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <set>

using namespace std ;

const int N = 100010 ;

int n , m ;

struct Node {
    int l , r ; //左右孩子编号
    int cnt ;
}tr[N*4 + N*17] ;

int root[N] ;
int idx ;

int build(int l , int r)    //建立最原始的线段树(空树)，返回根节点
{
    int _new = ++idx ;  //新节点编号
    if(l == r)
        return _new ;

    int mid = l + r >> 1 ;
    tr[_new].l = build(l , mid) , tr[_new].r = build(mid+1 , r) ;   //左右孩子节点编号
    return _new ;
}

int insert(int _old , int l , int r , int x , int pos)    //修改成last[x] = pos
{
    int _new = ++idx ;
    tr[_new] = tr[_old] ;
    if(l == r)
    {
        tr[_new].cnt = pos ;
        return _new ;
    }

    int mid = l + r >> 1 ;
    if(x <= mid)    tr[_new].l = insert(tr[_old].l , l , mid , x , pos) ; //在左边
    else    tr[_new].r = insert(tr[_old].r , mid+1 , r , x , pos) ;  //在右边

    tr[_new].cnt = min(tr[tr[_new].l].cnt , tr[tr[_new].r].cnt) ;    

    return _new ;
}

int query(int u , int l , int r , int k)  //找小于k的数
{
    if(l == r)  return l ;

    int mid = l + r >> 1 ;
    if(tr[tr[u].l].cnt < k)    return query(tr[u].l , l , mid , k) ; //在左边

    return query(tr[u].r , mid+1 , r , k) ; //在右边
}

int main()
{
    cin >> n ; 
    int M = n+1 ;
    root[0] = build(1 , M) ;
    vector<vector<int>> a(n+1 , vector<int>(1,0)) ;

    for(int i = 1 , x ; i <= n ; ++i)   
    {
        cin >> x ;
        a[x].push_back(i) ;
        root[i] = insert(root[i-1] , 1 , M , x , i) ;
    }
    for(int i = 1 ; i <= n ; ++i)   a[i].push_back(n+1) ;

    set<int> g ;
    for(int i = 1 ; i <= n ; ++i)
    {
        int m = a[i].size() ;
        for(int j = 0 ; j < m-1 ; ++j)
        {
            int l = a[i][j]+1 , r = a[i][j+1]-1 ;
            if(l <= r)
                g.insert(query(root[r] , 1 , M , l)) ;
        }
    }

    g.insert(query(root[n] , 1 , M , 1)) ;

    for(int i = 1 ; i <= N ; ++i)
    {
        if(!g.count(i)){
            cout << i << endl;
            break ;
        }
    }

    return 0 ;
}

线段树写法：
需要动态处理询问。

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <map>
#include <set>

using namespace std ;

const int N = 100010 ;

int tr[4*N] ;

int n , a[N] , idx ;
int last[N] ;

void modify(int u , int l , int r , int pos , int x)    //主席树
{
    if(l == r){
        tr[u] = x ;
    }else{
        int mid = l+r >> 1 ;
        if(pos <= mid)  modify(u<<1 , l , mid , pos , x) ;
        else    modify(u<<1|1 , mid+1 , r , pos , x) ;
        tr[u] = min(tr[u<<1] , tr[u<<1|1]) ;
    }
}

int query(int u , int l , int r , int k)    //查找区间[L+1,R-1]的mex，即...x(L)......x(R)...
{
    if(l == r)  return l ;

    int mid = l+r >> 1 ;
    if(tr[u<<1] < k)   return query(u<<1 , l , mid , k) ;  //左边只要有

    return query(u<<1|1 , mid+1 , r , k) ;  //右边
}

int main()
{
    cin >> n ; 

    //求形如...x......x...的mex
    set<int> g ;
    for(int i = 1 , x ; i <= n ; ++i)
    {
        cin >> a[i] ;
        x = a[i] ;
        if(last[x] + 1 < i)
            g.insert(query(1 , 1 , N , last[x]+1)) ;   //出现过了

        modify(1 , 1 , N , a[i] , i) ;
        last[a[i]] = i ;
    }

    for(int i = 1 ; i <= n ; ++i)   
        if(last[i] && last[i] != n)
            g.insert(query(1 , 1 , N , last[i]+1)) ;

    g.insert(query(1 , 1 , N , 1)) ;   //整个区间的mex

    for(int i = 1 ; i <= N ; ++i)
        if(!g.count(i)){
            cout << i << endl;
            break ;
        }

    return 0 ;
}