3585: mex

Time Limit: 20 Sec  Memory Limit: 128 MB

Submit: 787  Solved: 422

[][][]

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://blog.csdn.net/werkeytom_ftd/article/details/50975467

感觉是非常神的做法

建立权值线段树，每个位置i保存数字i出现的最右端

查询[l,r]，就是找第r棵前缀线段树中第一个值<l的

维护区间最小值就可以做到了

 

////  main.cpp//  bzoj3585////  Created by Candy on 2017/1/28.//  Copyright © 2017年 Candy. All rights reserved.//#include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define lc(x) t[x].l#define rc(x) t[x].rconst int N=2e5+5,MX=1e8+5;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){
    if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int n,Q,a[N],l,r;struct node{    int l,r,mn;}t[N*30];int sz,root[N];void ins(int &x,int l,int r,int p,int v){
    //right of p is v    t[++sz]=t[x];x=sz;    if(l==r) t[x].mn=v;    else{        int mid=(l+r)>>1;        if(p<=mid) ins(t[x].l,l,mid,p,v);        else ins(t[x].r,mid+1,r,p,v);        t[x].mn=min(t[lc(x)].mn,t[rc(x)].mn);    }}int query(int x,int l,int r,int v){    if(l==r) return l;    else{        int mid=(l+r)>>1;        if(t[lc(x)].mn