很自然地，枚举 \(i\)，若是存在某个子列，\([1,i-1]\) 都存在，且 \(i\) 不存在，那么 \(i\) 就不可能是答案。
又因为子列越长越好，那么肯定是以 \(a[j]=a[k]=i\) 时 \((j,k)\) 最优。
于是问题转化为区间 mex。
Sol1
区间 mex 很难支持区间合并。那么很自然想到莫队。
那么只需要对移动用树状数组维护桶的前缀和，对询问二分查找即可。
时间复杂度 \(O(N\sqrt N \log N+N \log ^2 N)\)
Sol2
发现复杂度不平衡，那么优化掉树状数组，改用分块维护桶。
即移动时单点修改加单块更新，查询时一块一块跳。
时间复杂度 \(O(N\sqrt N)\)
Sol3
实际上也没必要用桶，直接用链表，让 mex 每次都跳至合法。增加点时用链表合并，减少时直接原样撤回（需要记录每次增加前的数据）
时间复杂度 \(O(N\sqrt N)\)
Sol4
实际上是很老的板子了。
我们发现，若 \([l,r]\) 中所有 \([1,i-1]\) 都有出现，那么相当于 \([1,i-1]\) 所有数最后出现的位置都得在 \(l\) 右边（包含 \(l\)）。
那么用主席树维护考虑下标 \(1~r\) ，\(1~i\) 个数中最右位置的最小值即可。
当然离线后直接用线段树也可以。（差别只在空间吧）
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int a[N],las[N];
struct seg{
int ls,rs,minn;
}t[N*20];
int tot,rt[N];
//t[0]
int change(int p,int q,int l,int r,int tl){
t[p]=t[q];
if(l==r){
t[p].minn=las[tl];
return p;
}
int mid=(l+r)>>1;
if(tl<=mid)t[p].ls=change(++tot,t[q].ls,l,mid,tl);
else t[p].rs=change(++tot,t[q].rs,mid+1,r,tl);
t[p].minn=min(t[t[p].ls].minn,t[t[p].rs].minn);
return p;
}
int ask(int p,int l,int r,int tr){
if(r<=tr)return t[p].minn;
int mid=(l+r)>>1,minn=ask(t[p].ls,l,mid,tr);
if(tr>mid)minn=min(minn,ask(t[p].rs,mid+1,r,tr));
return minn;
}
int vis[N];
vector<int> pos[N];
int main(){
int n;cin>>n;
for(int i=1;i<=n;++i)cin>>a[i];
t[0].ls=t[0].rs=0;
t[0].minn=0;
for(int i=1;i<=n+1;++i)pos[i].push_back(0);
for(int i=1;i<=n;++i){
las[a[i]]=i;
rt[i]=change(++tot,rt[i-1],1,n,a[i]);
pos[a[i]].push_back(i);
if(a[i]!=1)vis[1]=1;
}
for(int i=1;i<=n+1;++i)pos[i].push_back(n+1);
for(int i=2;i<=n+1;++i){
for(int j=1;j<pos[i].size();++j){
int l=pos[i][j-1],r=pos[i][j],minn;
if(r==l+1)continue;
minn=ask(rt[r-1],1,n,i-1);
if(minn>l)vis[i]=1;
}
}
for(int i=1;i<=n+2;++i){
if(vis[i]==0){
cout<<i<<endl;
break;
}
}
return 0;
}