(Ioicamp Judge) 26. 區間MEX

http://judge.ioicamp.org/problems/26

區間MEX

Time Limit: 5s

Description

定義一個非負整數形成集合的 mex$\mathrm{mex}$（minimum excludant）為最小不在該集合的非負整數，例如：

• mex({1,2,3})=0$\mathrm{mex}(\{1,2,3\})=0$
• mex({0,1,2,3,5,8})=4$\mathrm{mex}(\{0,1,2,3,5,8\})=4$

現在給你一個長度 N$N$ 的序列 A$A$，你要支援以下詢問：

• 求一個區間內所有數形成的集合的 mex$\mathrm{mex}$ 值。

Input Format

第一行有一個正整數 T$T$，代表總共有幾筆測試資料。

每筆測試資料第一行包含兩個正整數 N,M$N,M$，代表序列的長度以及詢問數。
接下來包含 N$N$ 個由空白隔開的非負整數 Ai$A_i$，代表序列的元素。
接下來包含 M$M$ 行，每行包含兩個正整數 l,r$l,r$，
代表一個詢問，請輸出區間 {Al,…,Ar}$\{A_l,\dots ,A_r\}$ 的 mex$\mathrm{mex}$ 值。

• 1≤T≤20$1\le T\le 20$
• 1≤N,M≤105$1\le N,M\le {10}^5$
• 0≤Ai≤109$0\le A_i\le {10}^9$
• 詢問： 1≤l≤r≤N$1\le l\le r\le N$

Output Format

對於每個詢問，請輸出一行包含一個非負整數，代表該詢問區間的 mex$\mathrm{mex}$。

Sample Input

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

Sample Output

0
3
0
0
0
1
8

這題有兩種解法：

一種是我的隊友(很電的國手：余柏序)在賽中寫的：http://codingsimplifylife.blogspot.tw/2016/02/ioi-camp-judge-26mex.html

另外的解法是說：

因為數值>10^5就沒有用了(因為mex的定義是最小的非負整數，又最多只會出現10^5的數字，所以數值>10^5就可以不用考慮了)。

所以，我先把所有的詢問按照右界排序，數值線段樹裡面存的是 "這個數值最後出現在哪裡(沒有的話就-INF)" ！之後開始慢慢的push值(因問詢問按照右界排序)。

然後再查詢線段樹的時候，盡量往左走

這樣就OK了

#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

const int MAX_N = 100010;
const int MAX_M = 100010;

struct QUERY {
    int l;
    int r;
    int id;
} Query[MAX_M];

int ans[MAX_N];
int v[MAX_N];

bool operator<(const QUERY& q1,const QUERY& q2) {
    return q1.r<q2.r || q1.r==q2.r&&q1.l<q2.l;
}

struct Node {
    int val;
    Node* lc;
    Node* rc;
    Node () {
        val=-1;
        lc=rc=NULL;
    }
    void pull() {
        val = min(lc->val,rc->val);
    }
};

Node* Build(int L,int R) {
    Node* node = new Node();
    if (L==R) return node;
    int mid=(L+R)>>1;
    node->lc=Build(L,mid);
    node->rc=Build(mid+1,R);
    node->pull();
    return node;
}

void modify(Node* node,int L,int R,int pos,int val) {
    if (L==R) {
        node->val = val;
        return;
    }
    int mid=(L+R)>>1;
    if (pos<=mid) modify(node->lc,L,mid,pos,val);
    else modify(node->rc,mid+1,R,pos,val);
    node->pull();
    return; 
}

int query(Node* node,int L,int R,int val) { //val equals to query.l
    if (L==R) return L;
    int mid=(L+R)>>1;
    if (node->lc->val < val) return query(node->lc,L,mid,val);
    else return query(node->rc,mid+1,R,val);
}

int main () {
    int T;
    scanf("%d",&T);
    while (T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        for (int x=1;n>=x;x++) {
            scanf("%d",&v[x]);
            if (v[x]>100002) v[x]=100003;
        }
        Node* root = Build(0,MAX_N);
        for (int x=0;m>x;x++) {
            scanf("%d %d",&Query[x].l,&Query[x].r);
            Query[x].id=x;
        }
        sort(Query,Query+m);
        int nr;
        int id=1;
        for (int x=0;m>x;x++) {
            int L=Query[x].l;
            int R=Query[x].r;
            int t=Query[x].id;
            while (R>=id) {
                modify(root,0,MAX_N,v[id],id);
                id++;
            }
            ans[t]=query(root,0,MAX_N,L);
        }
        for (int x=0;m>x;x++) printf("%d\n",ans[x]);
    }
}