BZOJ 3339: Rmq Problem 莫队算法

3339: Rmq Problem

题目连接：

http://www.lydsy.com/JudgeOnline/problem.php?id=3339

Description

n个数，m次询问l，r。查询区间mex是什么．

Input

Output

Sample Input

7 5

0 2 1 0 1 3 2

1 3

2 3

1 4

3 6

2 7

Sample Output

3

0

3

2

4

Hint

题意

题解：

莫队算法水题

直接暴力搞就行了

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1000005;

inline int read()

{

    int x=0,f=1;char ch=getchar();

    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

int a[maxn],pos[maxn],c[maxn],Ans[maxn];

int ans,n,m;

struct query

{

    int l,r,id;

}Q[maxn];

bool cmp(query a,query b)

{

    if(pos[a.l]==pos[b.l])

        return a.r<b.r;

    return pos[a.l]<pos[b.l];

}

void Update(int x)

{

    c[x]++;

    if(ans==x)

        while(c[ans])

            ans++;

}

void Delete(int x)

{

    c[x]--;

    if(c[x]==0&&x<ans)ans=x;

}

int main()

{

    n=read(),m=read();

    int sz =ceil(sqrt(1.0*n));

    for(int i=1;i<=n;i++)

    {

        a[i]=read();

        pos[i]=(i-1)/sz;

    }

    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;ans=0;

    for(int i=1;i<=m;i++)

    {

        int id = Q[i].id;

        while(R<Q[i].r)R++,Update(a[R]);

        while(L>Q[i].l)L--,Update(a[L]);

        while(R>Q[i].r)Delete(a[R]),R--;

        while(L<Q[i].l)Delete(a[L]),L++;

        Ans[id]=ans;

    }

    for(int i=1;i<=m;i++)

        printf("%d\n",Ans[i]);

}