分块&莫队

分块

首先介绍一下分块。

分块的思想很暴力，但是是有技巧的暴力。分块有时候还要靠运气和玄学。也有线段树的思想。

分块的用法：

数组：$1,2,3,3,2,1,2,3,6,2$

下标：$1,2,3,4,5,6,7,8,9,10$

现在要将区间 $[2,7]$ 求和，我们可以用线段树求区间,也可以用前缀和直接算。但这里我们用分块来做一下。

首先我们定一下每个块的长度（不一定整分总区间），例如我们定块长为 $3$，首先预处理出每个块的基础信息。
按题目要求处理。在这里，我们处理出每个区间的长度。

数组：$1,2,3,3,2,1,2,3,6,2$

下标：$1,2,3,4,5,6,7,8,9,10$（方便表示下标从 $1$ 开始）

分块：$6[1,3],6[4,6],11[7,9],2[10,12]$（所以开始时数组定义尽量要大一些）

然后我们可以知道，询问边界两个数分别属于 $1,3$ 区间，$2\in[1,3]$，$7\in[7,9]$。这时，我们可以先加上两者之间的块，就是第 $2$ 个块。接着，从询问左区间 $2$ 暴力枚举到当前块的结尾也就是原数组中下标为 $3$ 的数暴力加和（$[2,3]$）；再从询问右区间的块初枚举到询问的地方加和即可（$[7,7]$）。

和线段树的区间维护非常像，但是它没有线段树写的那么复杂，而且它比线段树的用法多一些，方便。缺点就是块长很死板。

莫队

在区间暴力优化中，经常用到分块和莫队。

莫队的优化在于对询问进行排序，然后下次询问在上次询问的基础上略作删减搞出结果，而非重新开始。什么意思呢，举个例子。

数组：$1,2,3,3,2,1,2,3,6,2$

下标：$1,2,3,4,5,6,7,8,9,10$（我们还用上边的例子）

询问区间：$[1,5],[2,6],[3,6]$ 的和。

我们可以发现在查询 $[1,5]$ 了之后，我们可以不重新开始查询 $[2,6]$，我们可以先将上一个询问存的数组处理成 $[2,5]$，在加上最后一位，就可以直接找出结果了。第三个区间同理。这里不再赘述运行原理，感兴趣的可以看看这里。

莫队很好被卡掉，比如下面的几组询问：$[1,3],[4,6],[7,10]$。它们没有交集，所以时间复杂度反而上升，但是在随机数据面前还是很好用的。

莫队+分块

没错，既然两者都是对区间优化，那么用得好就可以相辅相成。先来看道题。

P4137 Rmq Problem / mex

要找的是区间没有出现过的最小自然数，要从 $0$ 开始找。

分块询问区间

先看一下变量与常量的定义与意义。

const int o_o=200005;//数组的大小 
const int m_a=501;//块长 
int n,m;//数的个数，询问次数 
int k_k[o_o],a[o_o];//询问分块初始化，原数组 
struct po{//存询问 
  int l,r,id;//询问的走右边界和编号 
}p_p[o_o];
int n_m[501],a_s[o_o];//每个块中不同数字的个数，结果 
int b_b[o_o];//记录数出现的次数 

再来看块的预处理。

int l_n=sqrt(n);//预定块长 
for(int i=1;i<=n;i++){
    a[i]=min(r_r(),n+1);//读入原数组
    //一定比n+1小，否则一定不会被考虑到 
    k_k[i]=(i-1)/l_n+1;//初始化分块询问 
}
for(int i=1;i<=m;i++)
    p_p[i].l=r_r(),p_p[i].r=r_r(),p_p[i].id=i;//查询信息存储 
sort(p_p+1,p_p+1+m,cmp);//排序 

为什么要处理块的询问呢？

在题目中，我们可以知道可能有 $2\times10^5$ 的询问次数，而对它们全部按照普通的莫队区间排序，时间复杂度会很高，所以可以让它们先大致排序一下再处理即可。按左边界所在的块前后排序。

bool cmp(po a,po b){
    if(k_k[a.l]==k_k[b.l]){//小优化 数太多，完全排好时间过大，所以按块排，草草排个大概就可以 
      if(k_k[a.l]%2)return a.r<b.r;//奇数从小到大 
      else return a.r>b.r;//偶数从大到小 
  }
    return k_k[a.l]<k_k[b.l];//从小到大
}

其中用了一个小优化。（为了方便理解，我们用正常的莫队排序演示。）

bool cmp(po a,po b){
  if(a.l==b.l){
    if(a.l%2)return a.r<b.r;
    else return a.r>b.r;
  }
  return a.l<b.l;
}

我们用下面几组询问：$[1,2],[1,3],[1,4],[2,3],[2,4],[2,1],[3,4],[3,6]$

根据我们刚刚所说的先按左边询问排序（已排好序），但是右边我们一直没有介绍应该怎么排序。大部分都会跟左边一样从小到大这样有顺序右边界不会来回伸缩。但是，要想跟快的话，应该是分奇偶排序，比如下面这样。

$[1,2],[1,3],[1,4],[2,4],[2,3],[2,1],[3,4],[3,6]$

不难看出“奇升偶降”的规律，搜寻时进一步减少了伸缩次数。但是也可以被卡，比如左询问全奇，但是和右边也从小到大的排序效果是一样的。

莫队查询，分块统计

