3585: mex

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 918  Solved: 481

[][][]

Description

　　有一个长度为n的数组{a1,a2,...,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。

Input

　　第一行n,m。

　　第二行为n个数。

　　从第三行开始，每行一个询问l,r。

Output

　　一行一个数，表示每个询问的答案。

Sample Input

5 5

2 1 0 2 1

3 3

2 3

2 4

1 2

3 5

Sample Output

1

2

3

0

3

HINT

 

数据规模和约定

　　对于100%的数据：

　　1<=n,m<=200000

　　0<=ai<=109

　　1<=l<=r<=n

　　对于30%的数据：

　　1<=n,m<=1000

 

Source

 

 

http://www.lydsy.com/JudgeOnline/problem.php?id=3585

 

思路：

其实这题的思路和bzoj 3339完全就一样啊，连离散化都不需要。->我的bzoj3339：

因为对于n个数字，他的mex一定是<=n的，所以就算a[i]=1e9，那么我们就不要放到mex函数里面就好了，然后直接令next[i]=n+1即可，并不需要离散化

 

于是就这么简单的修改一下3339的代码，一下子就又过了= =

//看看会不会爆int!数组会不会少了一维！//取物问题一定要小心先手胜利的条件#include 
      
       using namespace std;#pragma comment(linker,"/STACK:102400000,102400000")#define LL long long#define ALL(a) a.begin(), a.end()#define pb push_back#define mk make_pair#define fi first#define se second#define haha printf("haha\n")const int maxn = 200000 + 5;vector
       
        
          > ve[maxn];int tree[maxn << 2], lazy[maxn << 2];int n, q;int a[maxn], mex[maxn];bool vis[maxn];int nxt[maxn], pos[maxn];void build_tree(int l, int r, int o){    lazy[o] = -1;    if (l == r){        tree[o] = mex[l]; return ;    }    int mid = (l + r) / 2;    build_tree(l, mid, o << 1);    build_tree(mid + 1, r, o << 1 | 1);    tree[o] = min(tree[o << 1], tree[o << 1 | 1]);}void push_down(int o){    int lb = o << 1, rb = o << 1 | 1;    if (lazy[lb] == -1 || lazy[lb] > lazy[o]){        lazy[lb] = lazy[o];        tree[lb] = min(tree[lb], lazy[lb]);    }    if (lazy[rb] == -1 || lazy[rb] > lazy[o]){        lazy[rb] = lazy[o];        tree[rb] = min(tree[rb], lazy[rb]);    }    tree[o] = -1;}int query(int x, int l, int r, int o){    if (x == l && x == r){        return tree[o];    }    if (lazy[o] != -1) push_down(o);    int mid = (l + r) / 2;    if (x <= mid) return query(x, l, mid, o << 1);    if (x > mid) return query(x, mid + 1, r, o << 1 | 1);}void update(int ql, int qr, int l, int r, int o, int val){    if (ql <= l && qr >= r){        if (lazy[o] == -1) lazy[o] = val;        lazy[o] = min(lazy[o], val);        tree[o] = min(lazy[o], tree[o]);        return ;    }    if (lazy[o] != -1)push_down(o);    int mid = (l + r) / 2;    if (ql <= mid) update(ql, qr, l, mid, o << 1, val);    if (qr > mid) update(ql, qr, mid + 1, r, o << 1 | 1, val);    tree[o] = min(tree[o << 1], tree[o << 1 | 1]);}int ans[maxn];void solve(){    build_tree(1, n, 1);    for (int i = 1; i <= n; i++){        for (int j = 0; j < ve[i].size(); j++){            int pos = ve[i][j].fi, id = ve[i][j].se;            ans[id] = query(pos, 1, n, 1);        }        int lb = i + 1, rb = nxt[i] - 1;        if (lb <= rb) update(lb, rb, 1, n, 1, a[i]);    }    for (int i = 1; i <= q; i++){        printf("%d\n", ans[i]);    }}int main(){    cin >> n >> q;    for (int i = 1; i <= n; i++) {        scanf("%d", a + i);        if (a[i] <= n + 10) vis[a[i]] = true;        mex[i] = mex[i - 1];        while (vis[mex[i]]) mex[i]++;        pos[i] = n + 1;    }    for (int i = 0; i <= n; i++) pos[i] = n + 1;    for (int i = n; i >= 1; i--){        if (a[i] >= n + 10){            nxt[i] = n + 1; continue;        }        nxt[i] = pos[a[i]];        pos[a[i]] = i;    }    for (int i = 1; i <= q; i++){        int l, r; scanf("%d%d", &l, &r);        ve[l].pb(mk(r, i));    }    solve();    return 0;}