Code

点击查看代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5+5;
int n,m,a[N],b[N],bs,L[N],R[N];
int ans[N],cntb;
int buk[N],mn;
struct Q{int l,r,id;}q[N];
bool cmp(Q x,Q y){return b[x.l]!=b[y.l]?b[x.l]<b[y.l]:x.r>y.r;}
inline void add(int p){if(a[p]<=n)buk[a[p]]++;}
inline void del(int p){if(a[p]<=n)buk[a[p]]--;if(a[p]<=n&&!buk[a[p]])mn=min(mn,a[p]);
}
int main(){//freopen("bijiben.in","r",stdin);//freopen("bijiben.out","w",stdout);ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n>>m;bs=sqrt(n);for(int i=1;i<=n;i++){cin>>a[i],b[i]=(i-1)/bs+1;if(!L[b[i]])L[b[i]]=i;R[b[i]]=i;}for(int i=1;i<=m;i++){cin>>q[i].l>>q[i].r;q[i].id=i;}sort(q+1,q+1+m,cmp);int l=0,r=-1;for(int i=1;i<=m;i++){int qL=q[i].l,qR=q[i].r;if(b[qL]==b[qR]){mn=0;while(l<=r)del(r--);for(int j=qL;j<=qR;j++)add(j);int res=0;for(;;res++)if(!buk[res])break;ans[q[i].id]=res;for(int j=qL;j<=qR;j++)del(j);continue;}if(b[qL]!=b[l]){while(l<=r)del(r--);l=L[b[qL]],r=n;for(int j=l;j<=r;j++)add(j);for(mn=0;;mn++)if(!buk[mn])break;}while(r>qR)del(r--);int temp=mn,orl=l;while(l<qL)del(l++);ans[q[i].id]=mn;while(l>orl)add(--l);mn=temp;}for(int i=1;i<=m;i++)cout<<ans[i]<<'\n';return 0;
}

点击查看 datamaker

//a
/*
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=20;
int n,Tmax,d[N];
int main(){srand(time(NULL));n=rand()%N+1;for(int i=1;i<=n;i++)d[i]=rand()%30+1,Tmax=max(Tmax,d[i]);Tmax+=rand()%(30*(n/5+1));printf("%d %d\n",n,Tmax);for(int i=1;i<=n;i++)printf("%d ",d[i]);printf("\n");return 0;
}
*///b#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=2e5;
int n,m;
int main(){srand(time(NULL));printf("%d %d\n",n=rand()%N+1,m=rand()%N+1);for(int i=1;i<=n;i++)printf("%d ",rand()%3);printf("\n");for(int i=1;i<=m;i++){int l=rand()%n+1,r=rand()%n+1;if(l>r)swap(l,r);printf("%d %d\n",l,r);}return 0;
}