题解 P4137 【Rmq Problem / mex】

· · 题解

看到没有莫队+离散化的做法，我来水一发

首先，我们对原数组进行排序、去重、二分，即离散化，并把离散化用的辅助数组存下来，记为lsh。

和普通做法类似，莫队删除时直接对ans取min。加入的时候，如果符合当前删除的是答案，O(n)枚举合法数字，寻找ans。当我们发现一个数x出现过时，询问的区间中，x+1没有出现，答案就是x+1。

所以当我们遇到一个在询问区间里出现过的数 lsh_i 时，判断lsh数组中下一个数字 lsh_{i+1}，也就是在所有数字中大于当前数的第一个数，是否出现，如果出现，那么是否紧跟着lsh_i。如果以上条件不满足，那么lsh_i后面就没有紧跟着的数字，答案就是该数字+1。

讲起来可能有点乱，上核心代码

/*注意，由于a是离散化后的数组，a里存的数字相当于
原数组的相对大小，也就是lsh数组的下标*/
inline void add(int x)
{
    if(++cnt[a[x]]==1)
    {
        if(ans==lsh[a[x]])//同普通做法
        {
            for(int i=a[x];i<=len;i++)//在离散化数组里寻找答案 
                if(cnt[i])//我们需要的是在当前区间里出现的数，因为答案要么是0，要么紧跟在区间中出现的数字后面
                    if(!(lsh[i]+1==lsh[i+1]&&cnt[i+1]))//判断这一位后面有没有紧跟的数字 
                    {
                        ans=lsh[i]+1;
                        return;
                    }
        }
    }
}

完整代码

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
using namespace std;
const int N=200005;

#define dd ch=getchar()
inline int read()
{
    int x=0;bool f=false;char dd;
    while(!isdigit(ch)){f|=ch=='-';dd;}
    while(isdigit(ch)){x=(x<<1)+(x<<3)+ch-48;dd;}
    return f?-x:x;
}
#undef dd
void write(int x)
{
    if(x<0)putchar('-'),x=-x;
    if(x>9)write(x/10);
    putchar(x%10+48);
}

int n,m,a[N];
int res[N];

int belong[N];
inline void fuck(const int lim)
{
    int size=pow(lim,0.5);
    for(int i=1;i<=lim;i++)
        belong[i]=(i-1)/size+1;
}

int lsh[N];
int cnt[N];
int ans=0,len;

struct node
{
    int l,r,id;
}q[N];
inline bool cmp(node x,node y){return belong[x.l]^belong[y.l]?belong[x.l]<belong[y.l]:x.r<y.r;}

inline void add(int x)
{
    if(++cnt[a[x]]==1)
    {
        if(ans==lsh[a[x]])
        {
            for(int i=a[x];i<=len;i++)
                if(cnt[i])
                    if(!(lsh[i]+1==lsh[i+1]&&cnt[i+1]))
                    {
                        ans=lsh[i]+1;
                        return;
                    }
        }
    }
}
inline void del(int x)
{
    if(--cnt[a[x]]==0)
        ans=min(ans,lsh[a[x]]);
}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        a[i]=lsh[i]=read();
    sort(lsh+1,lsh+1+n);
    len=unique(lsh+1,lsh+1+n)-lsh-1;
    for(int i=1;i<=n;i++)
        a[i]=lower_bound(lsh+1,lsh+1+len,a[i])-lsh;

    fuck(n);
    for(int i=1;i<=m;i++)
        q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+1+m,cmp);

    int l=1,r=0;
    for(int i=1;i<=m;i++)
    {
        int ql=q[i].l,qr=q[i].r;
        while(l<ql)del(l++);
        while(l>ql)add(--l);
        while(r<qr)add(++r);
        while(r>qr)del(r--);
        res[q[i].id]=ans;
    }
    for(int i=1;i<=m;i++)
        write(res[i]),puts("");
    return 0;
}