CF传送门
洛谷传送门
解题思路
考虑什么情况数字 (i) 会出现在所有连续子数列的 (mex) 值中：
当且仅当两个 (i) 之间包含了 (1 o (i-1)) 的全部数字。
假设我们已经判断出两个 (i) 之间包含了 (1 o (i-1)) 的全部数字，这时使得 (vis[i]=1)，最后找到最小的 (vis[i]=0) 的数字即是最终答案。
如何判断呢？
可以用线段树来维护信息，原数组 (x[i]) 表示数字 (i) 最后出现的位置，线段树维护区间最小值即可。
注意数字1要单独处理，并且最后要判断一下后缀是否满足条件（见代码 53-55 行）
AC代码
#include<cstdio>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn=100005;
int n,a[maxn],d[maxn*4],ans,vis[maxn];
int query(int id,int l,int r,int x,int y){
if(x>y){
vis[2]=1;
return 0;
}
if(l>=x&&r<=y) return d[id];
int mid=(l+r)/2,res=maxn;
if(x<=mid) res=min(res,query(id*2,l,mid,x,y));
if(y>mid) res=min(res,query(id*2+1,mid+1,r,x,y));
return res;
}
void update(int id,int l,int r,int x,int v){
if(l==r){
d[id]=v;
return;
}
int mid=(l+r)/2;
if(x<=mid) update(id*2,l,mid,x,v);
else update(id*2+1,mid+1,r,x,v);
d[id]=min(d[id*2],d[id*2+1]);
}
int main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
if(a[i]>1) vis[1]=1;
}
for(int i=1;i<=n;i++){
if(query(1,1,n,1,a[i]-1)>query(1,1,n,a[i],a[i])) vis[a[i]]=1;
update(1,1,n,a[i],i);
}
for(int i=2;i<=n+1;i++){
if(query(1,1,n,1,i-1)>query(1,1,n,i,i)) vis[i]=1;
}
for(int i=1;i<=n+2;i++){
if(!vis[i]){
cout<<i<<endl;
return 0;
}
}
return 0;
}