题解 P4137 【Rmq Problem / mex】

一叶知秋。 · 2020-02-06 15:45:19 · 题解

本题难是不难，只是有点非常卡常数啊啊啊

一不小心就一两版qwq（人丑常数大也有可能）

回滚莫队？不存在的，直接莫队+值域分块即可

快读写强点，块大小别用sqrt，用pow貌似快一些

还有块大小开成n^{0.55}+1貌似会快一些，不要问我怎么知道的

离散化当然不用了，答案最大就n+1，读者自证不难

贴代码：

#include<cstdio>
#include<cmath>
#include<cctype>
#include<algorithm>

using namespace std;

#define maxn 200022

inline int read(){
    int r=0;
    char c=getchar();
    while(!isdigit(c))c=getchar();
    while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
    return r;
}

inline int min(int a,int b){
    return a<b?a:b;
}

int n,m,l,r,size,a[maxn],lb[maxn],rb[maxn],pos[maxn],cnt[maxn],tot[maxn],ans[maxn];

struct Q{
    int l,r,num;
    bool operator <(const Q &q) const{
        return pos[l]^pos[q.l]?pos[l]<pos[q.l]:r<q.r;
    }
}q[maxn];

inline void add(int x){
    if(!cnt[a[x]])tot[pos[a[x]]]++;
    cnt[a[x]]++;
}

inline void del(int x){
    cnt[a[x]]--;
    if(!cnt[a[x]])tot[pos[a[x]]]--;
}

inline int query(){
    for(int i=1;i<=pos[n];i++){
        if(tot[i]==rb[i]-lb[i]+1)continue;
        for(int j=lb[i];j<=rb[i];j++)
            if(!cnt[j])return j;
    }
    return n;
}

int main(){
    n=read(),m=read();
    size=pow(n+2,0.5);
    for(int i=1;i<=n;i++){
        pos[i]=(i-1)/size+1;//值域反正是0~n+1，同时+1，用同一个块大小
        a[i]=min(read()+1,n+2);
    }
    pos[n+1]=n/size+1;
    pos[n+2]=(n+1)/size+1;
    n+=2;
    for(int i=1;i<=pos[n];i++){
        lb[i]=(i-1)*size+1;
        rb[i]=min(lb[i]+size-1,n);
    }
    for(int i=1;i<=m;i++){
        q[i].l=read(),q[i].r=read();
        q[i].num=i;
    }
    sort(q+1,q+m+1);
    l=q[1].l,r=q[1].l-1;
    for(int i=1;i<=m;i++){
        while(l>q[i].l)add(--l);
        while(r<q[i].r)add(++r);
        while(l<q[i].l)del(l++);
        while(r>q[i].r)del(r--);
        ans[q[i].num]=query()-1;
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}