HUAS 1483 mex(莫队算法)

考虑莫队算法，对于区间减小的情况，可以O(1)解决。对于区间增加的情况，可能需要O(n)解决。好在数据不卡莫队。

1200ms过了。

离线+线段树 760ms过了。

# include <cstdio>
# include <cstring>
# include <cstdlib>
# include <iostream>
# include <vector>
# include <queue>
# include <stack>
# include <map>
# include <set>
# include <cmath>
# include <algorithm>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi 3.1415926535
# define eps 1e-9
# define MOD 1000000009
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(int i=a; i<=n; ++i)
# define FO(i,a,n) for(int i=a; i<n; ++i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
int Scan() {
    int res=0, flag=0;
    char ch;
    if((ch=getchar())=='-') flag=1;
    else if(ch>='0'&&ch<='9') res=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')  res=res*10+(ch-'0');
    return flag?-res:res;
}
void Out(int a) {
    if(a<0) {putchar('-'); a=-a;}
    if(a>=10) Out(a/10);
    putchar(a%10+'0');
}
const int N=200005;
//Code begin...

struct Node{int l, r, l1, id;}node[N];
int a[N], ans[N], unit, q, num[N];

bool comp(Node a, Node b){
    if (a.l1!=b.l1) return a.l1<b.l1;
    return a.r<b.r;
}
void sol(){
    int tmp=0, l=1, r=0;
    FOR(i,1,q) {
        while (r<node[i].r) {
            ++r; ++num[a[r]];
            if (a[r]!=tmp) continue;
            for (int now=tmp+1; ; ++now) if (!num[now]) {tmp=now; break;}
        }
        while (r>node[i].r) {
            --num[a[r]];
            if (a[r]<tmp&&!num[a[r]]) tmp=a[r];
            --r;
        }
        while (l<node[i].l) {
            --num[a[l]];
            if (a[l]<tmp&&!num[a[l]]) tmp=a[l];
            ++l;
        }
        while (l>node[i].l) {
            --l; ++num[a[l]];
            if (a[l]!=tmp) continue;
            for (int now=tmp+1; ; ++now) if (!num[now]) {tmp=now; break;}
        }
        ans[node[i].id]=tmp;
    }
}
int main ()
{
    int n;
    n=Scan(); q=Scan();
    unit=(int)sqrt(n);
    FOR(i,1,n) a[i]=Scan();
    FOR(i,1,q) node[i].l=Scan(), node[i].r=Scan(), node[i].id=i, node[i].l1=node[i].l/unit;
    sort(node+1,node+q+1,comp);
    sol();
    FOR(i,1,q) Out(ans[i]), putchar('
');
    return 0;
}