题解 P4137 【Rmq Problem / mex】

· · 题解

先吐嘈一下

楼下大佬的方法貌似比较难啊，可惜我太cai了看不懂，就只好用了个分块，算是比较易懂的暴力吧

题解

想必同学们都是刷莫队的时候不小心刷到这题的 主要考虑怎么修改和查询 类似值域线段树的思想，将值域O(0,K) 进行分块，查询时先遍历所有的块，如果某个块非空那么查询该块，当查询到一个数字为空时，即可break输出答案，复杂度为O(\sqrt k+\sqrt k)，修改时要注意判断块的信息

1.增加一个数时，如果该数为空，则要将该数所在块的元素个数和该数的个数都+1，否则只将该数的个数+1

2.删除一个数时，如果该数删除后为空，则要将该数所在块的元素个数和该数的个数都-1，否则只将该数的个数-1

细节： 考虑到最坏情况下的区间是(0,1,2,3,......N-1) 因此最大答案也是N，所以A_i>=1e9是用来搞笑的，将所有大于等于N+1的数修改为N+1就可以了

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int _=200005;
const int K=448;
inline int read()
{
    char ch='!';int z=1,num=0;
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')z=-1,ch=getchar();
    while(ch<='9'&&ch>='0')num=(num<<3)+(num<<1)+ch-'0',ch=getchar();
    return z*num;
}
int n,m,kuai[_],a[_];
struct hand{int l,r,id;}ask[_];
bool cmp(hand A,hand B)
{
    if(kuai[A.l]==kuai[B.l])return A.r<B.r;
    return kuai[A.l]<kuai[B.l];
}
int num[500],cnt[_],ans[_];
void add(int x)
{
    if(!cnt[x])num[x/K]++;
    cnt[x]++;
}
void del(int x)
{
    if(cnt[x]==1)num[x/K]--;
    cnt[x]--;
}
void Query(int x)
{
    for(int i=1;i<=K;i++)
    {
        if(num[i-1]!=K)
        {
            for(int j=(i-1)*K;j<i*K;j++)
            {
                if(!cnt[j])
                {
                    ans[ask[x].id]=j;return;
                }
            }
        }
    }
}
int main()
{
    n=read();m=read();
    int len=sqrt(n);
    for(int i=1;i<=n;i++)
    {
        a[i]=min(read(),n+1);
        kuai[i]=(i-1)/len+1;
    }
    for(int i=1;i<=m;i++)
        ask[i].l=read(),ask[i].r=read(),ask[i].id=i;
    sort(ask+1,ask+1+m,cmp);
    int l=ask[1].l,r=ask[1].r;
    for(int i=l;i<=r;i++)
        add(a[i]);
    Query(1);
    for(int i=2;i<=m;i++)
    {
        while(l<ask[i].l)del(a[l++]);
        while(l>ask[i].l)add(a[--l]);
        while(r<ask[i].r)add(a[++r]);
        while(r>ask[i].r)del(a[r--]);
        Query(i);
    }
    for(int i=1;i<=m;i++)
        printf("%d\n",ans[i]);
    return 0;
}