Description:

有一个长度为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;

}