CodeForces - 1436E（思维、线段树）

[题目链接](https://vjudge.net/problem/CodeForces-1436E) ------------ ------------ ```cpp #include <bits/stdc++.h> using namespace std; const int M=1e5+5; int n,last[M],ans[M]; struct d { int l,r,mn; #define ls i<<1 #define rs i<<1|1 #define mid (tree[i].l+tree[i].r)/2 }tree[M*4]; void build(int i,int l,int r) { tree[i].l=l;tree[i].r=r; if(l==r)return ; build(ls,l,mid); build(rs,mid+1,r); } void upd(int i,int pos,int x) { if(tree[i].l==tree[i].r) { tree[i].mn=x; return ; } if(pos<=mid)upd(ls,pos,x); else upd(rs,pos,x); tree[i].mn=min(tree[ls].mn,tree[rs].mn); } int que(int i,int l,int r) { if(tree[i].l==l&&tree[i].r==r)return tree[i].mn; if(r<=mid)return que(ls,l,r); else if(l>mid)return que(rs,l,r); else return min(que(ls,l,mid),que(rs,mid+1,r)); } int main() { scanf("%d",&n); build(1,1,n); for(int i=1;i<=n;i++) { int x;scanf("%d",&x); upd(1,x,i); if(x!=1)ans[1]=1; else continue; int k=que(1,1,x-1); if(k>last[x])ans[x]=1; last[x]=i; } for(int i=2;i<=n+1;i++) { int k=que(1,1,i-1); if(k>last[i])ans[i]=1; } int fnl=0; for(int i=1;i<=n+2;i++)if(!ans[i]){fnl=i;break;} printf("%d\n",fnl); return 0; } ```