有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。
Hint:\(n \le 2*10^5\)
Solution:把坐标离散化
不同于维护\(size\),这里用线段树维护以一个区间所有数的最后出现位置的最小值
这样我们每次直接在以\(r\)为根的值域线段树上找最小的\(val<l\)的数
// luogu-judger-enable-o2 #include <map> #include <set> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; const int mxn=8e6+100,mxm=1e7+5; int n,m,s,p,cnt,tot,a[mxn],b[mxn],rt[mxm],tr[mxm],ls[mxm],rs[mxn]; inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f; } inline int chkmax(int &x,int y) {if(x<y) x=y;} inline int chkmin(int &x,int y) {if(x>y) x=y;} struct ed { int to,nxt; }t[mxn<<1]; void update(int las,int &p,int l,int r,int val,int pos) { if(!p) p=++cnt; if(l==r) {tr[p]=val;return ;} int mid=(l+r)>>1; if(pos<=mid) update(ls[las],ls[p],l,mid,val,pos),rs[p]=rs[las]; else update(rs[las],rs[p],mid+1,r,val,pos),ls[p]=ls[las]; tr[p]=min(tr[ls[p]],tr[rs[p]]); } int query(int p,int l,int r,int pos) { if((p == 0) or (l==r)) return b[l]; int mid=(l+r)>>1; if(tr[ls[p]]>=pos) return query(rs[p],mid+1,r,pos); else return query(ls[p],l,mid,pos); } int main() { n=read(); m=read(); int l,r; b[++tot]=0; for(int i=1;i<=n;++i) a[i]=read(),b[++tot]=a[i],b[++tot]=a[i]+1; sort(b+1,b+tot+1); s=unique(b+1,b+tot+1)-b-1; for(int i=1;i<=n;++i) a[i]=lower_bound(b+1,b+s+1,a[i])-b; for(int i=1;i<=n;++i) update(rt[i-1],rt[i],1,s,i,a[i]); for(int i=1;i<=m;++i) { l=read(); r=read(); printf("%d\n",query(rt[r],1,s,l)); } return 0; }常数极大的回滚莫队:
#include <map> #include <set> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const int mxn=5e5+5; int n,m,L,R,sz,num,res,a[mxn],b[mxn],bl[mxn],ans[mxn],bac[mxn]; inline int read() { char c=getchar(); int x=0,f=1; while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();} while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();} return x*f; } inline int chkmax(int &x,int y) {if(x<y) x=y;} inline int chkmin(int &x,int y) {if(x>y) x=y;} struct ed { int to,nxt; }t[mxn<<1]; struct Q { int id,l,r; }q[mxn]; int cmp(Q x,Q y) { return bl[x.l]==bl[y.l]?x.r>y.r:bl[x.l]<bl[y.l]; } void md(int x) { if(a[x]<=n) { --bac[a[x]]; if(bac[a[x]]==0) chkmin(res,a[x]); } } void solve() { int l=1,r=0,z=1; for(int i=1;i<=num;++i) { L=(i-1)*sz; R=i*sz+1; res=n+1; for(int j=0;j<=n;++j) bac[j]=0; for(int j=1;j<=n;++j) if(a[j]<=n) ++bac[a[j]]; for(int j=0;j<=n;++j) if(!bac[j]) {res=j;break;} l=-1,r=n+1; while(l<L-1) md(++l); for(;bl[q[z].l]==i;++z) { if(bl[q[z].l]==bl[q[z].r]) { for(int k=q[z].l;k<=q[z].r;++k) if(a[k]<=n) ++b[a[k]]; for(int k=0;k<=n;++k) if(!b[k]) {ans[q[z].id]=k;break;} for(int k=q[z].l;k<=q[z].r;++k) if(a[k]<=n) --b[a[k]]; continue ; } while(r-1>q[z].r) md(--r); int las=res; while(l<q[z].l-1) md(++l); while(l>=L) {if(a[l]<=n) ++bac[a[l]]; --l;} ans[q[z].id]=res; res=las; } } } int main() { n=read(); m=read(); sz=sqrt(n); int l,r; a[0]=n+1; for(int i=1;i<=n;++i) a[i]=read(),bl[i]=(i-1)/sz+1,chkmax(num,bl[i]); for(int i=1;i<=m;++i) q[i].l=read(),q[i].r=read(),q[i].id=i; sort(q+1,q+m+1,cmp); solve(); for(int i=1;i<=m;++i) printf("%d\n",ans[i]); return 0; }