题目大意
给定一个静态区间，有多次询问，每次询问查询一段区间 的 。（一个区间的 为最小的没有出现在这个区间的数字中的自然数）
题目大意一句话可还行
，值域与 相同。
题目分析
暴力求解
考虑到本题的数据范围整体较小，可以使用莫队进行。不带修的莫队的复杂度约为 的，但是还要乘上一个求 的复杂度。
如果我们打出这样的代码：
inline void add(int pos){
++cnt[a[pos]]; // cnt 表示这个数字出现的次数，a 是原数组
}
inline void del(int pos){
--cnt[a[pos]];
}
inline int mex(){ // O(n) 跑一遍暴力求mex
for(register int i=0;i<=max_n;++i)
if(cnt[i]<=0)
return i;
return max_n+1; // 不会超过值域，所以可以这么写
}
inline void moque(){
sort(q+1,q+1+m,cmp1); // cmp1：按照莫队的排序方法排序
int l=1,r=0;
for(register int i=1;i<=m;++i){ // 莫队板子
int ql=q[i].l,qr=q[i].r;
while(r<qr) add(++r);
while(l>ql) add(--l);
while(l<ql) del(l++);
while(r>qr) del(r--); // 莫队基操之：四个 while 整整齐齐
q[i].ans=mex(); // 更新答案
}
sort(q+1,q+1+m,cmp2); // cmp2：按照输入顺序排序
}
交到洛谷上，即使你打开了 O2，也只能得到 分的不好的成绩。最坏是 的。
因为只 T 了两个点，让我不得不想到可不可以各种优化常数。
优化即正解
先摆上莫队的基操优化，奇偶性排序：
// 分块时为根号分块，莫队基操
inline bool cmp1(que a,que b){ // idx 表示这个点所在块
if(idx[a.l]!=idx[b.l]) return idx[a.l]<idx[b.l];
if(idx[a.l]&1) return a.r<b.r;
return a.r>b.r;
}
把这个东西和上面放在一起，开 O2 才是 分……
莫队是不好再进行什么阴间优化了，而且也不难发现本题的瓶颈在于如何求 。考虑怎么优化求 的过程。
因为求 只需要知道一个数是否在这个区间里面就可以了，不关心它具体出现的次数。因此，假设用 表示这个数没出现， 表示这个数出现了，显然开一个 bool 数组不是个很聪明的选择，因此我们考虑状态压缩。我们先不管值域，假设它们都能压到一个变量上。
显然原来的 还是要保留的，因为我只有知道这个数出现多少次，才可以在这个数被删一次的时候判断它有没有出现。假设我们状态压缩的变量名字叫 。
- 显然 初始值为 。
- 如果一个数本来没有，现在新出现了，我们需要把 的第这个数那么多位（为了方便一个二进制数的最低位我们当做第 位）赋为 。
- 如果一个数本来有，现在没了，则把第这个数那么多为赋为 。
- 这段区间的 ，就是第一个 的位置是第几个。求第一个 的位置我们都不熟悉，但是如果给 取个反，那不就变成求第一个 的位置了吗？梦回树状数组，取反后直接
seg&-seg，但是注意这里我们得到的是一个状压后的二进制数（一个一后面一堆零的形式，显然它是 的自然数次幂），我们还要求出它的 是第几个。因为最好别搞太复杂了，所以直接 。
（当然 C++ 自带的 函数常数还是有一点的，但是因为我过了所以假装很小，实际上使用时一定要注意）
到这里思路就很清晰了，把一个位变成 ，可以考虑 &(~(1<<k))，变成 则是 |(1<<k)。
但是现实很骨感，并不存在一个值域范围为 的变量让你肆意挥霍。所以我们只能老老实实把它拆成若干可以用位运算方便解决的变量。C++ 里面也只有 unsigned long long 比较给力了，一个变量有 位。总的复杂度期望缩减为原来的 。
因此可以改造出如下代码：
int cnt[max_n];
unsigned long long seg[max_n]; // 前文提到的状压变量，现在变成数组了
inline void add(int pos){
if(!cnt[a[pos]]){ // 本来没有，现在加进去
int x=a[pos]; // x/64 为下标，x%64 为这个下标的 seg 的第几位
unsigned long long y=x%64;
seg[x/64]|=(1ULL<<y);
}
++cnt[a[pos]];
}
inline void del(int pos){ // 和 add 基本一致
--cnt[a[pos]];
if(!cnt[a[pos]]){
int x=a[pos];
unsigned long long y=x%64;
seg[x/64]&=(~(1ULL<<y));
}
}
inline int mex(){
for(register int i=0;i<=max_n;++i){ // 先顺序查找哪个 seg
unsigned long long tmp=(~seg[i]); // 不要忘记先取反再 lowbit
// 如果取反后是 0,说明这个 seg 全是 1，mex 不在这个 seg 里，直接过掉
if(tmp){
unsigned long long k=(tmp&-tmp);
// 取 lowbit，这是得到的二进制数，需要还原
return i*64+(int)log2(k); // 还原，这个式子一拍脑袋就知道
}
}
return -1;
}
代码与效率
代码
总的代码如下，因为主体部分已经在前面写到并且加注释了，因此放的是清爽无注释版本：
#include<bits/stdc++.h>
using namespace std;
const int max_n=200005;
inline int read(){
int x=0;bool w=0;char c=getchar();
while(c<'0' || c>'9') w|=c=='-',c=getchar();
while(c>='0' && c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
return w?-x:x;
}
inline void write(int x){
if(x<0) x=-x,putchar('-');
if(x>9) write(x/10);
putchar(x%10^48);
}
int n,m,a[max_n];
struct que{
int l,r,id,ans;
inline void init(int _l,int _r,int _id){
l=_l,
r=_r,
id=_id;
ans=0;
}
}q[max_n];
int idx[max_n];
inline bool cmp1(que a,que b){
if(idx[a.l]!=idx[b.l]) return idx[a.l]<idx[b.l];
if(idx[a.l]&1) return a.r<b.r;
return a.r>b.r;
}
inline bool cmp2(que a,que b){
return a.id<b.id;
}
int cnt[max_n];
unsigned long long seg[max_n];
inline void add(int pos){
if(!cnt[a[pos]]){
int x=a[pos];
unsigned long long y=x%64;
seg[x/64]|=(1ULL<<y);
}
++cnt[a[pos]];
}
inline void del(int pos){
--cnt[a[pos]];
if(!cnt[a[pos]]){
int x=a[pos];
unsigned long long y=x%64;
seg[x/64]&=(~(1ULL<<y));
}
}
inline int mex(){
for(register int i=0;i<=max_n;++i){
unsigned long long tmp=(~seg[i]);
if(tmp){
unsigned long long k=(tmp&-tmp);
return i*64+(int)log2(k);
}
}
return -1;
}
inline void moque(){
sort(q+1,q+1+m,cmp1);
int l=1,r=0;
for(register int i=1;i<=m;++i){
int ql=q[i].l,qr=q[i].r;
while(r<qr) add(++r);
while(l>ql) add(--l);
while(l<ql) del(l++);
while(r>qr) del(r--);
q[i].ans=mex();
}
sort(q+1,q+1+m,cmp2);
}
signed main(){
n=read(),m=read();
for(register int i=1;i<=n;++i)
a[i]=read();
for(register int i=1;i<=m;++i){
int l=read(),r=read();
q[i].init(l,r,i);
}
int sq=sqrt(n);
for(register int i=1;i<=n;++i) idx[i]=i/sq+1;
moque();
for(register int i=1;i<=m;++i)
write(q[i].ans),putchar('\n');
return 0;
}
实际效率
时间复杂度是 （最坏还是 T，本来想写 bitset，后来觉得算了别搞那么麻烦，最后居然过了，不知是我常数小还是这题数据弱），空间复杂度是 。
实际在洛谷评测机上跑的时候感觉还挺快（两份的代码完全一致，都是莫队+状压）：
可以发现本来只是一个图运气的常数优化，效果居然如此显著。开 O2 版本在写博客的时候在最优解的第五页（接近末尾了，因此各位看到时估计掉到后面去很多了，毕竟大部分写的都是莫队+值域分块，甚至效率更高的权值线段树），虽然算不上很快但是已经不慢了，比我的期望高多了。
