题目链接：BZOJ - 3585
题目分析
区间mex，即区间中没有出现的最小自然数。
那么我们使用一种莫队+分块的做法，使用莫队维护当前区间的每个数字的出现次数。
然后求mex用分块，将权值分块（显然mex 一定小于等于 n ，大于 n 的权值没有意义，可以直接忽略），每块大小 sqrt(n) 。
然后区间中的某个数的数量被减到0的时候就将它所在的块的种类计数减一，添加数的时候类似。
然后枚举每个块，找到最小的中间有数不存在的块（即种类数小于块中的数的种数），然后到这个快里直接从小一个一个找到第一个不存在的数。
这样莫队的复杂度和分块的复杂度是相加的， O(n^1.5) + O(n^1.5) = O(n^1.5) 。
代码
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm> using namespace std; const int MaxN = 200000 + 5, MaxQ = 200000 + 5, MaxB = 500 + 5; int n, m, BlkSize, MaxBlk;
int A[MaxN], Blk[MaxN], L[MaxB], R[MaxB], Ans[MaxQ], Cnt[MaxN], V[MaxB], Size[MaxB]; struct Query
{
int Idx, l, r, v;
} Q[MaxQ]; inline bool Cmp(Query q1, Query q2)
{
if (q1.v == q2.v) return q1.r < q2.r;
return q1.v < q2.v;
} inline void Del_Num(int x)
{
--Cnt[x];
if (Cnt[x] == 0) --V[Blk[x]];
} inline void Add_Num(int x)
{
if (Cnt[x] == 0) ++V[Blk[x]];
++Cnt[x];
} void Pull(int f, int x, int y)
{
if (x == y) return;
if (f == 0)
{
if (x < y)
{
for (int i = x; i < y; ++i)
Del_Num(A[i]);
}
else
{
for (int i = x - 1; i >= y; --i)
Add_Num(A[i]);
}
}
else
{
if (x < y)
{
for (int i = x + 1; i <= y; ++i)
Add_Num(A[i]);
}
else
{
for (int i = x; i > y; --i)
Del_Num(A[i]);
}
}
} int Get_Ans()
{
int ret = n;
for (int i = 1; i <= MaxBlk; ++i)
if (V[i] < Size[i])
{
for (int j = L[i]; j <= R[i]; ++j)
if (Cnt[j] == 0)
{
ret = j;
break;
}
break;
}
return ret;
} int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i)
{
scanf("%d", &A[i]);
if (A[i] > n) A[i] = n + 1;
}
BlkSize = (int)sqrt((double)n);
for (int i = 0; i <= n; ++i) Blk[i] = i / BlkSize + 1;
MaxBlk = Blk[n];
for (int i = 1; i <= MaxBlk; ++i)
{
L[i] = (i - 1) * BlkSize;
R[i] = i * BlkSize - 1;
Size[i] = R[i] - L[i] + 1;
}
R[MaxBlk] = n;
Size[MaxBlk] = n - L[MaxBlk] + 1;
for (int i = 1; i <= m; ++i)
{
scanf("%d%d", &Q[i].l, &Q[i].r);
Q[i].Idx = i;
Q[i].v = Q[i].l / BlkSize;
}
sort(Q + 1, Q + m + 1, Cmp);
for (int i = Q[1].l; i <= Q[1].r; ++i) Add_Num(A[i]);
Ans[Q[1].Idx] = Get_Ans();
for (int i = 2; i <= m; ++i)
{
if (Q[i].r <= Q[i - 1].l)
{
Pull(0, Q[i - 1].l, Q[i].l);
Pull(1, Q[i - 1].r, Q[i].r);
}
else
{
Pull(1, Q[i - 1].r, Q[i].r);
Pull(0, Q[i - 1].l, Q[i].l);
}
Ans[Q[i].Idx] = Get_Ans();
}
for (int i = 1; i <= m; ++i) printf("%d\n", Ans[i]);
return 0;
}