莫队基础操作。

//初始化莫队
  int l=p_p[1].l,r=p_p[1].r;//初始化走右边界 
  for(int i=l;i<=r;i++)a_d(a[i]);
  f_i(1);//找最小没出现的自然数 
  //初始化完毕 
  for(int i=2;i<=m;i++){//莫队操作 
      while(l<p_p[i].l)d_l(a[l++]);//左边回缩 
      while(l>p_p[i].l)a_d(a[--l]);//左边延长 
      while(r<p_p[i].r)a_d(a[++r]);//右边延长 
      while(r>p_p[i].r)d_l(a[r--]);//右边回缩 
      f_i(i);//找最小没出现的自然数 
  }

主要介绍增加，减少和查询的操作。

void a_d(int x){//增加操作 
  int k_x=x/m_a;//分块记录 
    if(!b_b[x])n_m[k_x]++;//这个块中不同的数增加 
    b_b[x]++;//记录数出现的次数 
}
void d_l(int x){//删除操作 
  int k_x=x/m_a;//分块记录 
    if(b_b[x]==1)n_m[k_x]--;//这个块中不同的数减少 
    b_b[x]--;//记录数出现的次数 
}
void f_i(int x){//查询 
    for(int i=1;i<=m_a;i++)//枚举第几个块 
        if(n_m[i-1]!=m_a)//若n_m[i-1]==m_a说明这部分块中所有的数都已经出现过了 
            for(int j=(i-1)*m_a;j<i*m_a;j++)//块长间查找 
                if(!b_b[j]){//找到结果 
                    a_s[p_p[x].id]=j;//保存结果 
                    return;
                }
}

我们统计每个块中不同的数的个数，如果数量和块长一样，那么这个块中一定没有未出现过的数，所以统计每个块中未出现过的数即可。

查询的时候，如果一个区间内不同数的数量小于块长，那么一定有未出现的数字，直接用块的两端为查找区间，暴力搜即可。

代码

#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<set>
#include<queue>
#include<vector>
#include<bitset>
#include<map> 
using namespace std;
int r_r(){//快读 
  int x=0,f=1;
  char c=getchar();
  while(!isdigit(c)){
    if(c=='-')f=-1;
    c=getchar();
  }
  while(isdigit(c)){
    x=(x<<1)+(x<<3)+(c^48);
    c=getchar();
  }
  return x*f;
}
const int o_o=200005;
const int m_a=501;//块长 
int n,m;//数的个数，询问次数 
int k_k[o_o],a[o_o];//询问分块初始化，原数组 
struct po{//存询问 
  int l,r,id;//询问的走右边界和编号 
}p_p[o_o];
bool cmp(po a,po b){
    if(k_k[a.l]==k_k[b.l]){//小优化 数太多，完全排好时间过大，所以按块排，草草排个大概就可以 
      if(k_k[a.l]%2)return a.r<b.r;//奇数从小到大 
      else return a.r>b.r;//偶数从大到小 
  }
    return k_k[a.l]<k_k[b.l];
}
int n_m[501],a_s[o_o];
int b_b[o_o];//记录数出现的次数 
void a_d(int x){//增加操作 
  int k_x=x/m_a;//分块记录 
    if(!b_b[x])n_m[k_x]++;//这个块中不同的数增加 
    b_b[x]++;//记录数出现的次数 
}
void d_l(int x){//删除操作 
  int k_x=x/m_a;//分块记录 
    if(b_b[x]==1)n_m[k_x]--;//这个块中不同的数减少 
    b_b[x]--;//记录数出现的次数 
}
void f_i(int x){
    for(int i=1;i<=m_a;i++)//枚举第几个块 
        if(n_m[i-1]!=m_a)//若n_m[i-1]==m_a说明这部分块中所有的数都已经出现过了 
            for(int j=(i-1)*m_a;j<i*m_a;j++)//块长间查找 
                if(!b_b[j]){//找到结果 
                    a_s[p_p[x].id]=j;//保存结果 
                    return;
                }
}
int main(){
    n=r_r();m=r_r();
    int l_n=sqrt(n);//预定块长 
    for(int i=1;i<=n;i++){
        a[i]=min(r_r(),n+1);//读入原数组
    //一定比n+1小，否则一定不会被考虑到 
        k_k[i]=(i-1)/l_n+1;//初始化分块询问 
    }
    for(int i=1;i<=m;i++)
        p_p[i].l=r_r(),p_p[i].r=r_r(),p_p[i].id=i;//查询信息存储 
    sort(p_p+1,p_p+1+m,cmp);//排序 
  //初始化莫队
    int l=p_p[1].l,r=p_p[1].r;//初始化走右边界 
    for(int i=l;i<=r;i++)a_d(a[i]);
    f_i(1);//找最小没出现的自然数 
    //初始化完毕 
    for(int i=2;i<=m;i++){//莫队操作 
        while(l<p_p[i].l)d_l(a[l++]);//左边回缩 
        while(l>p_p[i].l)a_d(a[--l]);//左边延长 
        while(r<p_p[i].r)a_d(a[++r]);//右边延长 
        while(r>p_p[i].r)d_l(a[r--]);//右边回缩 
        f_i(i);//找最小没出现的自然数 
    }
    for(int i=1;i<=m;i++)printf("%d\n",a_s[i]);//按询问顺序输出 
    return 0;
}