[BZOJ3339]Rmq Problem / mex

佚名 5年前 (2019-03-16) 算法 1915人围观抢沙发百度已收录

Description:

有一个长度为n的数组{a1,a2,…,an}。m次询问，每次询问一个区间内最小没有出现过的自然数。

Hint:

\(n \le 2*10^5\)

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

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;
}