3585: mex
Time Limit: 20 Sec Memory Limit: 128 MB
Submit: 787 Solved: 422
[Submit][Status][Discuss]
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
2 1 0 2 1
3 3
2 3
2 4
1 2
3 5
Sample Output
1
2
3
0
3
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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define lc(x) t[x].l
#define rc(x) t[x].r
const int N=2e5+,MX=1e8+;
inline int read(){
char c=getchar();int x=,f=;
while(c<''||c>''){if(c=='-')f=-;c=getchar();}
while(c>=''&&c<=''){x=x*+c-'';c=getchar();}
return x*f;
}
int n,Q,a[N],l,r;
struct node{
int l,r,mn;
}t[N*];
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)>>;
if(p<=mid) ins(t[x].l,l,mid,p,v);
else ins(t[x].r,mid+,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)>>;
if(t[lc(x)].mn<v) return query(t[x].l,l,mid,v);
else return query(t[x].r,mid+,r,v);
}
}
int main(int argc, const char * argv[]) {
n=read();Q=read();
for(int i=;i<=n;i++) a[i]=read(),root[i]=root[i-],ins(root[i],,MX,a[i],i);
while(Q--){
l=read();r=read();
printf("%d\n",query(root[r],,MX,l));
}
return ;
}