浅谈根号算法----分块

· · 个人记录

浅谈根号算法----分块

------谨以此篇纪念我可怜的分块水准

不定期更新

由于要NOIp复赛了。。。发现自己的暴力还打不好

尤其是一些非常神奇优美(玄学)的暴力非常实用233

所以最近打算学习一下分块和莫队

（也是为了好打暴力）（大雾）

这些东西我打算花3天左右的时间好好学习一下

不多说了，直接看好了

分块简介：

分块概述和大致思想：

对于一个长度为N的序列，我们可以把其中的元素分为K个连续的子序列（块），每块的长度自然就为len=N/K

如果我们要更新一段区间[l,r]，可以先更新l到l所在块的右端点(R[bel[l]])和r所在块的左端点(L[bel[r]])到r。因为每块中最多有N/K个元素，那么这一操作的复杂度的为O(N/K)；

之后我们再统一更新中间的那些整块（打标记），又因为整块最多N块，那么这一操作的复杂度为O(K)

那么修改操作的总复杂度即为O(K+N/K)

又由均值不等式可知，显然当K=sqrt(N)时，整个算法的复杂度最优

对区间查询的时候也可以按上述方法处理

由此可见，分块算法是一种通过适当的划分，预处理一些信息并保留，用空间换时间，达到时空平衡的一种算法，一般情况下均摊时间复杂度为O(sqrt(N))

分块算法中利用了均值不等式取得了算法的最优性，因此我们也可以说，分块算法是一种基于根号平衡的算法

注意：根号平衡的算法都自带二倍常数！

这也是为什么分块往往能保证正确性，但是执行的效率很低很低的原因

分块优点及比较

对于很多的数列操作问题，线段树和树状数组等数据结构都是可以实现的，其中典型的，树状数组基于二进制倍增思想，而线段树则基于分治思想。

二者之所以能非常快速、高效的处理信息和执行命令，正是因为它们都将序列中的元素分成大大小小的“段”，花费代价来维护那些成段的信息，从而可以通过这些“段”来快速合并出所有区间的信息

作为一名成熟的OIer，你肯定清楚树状数组和线段树也是有缺点的

当要求维护一些复杂的信息时（不满足区间可加可减性的信息，比如区间众数），二者处理起来显得非常吃力（代码又臭又长）。

这时，分块就显现出了优势（其实也没有多大）

分块的适用范围更广，能解决的问题更多，相对树状数组和线段树等数据结构而言更加通用和容易实现，没有所维护信息特性的限制，但是通常情况下，分块的效率往往比不上树状数组和线段树，这也是它的缺点所在

事实上，分块更接近于“朴素”，我们也可以称它是一种“优美的暴力”，几乎所有的分块都可以形容为“大块维护，小段朴素”

分块的本质：

分块的本质，其实是一颗度数为sqrt(n)，只有三层的树

如下图：

其实，第一层没有用，真正操作我们只用到了第二层和第三层

其中第二层有sqrt(n)个节点，第三层有n个节点

每次我们维护和查询信息时，只使用了第二层的整块信息和第三层的部分节点信息

更新时，自底而上更新信息

这大概就是分块的本质了

这上面的东西都很好理解吧~~~下面就来热热身好了

===============================================================

新鲜热乎的分块例题：（未完待续）

ex1：P3372 【模板】线段树 1

题目传送门：

https://www.luogu.org/problemnew/show/P3372

诶？这不是线段树题吗？为啥要用分块啊？

看我用线段树、树状数组、Splay、Theap、珂朵莉树秒切了这题！（大雾）

毕竟是在讲分块，我们不妨尝试用分块解决一下这个经典问题

不妨将整个序列A分为若干个长度不超过sqrt(n)的块，其中对于每一个块i，它的左端点是(i-1)*sqrt(n)+1，右端点是min(i*sqrt(n),n)，这样的块的总数显然为tot=sqrt(n)

（我太菜了画不出图，请脑补）

我们预处理出sum数组，其中sum[i]表示对于第i块的区间和

预处理bel数组，其中bel[i]表示序列中下标为i的元素所在的块的编号

再设tag[i]表示第i块的增量（加法）标记，显然初始tag[i]=0(1<=i<=tot)

对于指令“1 x y k”，我们有如下操作：

(1)$：若此时$x$和$y$在**同一块内，直接暴力更新**，让$A[x]$~$A[y]$全体加$k$，同时使$sum[bel[x]]+=(y-x+1)*k 1.（**整块**操作）对所有的$i∈[p+1,q-1]$，令$tag[i]+=k

2.（零散块操作）对开头和结尾两段不足一整块的部分，按照1中的方法暴力更新

那么以上这些就是修改操作

对于查询操作“2 x y”，我们有如下操作：

(1)$：若此时$x$和$y$在**同一块内，直接暴力查询**，那么此时$ans=sum(A[x]$~$A[y])+(y-x+1)*tag[bel[x]] 1.（**整块**操作）对所有的$i∈[p+1,q-1]$，令$ans+=sum[i]+tag[i]*len_i$，其中$len_i$表示第$i$块的长度，即$len_i=R[i]-L[i]+1

2.（零散块操作）对开头和结尾两段不足一整块的部分，按照1中的方法暴力查询

那么以上这些就是查询操作

综上，我们设计的分块算法采用了“整块修改用tag标记，不足整块的暴力修改”的策略。

又由于我们分块的长度和分块的个数都是O(sqrt(n))的，所以整个算法的时间复杂度维持在O((n+Q)*sqrt(n))级别

那么放一下代码

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<queue>
#include<cstring>
#define re register
using namespace std;
typedef long long ll;
const int inf=1e9+7;
inline ll read()
{
    ll p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return 1ll*f*p;}
const int maxn=100003;
int n,Q,tot,L[maxn],R[maxn],bel[maxn];
ll A[maxn],sum[maxn],tag[maxn];
inline void pre_divide()//分块 
{
    tot=sqrt(n);
    for(re int i=1;i<=tot;i++)
        L[i]=(i-1)*sqrt(n)+1,R[i]=i*sqrt(n);
    if(R[tot]<n)tot++,L[tot]=R[tot-1]+1,R[tot]=n;
    for(re int i=1;i<=tot;i++)
        for(re int j=L[i];j<=R[i];j++)
            bel[j]=i,sum[i]+=A[j];
}
inline void change(int l,int r,ll k)//给区间[l,r]加上k 
{
    int p=bel[l],q=bel[r];
    if(p==q)//同一块内暴力修改 
        {
            for(re int i=l;i<=r;i++)
                A[i]+=k;
            sum[p]+=(ll)k*(r-l+1);
            return ;
        }
    for(re int i=p+1;i<=q-1;i++)tag[i]+=k;
    //中间块不修改,打上标记 
    //维护左边残余 
    for(re int i=l;i<=R[p];i++)A[i]+=k;
    sum[p]+=(ll)k*(R[p]-l+1);
    //维护右边残余 
    for(re int i=L[q];i<=r;i++)A[i]+=k;
    sum[q]+=(ll)k*(r-L[q]+1);
}
inline ll query(int l,int r)//查询[l,r]的和 
{
    int p=bel[l],q=bel[r];
    ll ans=0;
    if(p==q)//同一块内暴力查询 
        {
            for(re int i=l;i<=r;i++)
                ans+=A[i];
            ans+=tag[p]*(r-l+1);
            return ans; 
        }
    for(re int i=p+1;i<=q-1;i++)
        ans+=sum[i]+tag[i]*(R[i]-L[i]+1);
    //整块的信息
    //左边残余 
    for(re int i=l;i<=R[p];i++)
        ans+=A[i];
    ans+=tag[p]*(R[p]-l+1);
    //右边残余 
    for(re int i=L[q];i<=r;i++)
        ans+=A[i];
    ans+=tag[q]*(r-L[q]+1);
    return ans;
}
int main()
{
    n=read(),Q=read();
    for(re int i=1;i<=n;i++)
        A[i]=read();
    pre_divide();
    while(Q--)
        {
            int flag=read();
            if(flag==1)//区间修改 
                {
                    int x=read(),y=read();
                    ll k=read();
                    change(x,y,k);
                }
            else if(flag==2)//区间查询 
                {
                    int x=read(),y=read();
                    printf("%lld\n",query(x,y));
                }
        }
    return 0;
}

突然发现。。。貌似分块跑的比线段树快？？？（大雾）

可能是我太菜了，导致线段树写的很丑，常数很大233

其实这也就是最简单的分块了

===============================================================

ex2：P2801 教主的魔法

题目传送门：

https://www.luogu.org/problemnew/show/P2801

第一眼一看。。。貌似是个线段树题

仔细想，线段树好像不能做“询问区间大于等于k的数的个数”，即使能做也很费劲实现

你可能会说：“我会树套树！”

不妨**考虑分块** 显然，有修改操作肯定是要有标记的，不妨记为$add$数组 那么类似于$ex1$，我们有如下操作： 对于指令“$M$ $L$ $R$ $W$”，我们有如下操作： $(1)$：若此时$x$和$y$在**同一块内，直接暴力更新**，让$A[x]$~$A[y]$全体加$k$，同时**暴力重构第$bel[x]$块** $(2)$：($x$和$y$**不在同一块内**)此时不妨设$x$在第$p$块，$y$在第$q$块 1.（**整块**操作）对所有的$i∈[p+1,q-1]$，令$add[i]+=k$，但是**不暴力重构** 2.（**零散块**操作）对**不足一整块的边角块$q$和$p$**，按照$1$中的方法**暴力重构** 那么以上这些就是**修改操作** 又要查询区间内$>=k$的元素的个数，怎么办呢？ 对于每块，我们可以找出每块内的元素，然后**对每块进行块内排序** 还是类似于$ex1$，考虑一下操作的左右端点 对于指令“$A$ $L$ $R$”，我们有如下操作： $(1)$：若此时$x$和$y$在**同一块内，直接暴力统计第$bel[x]$块中>=k的元素个数** $(2)$：($x$和$y$**不在同一块内**)此时不妨设$x$在第$p$块，$y$在第$q$块 1.（**整块**操作）对所有的$i∈[p+1,q-1]$的块，**在各个块内二分查找第一个满足$T[pos]+add[i]>=k$的位置，此时该块内$>=k$的元素个数即为$R[i]-pos+1$** 2.（**零散块**操作）对**不足一整块的边角块$q$和$p$**，按照$1$中的方法**暴力统计** 那么以上这些就是**查询操作** 其实还是很好理解的 下面放一下代码好了 ```cpp #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #define re register using namespace std; inline int read() { int p=0,f=1;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();} return f*p;} const int maxn=1000003; int n,Q,tot,L[maxn],R[maxn],bel[maxn],A[maxn],add[maxn],T[maxn]; inline void pre_divide()//分块 { tot=sqrt(n); for(re int i=1;i<=tot;i++) L[i]=(i-1)*sqrt(n)+1,R[i]=i*sqrt(n); if(R[tot]<n)tot++,L[tot]=R[tot-1]+1,R[tot]=n; for(re int i=1;i<=tot;i++) { for(re int j=L[i];j<=R[i];j++) bel[j]=i,T[j]=A[j]; sort(T+L[i],T+R[i]+1); } } inline void reset(int x)//暴力重构第x块 { for(re int i=L[x];i<=R[x];i++)T[i]=A[i]; sort(T+L[x],T+R[x]+1); } inline int Binary_search(int x,int val)//块内二分 { int l=L[x],r=R[x],mid,ans=0; while(l<=r) { mid=(l+r)>>1; if(T[mid]+add[x]>=val)r=mid-1,ans=R[x]-mid+1; else l=mid+1; } return ans; } inline void change(int l,int r,int k) { int p=bel[l],q=bel[r]; if(p==q)//同一块内 { for(re int i=l;i<=r;i++) A[i]+=k; reset(p); return ; } for(re int i=p+1;i<=q-1;i++)add[i]+=k;//中间整块标记 for(re int i=l;i<=R[p];i++)A[i]+=k; reset(p);//暴力重构左边角块 for(re int i=L[q];i<=r;i++)A[i]+=k; reset(q);//暴力重构右边角块 } inline int query(int l,int r,int k) { int p=bel[l],q=bel[r],ans=0; if(p==q)//同一块内 { for(re int i=l;i<=r;i++) if(A[i]+add[p]>=k)ans++; return ans; } for(re int i=l;i<=R[p];i++)//左边零散暴力 if(A[i]+add[p]>=k)ans++; for(re int i=L[q];i<=r;i++)//右边零散暴力 if(A[i]+add[q]>=k)ans++; for(re int i=p+1;i<=q-1;i++)//中间整块二分 ans+=Binary_search(i,k); return ans; } int main() { n=read(),Q=read(); for(re int i=1;i<=n;i++) A[i]=read(); pre_divide(); while(Q--) { char s[3]; scanf("%s",s); if(s[0]=='M')//区间修改 { int x=read(),y=read(),k=read(); change(x,y,k); } else if(s[0]=='A')//区间查询>=k的数的个数 { int x=read(),y=read(),k=read(); printf("%d\n",query(x,y,k)); } } return 0; } ``` 其实可以发现，分块算法不仅仅是一种优美的暴力，更需要在暴力的基础上运用优化暴力的策略，例如本题中**块内二分**的操作，正属于十分常用的技巧，要多多积累 =============================================================== ### ex3：P3203 [HNOI2010]弹飞绵羊 题目传送门： https://www.luogu.org/problemnew/show/P3203 看完题发现，这题还是挺有意思的，做法很有趣 不过。。。貌似这不是一道分块题？ 看起来题目中说的那些弹射装置之间是有联系的，这就让我们感到很玄妙 其实，这题还是可以分块来做 我们把整个序列分成$tot=sqrt(n)$块，每块都可以**预处理**其中每个装置能弹射的次数$step$和最终弹射到的位置$to$（**倒着预处理**），这个预处理显然是$O(n)$的 对于**每次修改**操作，都是对于某一块内的**单点修改**，**直接暴力重构该块内的点，重新更新每个点的$step$和$to$值** 对于**每次查询**操作，我们**直接暴力从该点向后"弹"，累加步数**即可 注意坑点：每个装置的编号从$0$开始，注意操作下标$x+1

分块看起来很好想对吧？其实实现起来也是很简单的，代码如下：

#include<iostream>
#include<cstdio>
#include<cmath>
#define re register
using namespace std;
inline int read()
{
    int p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return f*p;}
const int maxn=200003;
int n,Q,tot,L[maxn],R[maxn],bel[maxn],A[maxn],to[maxn],step[maxn];
inline void pre_divide()//分块 
{
    tot=sqrt(n);
    for(re int i=1;i<=tot;i++)
        L[i]=(i-1)*sqrt(n)+1,R[i]=i*sqrt(n);
    if(R[tot]<n)tot++,L[tot]=R[tot-1]+1,R[tot]=n;
    for(re int i=tot;i>=1;i--)//预处理每个点能到达的点和能走的步数 
        for(re int j=R[i];j>=L[i];j--)
            {
                bel[j]=i,to[j]=j+A[j];
                if(to[j]>R[i])step[j]=1;
                else step[j]=step[to[j]]+1,to[j]=to[to[j]];
            }
}
inline void change(int x,int k,int p=0)//单点修改 
{
    A[x]=k,p=bel[x];
    for(re int i=R[p];i>=L[p];i--)
        {
            to[i]=i+A[i];
            if(to[i]>R[p])step[i]=1;
            else step[i]=step[to[i]]+1,to[i]=to[to[i]];
        }
}
inline int query(int x,int ans=0)//暴力向后弹 
{
    for(;x<=n;x=to[x])ans+=step[x];
    return ans;
}
int main()
{
    n=read();
    for(re int i=1;i<=n;i++)
        A[i]=read();
    pre_divide();
    Q=read();
    while(Q--)
        {
            int flag=read();
            if(flag==1)
                {
                    int x=read()+1;
                    printf("%d\n",query(x));
                }
            else if(flag==2)
                {
                    int x=read()+1,k=read();
                    change(x,k);
                }
        }
    return 0;
}

以上就是分块的做法了

但其实，本题的std貌似不是分块，而是LCT(line-cut-tree)

我太菜了不会写LCT还是用分块解法好了（大雾）

时间复杂度分析：

本题中，分块预处理的时间复杂度为O(n)，每次操作的复杂度均为O(sqrt(n))

那么总复杂度为O(n+Q*sqrt(n))，解决本题还是绰绰有余的

===============================================================

ex4：P4168 [Violet]蒲公英

题目传送门：

https://www.luogu.org/problemnew/show/P4168

一道神仙毒瘤题，终于写完了

真的是一道挺好的分块模板（水）题，还是可以做一做的

（感觉又占了一道黑题的便宜）（大雾）

这题算得上是一道典型的在线区间众数问题了

题意很简单，给定一个序列，求区间众数，强制在线

可能有人说：我会线段树、树状数组、Splay、Theap、珂朵莉树^&$@#@^(&*%^（此处省去一万字神仙算法）。。。

但是不好意思，这些做法不能解决这个题

Why?

因为众数不满足“区间加法”的性质

例如现有区间[x,y]的众数A,还有区间[y+1,z]的众数B，但是我们不能直接得到区间[x,z]的众数

这时，如果使用线段树和树状数组等数据结构就很难维护。

发现是一个强制在线无修改区间众数题，不妨考虑分块

本题实际上有两种分块做法，在这里都介绍一下

part1：做法1 暴力分快

一种比做法2更好想的做法

我们可以只预处理那些以“块”为单位的众数，即我们设Mode[i][j]表示块i到块j之间的众数(Mode)，同时记下每个元素出现的次数，即num[i][j][k]表示k在第i块到第j块之间出现的次数

我们还是考虑每次询问，那么有以下操作

对于查询指令“l r”，有如下操作：

$(2)$：($l$和$r$**不在同一块内**)此时不妨设$l$在第$p$块，$r$在第$q$块 1.（**整块**操作）对所有的$i∈[p+1,q-1]$，我们可以$O(1)$查询$Mode[p+1][q-1]$，并记录其出现次数为$sum

2.（零散块操作）对不足一整块的边角块q和p，按照1中的方法暴力查询每个元素的出现次数，此时每个元素对应的出现次数为num[p+1][q-1][k]+cnt_k，取maxnum所对应的A[i]即为答案，最后再将这些统计的次数复原

那么以上这些就是查询操作

现在来分析一下做法1的时间复杂度

我们不妨设将整个序列分为t块，那么每一块的长度就是Len=n/t

显然，我们预处理这些只以块为单位的众数，这些以块为单位组成的区间一共有O(t^2)个，对于每个数还要有一个长度为O(n)的数组来记录，即空间消耗为O(n*t^2)

考虑每次询问，对于整块显然是O(1)的，但是我们都需要朴素扫描长度至多为O(len)的边角块来更新答案，所以单次回答询问的时间复杂度为O(len)的，因此回答询问的总复杂度为O(Q*len)的

那么综上，整个算法的总复杂度为O(n*t^2+Q*len)，我们将len代换为n/t得到O(n*t^2+Q*n/t)

根据均值不等式，显然当t=cbrt(n)（n^(1/3)）时，整个算法复杂度取得最优

此时整个算法的时间复杂度为O(n^(5/3))，空间复杂度为O(n^(5/3))

那么以上就是第一种做法了

可能。。。数据再大一些就会被卡掉了，毕竟复杂度很高，常数也不小

下面放一下代码

```cpp #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #define re register using namespace std; char IN[1<<17],*SS=IN,*TT=IN; inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);} inline int read()//fread一发入魂 { int now=0,f=1;re char c=gc(); for(;!isdigit(c);c=='-'&&(f=-1),c=gc()); for(;isdigit(c);now=now*10+c-'0',c=gc()); return now*f;} const int maxn=40003; int n,Q,cnt,ans,tot,Len,A[maxn],B[maxn]; int L[maxn],R[maxn],Mode[41][41],num[41][41][maxn]; inline void pre_divide()//分块 { tot=(int)pow(n*1.0,1.0/3),Len=n/tot; for(re int i=1;i<=tot;i++) L[i]=(i-1)*Len+1,R[i]=i*Len; if(R[tot]<n)L[tot+1]=R[tot]+1,R[++tot]=n; for(re int i=1;i<=tot;i++)//计算第[l,r]块的众数 for(re int j=i;j<=tot;j++) { for(re int k=L[i];k<=R[j];k++) num[i][j][A[k]]++; for(re int k=1;k<=cnt;k++) if(num[i][j][k]>num[i][j][Mode[i][j]]||(num[i][j][k]==num[i][j][Mode[i][j]]&&k<Mode[i][j])) Mode[i][j]=k; } } inline int query(int l,int r)//查询[l,r]众数 { int lb=1,rb=tot,sum=-1; while(lb<=tot&&L[lb]<l)lb++;//找到l右边的第一个整块 while(rb&&R[rb]>r)rb--;//找到r左边的第一个整块 if(lb>rb)//l右整块比r左整块编号大,说明l和r在同一块内,则暴力查询 { ans=0; for(re int i=l;i<=r;i++)//暴力查询 { num[0][0][A[i]]++; if(num[0][0][A[i]]>sum||(num[0][0][A[i]]==sum&&A[i]<ans)) ans=A[i],sum=num[0][0][A[i]]; } for(re int i=l;i<=r;i++)//复原 num[0][0][A[i]]--; return ans=B[ans]; } //反之,l和r不在同一块内,零散块暴力 ans=Mode[lb][rb],sum=num[lb][rb][ans]; for(re int i=l;i<L[lb];i++)//暴力统计左零散块 { num[lb][rb][A[i]]++; if(num[lb][rb][A[i]]>sum||(num[lb][rb][A[i]]==sum&&A[i]<ans)) ans=A[i],sum=num[lb][rb][A[i]]; } for(re int i=R[rb]+1;i<=r;i++)//暴力统计右零散块 { num[lb][rb][A[i]]++; if(num[lb][rb][A[i]]>sum||(num[lb][rb][A[i]]==sum&&A[i]<ans)) ans=A[i],sum=num[lb][rb][A[i]]; } for(re int i=l;i<L[lb];i++)//复原左零散块 num[lb][rb][A[i]]--; for(re int i=R[rb]+1;i<=r;i++)//复原右零散块 num[lb][rb][A[i]]--; return ans=B[ans]; } int main() { n=read(),Q=read(); for(re int i=1;i<=n;i++) A[i]=B[i]=read(); sort(B+1,B+1+n); cnt=unique(B+1,B+1+n)-B-1; for(re int i=1;i<=n;i++) A[i]=lower_bound(B+1,B+1+cnt,A[i])-B; //离散化 pre_divide(); while(Q--) { int l=read(),r=read(); l=(l+ans-1)%n+1,r=(r+ans-1)%n+1; if(l>r)swap(l,r); printf("%d\n",query(l,r)); } return 0; } ``` 个人感觉，第一种做法更接近于“朴素”（暴力），总觉得有些太“想当然”了 下面来看一下第二种做法 #### part2：做法2 优雅的分块 一种**比做法$1$理论复杂度更优**的算法 部分思想和做法$1$一致 我们可以**只预处理那些以“块”为单位的众数**，即我们**设$Mode[i][j]$表示块$i$到块$j$之间的众数$(Mode)$** 同时，**对于每个元素都建立一个$vector$数组$T$，其中$T[i]$表示数$i$在序列中出现的位置**，这些**所有的$T$数组内部都按照升序排序** 此时，**每个元素的$vector$内部是有序的**，我们可以想到一个神奇的东西----**二分** 类似于上面的例题$ex2$，我们这次**不在块内二分，而在每个元素内部二分** 什么意思呢？请往下看 考虑每一个询问操作，我们依旧按上面的方法来处理 对于查询指令“$l$ $r$”，有如下操作： $(1)$：若此时$l$和$r$在**同一块内，直接暴力查询块内每一个元素在区间$[l,r]$内的元素个数，在其所对应的$T$数组中进行二分，那么元素$A[i]$在$[l,r]$内出现的次数为$num=upper$_$bound(A[i],r)-lower$_$bound(A[i],l)$，此时取$maxnum$对应的的$A[i]$即为答案** $(2)$：($l$和$r$**不在同一块内**)此时不妨设$l$在第$p$块，$r$在第$q$块 1.（**整块**操作）对所有的$i∈[p+1,q-1]$，我们可以$O(1)$查询$Mode[p+1][q-1]$，并记录其出现次数为$sum

2.（零散块操作）对不足一整块的边角块q和p，按照1中的方法暴力查询每个元素的出现次数（还是在对应的T内进行二分）

那么以上这些就是查询操作

现在来分析一下做法2的复杂度

我们不妨设将整个序列分为t块，那么每一块的长度就是Len=n/t

显然，我们预处理整块的众数为O(n*t)的，空间消耗为O(t^2)

单次回答询问显然是O(len*logn)的，那么回答所有的询问操作时间是O(Q*len*logn)

那么整个算法的总复杂度是O(n*t+Q*len*logn)，我们把len替换为n/t，原式变为O(n*t+Q*logn*n/t)

根据均值不等式，显然当t=sqrt(n*logn)时，该算法的复杂度取得最优

此时整个算法的时间复杂度为O(n*sqrt(n*logn))，空间复杂度为O(n*logn)

那么第二种方法也就算写完了

感觉。。。大概的思路还是很好理解的吧（可能代码写的有点让人摸不着头脑）

我太菜了，常数写的巨大，滥用STL导致效率不是太好，甚至。。。比做法1还慢

下面放一下（巨丑的）代码好了

```cpp #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #include<vector> #include<cstring> #define re register using namespace std; char IN[1<<17],*SS=IN,*TT=IN; inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);} inline int read()//fread一发入魂 { int now=0,f=1;re char c=gc(); for(;!isdigit(c);c=='-'&&(f=-1),c=gc()); for(;isdigit(c);now=now*10+c-'0',c=gc()); return now*f;} const int maxn=40003; int n,Q,cnt,ans,tot,Len,A[maxn],B[maxn],num[maxn]; int L[maxn],R[maxn],Mode[1003][1003]; vector <int> T[maxn]; vector <int>::iterator pos1,pos2; inline void pre_divide()//分块 { tot=sqrt(n*log2(n)),Len=n/tot; for(re int i=1;i<=tot;i++) L[i]=R[i-1]+1,R[i]=i==tot?n:L[i]+Len-1; for(re int i=1;i<=tot;i++)//计算第[l,r]块的众数 { memset(num,0,sizeof(num)); for(re int j=i;j<=tot;j++) { Mode[i][j]=Mode[i][j-1]; for(re int k=L[j];k<=R[j];k++) { num[A[k]]++; if(num[A[k]]>num[Mode[i][j]]||(num[A[k]]==num[Mode[i][j]]&&A[k]<Mode[i][j])) Mode[i][j]=A[k]; } } } //把每个元素所在的下标对应放进数组(此时保证升序) for(re int i=1;i<=n;i++) T[A[i]].push_back(i); } inline int query(int l,int r)//查询[l,r]众数 { int lb=1,rb=tot,sum=-1,len; while(lb<=tot&&L[lb]<l)lb++;//找到l右边的第一个整块 while(rb&&R[rb]>r)rb--;//找到r左边的第一个整块 if(lb>rb)//l右整块比r左整块编号大,说明l和r在同一块内,则暴力查询 { ans=0; for(re int i=l;i<=r;i++) { pos1=lower_bound(T[A[i]].begin(),T[A[i]].end(),l); pos2=upper_bound(T[A[i]].begin(),T[A[i]].end(),r); len=pos2-pos1; if(len>sum||(len==sum&&A[i]<ans)) ans=A[i],sum=len; } return ans=B[ans]; } //反之,l和r不在同一块内,零散块暴力,整块O(1+2*logn) ans=Mode[lb][rb]; pos1=lower_bound(T[ans].begin(),T[ans].end(),l); pos2=upper_bound(T[ans].begin(),T[ans].end(),r); sum=pos2-pos1; for(re int i=l;i<L[lb];i++)//暴力统计左零散块 { pos1=lower_bound(T[A[i]].begin(),T[A[i]].end(),l); pos2=upper_bound(T[A[i]].begin(),T[A[i]].end(),r); len=pos2-pos1; if(len>sum||(len==sum&&A[i]<ans)) ans=A[i],sum=len; } for(re int i=R[rb]+1;i<=r;i++)//暴力统计右零散块 { pos1=lower_bound(T[A[i]].begin(),T[A[i]].end(),l); pos2=upper_bound(T[A[i]].begin(),T[A[i]].end(),r); len=pos2-pos1; if(len>sum||(len==sum&&A[i]<ans)) ans=A[i],sum=len; } return ans=B[ans]; } int main() { n=read(),Q=read(); for(re int i=1;i<=n;i++) A[i]=B[i]=read(); sort(B+1,B+1+n); cnt=unique(B+1,B+1+n)-B-1; for(re int i=1;i<=n;i++) A[i]=lower_bound(B+1,B+1+cnt,A[i])-B; //离散化 pre_divide(); while(Q--) { int l=read(),r=read(); l=(l+ans-1)%n+1,r=(r+ans-1)%n+1; if(l>r)swap(l,r); printf("%d\n",query(l,r)); } return 0; } ``` 这就是第二种方法了。。。 这种做法嘛，看起来就很舒服，感觉比做法$1$好多了 ~~虽然说我没手打二分结果常数大到死~~也是一种很好的想法 对了，如果觉得我写的不是太好，也可以看看这位巨佬的$blog$: [链接](https://shehuizhuyihao.blog.luogu.org/yi-suo-ji-guai-di-fen-kuai-ti-ti-xie) ================================================================== ## 分块的扩展：莫队$(Mo's$ $algorithm)

既然讲到了分快，就必须提一下更加优美的暴力----莫队

从一种角度来讲，莫队是一种思想化的算法，是一种将询问放在一起考虑，基于分块实现操作，凭借分块的根号算法优势来达到普通暴力无法企及的效率的一种算法。

因此，也可以说莫队本质上是一种优化后的暴力

注意：莫队算法是一种离线算法，通常不能有修改操作

首先，如果要用莫队算法，则必须满足已知ans[l,r]可以得到ans[l+1,r],ans[l-1,r],ans[l,r+1],ans[l,r-1]

莫队算法的具体步骤：

1.先对原序列分块，一般分为tot=sqrt(n)块（但也有更玄学的分块方式）

2.离线操作，把所有询问放在一起排序，以左端点所在块编号为第一关键字，右端点的位置为第二关键字，之后维护[L,R]的答案，并不断调整L和R，直至与询问区间[ql,qr]恰好重合，此时ans[ql,qr]即为ans[L,R]

来分析一下莫队算法的时间复杂度：

1.左端点所在块编号确定时，右端点位置单调不降，右端点移动最坏产生的时间复杂度是O(n)，又由于总共O(sqrt(n))块，总时间复杂度为O(n*sqrt(n))

2.左端点所在块编号变动时，右端点移动最坏产生的时间复杂度是O(n)，总共O(sqrt(n))块，变动次数O(sqrt(n))次，总时间复杂度为O(n*sqrt(n))

3.块内左端点位置每次最多移动O(n*sqrt(n))，共m次询问，即共移动m次，故移动的总时间复杂度为O(m*sqrt(n))。

又由于通常m和n是同阶的，因此总的来说算法时间复杂度是O(n*sqrt(n))的

莫队算法的分类：

莫队算法一般分为两类，一是莫队维护区间答案，二是维护区间内的数据结构。当然细分的话还有树上莫队，带修改莫队、二维莫队等等。

莫队算法的小优化：奇偶块排序

莫队算法比较重要的东西是对询问排序

但是排序也是有讲究的

莫队算法一般的排序方式是这样的：

bool cmp(query x,query y)
{
    return (x.r/tot)==(y.r/tot)?x.l<y.l:x.r<y.r;
}

而有一种神奇的排序方式叫做奇偶块排序，它长这样：

bool cmp1(query x,query y)
{
    return (x.l/tot)^(y.l/tot)?x.l<y.l:(((x.l/tot)&1)?x.r<y.r:x.r>y.r);
}

由于chen_zhe过于毒瘤，导致现在几乎没有几道莫队题用普通排序能通过了233

奇偶块排序会快的原理貌似是因为在普通排序之后，指针会出现跳回左边的情况后，而为了处理下一个块又要跳回右边，但经过奇偶块排序之后，指针移到右边后就不用再跳回左边，所以这样能减少很多（一半）操作，理论上能快一倍

但是都不重要，只要记背下来就好了（雾）

到了这里，上面的东西都挺好理解的吧

由于我很菜还不会其他的莫队接下来我们主要来讲一下普通的莫队算法

来看几道例题：（以下都是不带修改的普通莫队）

===============================================================

新鲜热乎的（普通）莫队例题：（未完待续）

ex5：P1972 [SDOI2009]HH的项链

题目传送门：

https://www.luogu.org/problemnew/show/P1972

还记得zsy巨佬告诉我不用奇偶块排序死后都过不去之前我用主席树做法交了1页多的悲惨故事。。。

题目大意：

给定一个长度为n的序列，有m次询问，每次询问区间[l,r]内的不同颜色种数

数据范围：n,m<=100000(1e5)

这题一看就可以主席树来做，但是我们假装不会主席树

emmm....考虑暴力，每次询问暴力扫[l,r]，那么这样总体是O(n*m)的

不妨来改变一下暴力的方式，可以维护一个区间[L,R]的答案，那么对于每一个询问[ql,qr]，我们都可以移动L和R指针，顺便更新答案，最后当L=ql&&R=qr时正好得到了答案，单次操作复杂度为

O(abs(L-ql)+abs(R-qr))

仔细一想，会发现我根本就是在骗人

什么嘛，这不就是暴力嘛！和O(n^2)做法有啥区别啊！

（没错，我就是在骗你）（大雾）

想到这个过程本质上是与暴力枚举没有区别的，我们考虑优化（其实就是莫队算法）

先对所有询问按上面的方法以左端点所在块为第一关键字，右端点为第二关键字排序

之后就从左往右依次回答每一个询问（暴力跳指针L和R）

在回答询问时更新答案也很简单，考虑在指针移动时其实就是加入和删除贝壳的过程。加入贝壳时对于一种颜色x，如果发现cnt[x]==1那么ans++，反之当删除贝壳时对于一种颜色x，如果发现cnt[x]==0，那么ans--

看起来很好理解是不是？其实这就是最简单的莫队算法了

下面放一下代码

（由于数据加强，下面的代码过不去了，有需要的同学可以尝试主席树解决本题）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()//fread一发入魂  
{
    int now=0,f=1;char c=gc();
    for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now*f;}
const int maxn=500003;
struct query
{
    int l,r,id;
}q[maxn];
int n,m,tot,A[maxn],bel[maxn],sum[maxn<<1],Ans[maxn],ans,L,R;
bool cmp1(query x,query y)
{
    if(bel[x.l]==bel[y.l])return (bel[x.l]&1)?x.r<y.r:x.r>y.r;
    return bel[x.l]<bel[y.l];
}
inline void del(int x)
{
    if(!(--sum[A[x]]))ans--;
}
inline void add(int x)
{
    if((++sum[A[x]])==1)ans++;
}
int main()
{
    n=read(),tot=1221;
    for(int i=1;i<=n;i++)
        A[i]=read(),bel[i]=(i-1)/tot+1;
    m=read();
    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,cmp1);
    for(int i=1;i<=m;i++)
        {
            int ql=q[i].l,qr=q[i].r,x=q[i].id;
            while(L<ql)del(L++);
            while(L>ql)add(--L);
            while(R<qr)add(++R);
            while(R>qr)del(R--);
            Ans[x]=ans;
        }
    for(int i=1;i<=m;i++)
        printf("%d\n",Ans[i]);
    return 0;
}

（尽管用了神奇的奇偶块排序和fread+O^2最后也没卡过233）

所以说上面这题的代码仅供参考

==================================================================

ex6：P2709 小B的询问

题目传送门：

https://www.luogu.org/problemnew/show/P2709

题意很简单，对于每一次询问[l,r]求∑cnt[A[i]]^2，其中i∈[l,r]且cnt[x]表示x在[l,r]出现的次数

第一眼看完。。。直接就想到了暴力（雾）

不妨来考虑一下更优的暴力----莫队

显然，用莫队来维护答案是合理的

类似于上面的做法，不妨设维护的区间[L,R]答案为ans

考虑在指针移动时其实就是加入和删除某个数字的过程。加入数字时对于一种颜色x，它的贡献是2*cnt[x]+1，反之当删除数字时，对于一种颜色x，它的贡献是2*cnt[x]-1，那么直接修改ans即可

下面放一下代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
typedef long long ll;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()//fread一发入魂  
{
    int now=0,f=1;re char c=gc();
    for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now*f;}
const int maxn=50003;
struct query
{
    int l,r,id;
}q[maxn];
int n,m,K,tot,L=1,R,A[maxn],sum[maxn];
ll Ans[maxn],ans;/*
bool cmp(query x,query y)
{
    return (x.r/tot)==(y.r/tot)?x.l<y.l:x.r<y.r;
}*/
bool cmp1(query x,query y)
{
    return (x.l/tot)^(y.l/tot)?x.l<y.l:(((x.l/tot)&1)?x.r<y.r:x.r>y.r);
}
inline void del(int x)
{
    sum[A[x]]--;
    ans-=2*sum[A[x]]+1;
}
inline void add(int x)
{
    sum[A[x]]++;
    ans+=2*sum[A[x]]-1;
}
int main()
{
    n=read(),m=read(),K=read(),tot=sqrt(n);
    for(re int i=1;i<=n;i++)
        A[i]=read();
    for(re int i=1;i<=m;i++)
        q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+1+m,cmp1);
    for(re int i=1;i<=m;i++)
        {
            int ql=q[i].l,qr=q[i].r;
            while(L<ql)del(L++);
            while(L>ql)add(--L);
            while(R<qr)add(++R);
            while(R>qr)del(R--);
            Ans[q[i].id]=ans;
        }
    for(re int i=1;i<=m;i++)
        printf("%lld\n",Ans[i]);
    return 0;
}

这道题还是要用奇偶块排序（但是尝试了一下，不用也能过）

================================================================

ex7：P1494 [国家集训队]小Z的袜子

题目传送门：

https://www.luogu.org/problemnew/show/P1494

听说是一道莫队入门经典题，于是就来做了

结果发现和ex6没啥区别。。。就是多了约分和特判

（反正莫队都是一个套路就对了）

来讲一下这道题

一看，立马就能出答案（真的，不是我吹牛）

对于某一次询问[l,r]，在该区间内对于某一种袜子x，选择同一双的方案是cnt[x]*(cnt[x]-1)（从x中袜子中拿出两支来穿）

则所有合法的方案为∑(cnt[x]*(cnt[x]-1))，其中x都是区间[l,r]内出现的袜子

还可以得到本区间内所有方案数为(r-l+1)*(r-l)（从该区间内任选两支穿）

那么对于询问区间[l,r]的答案为

ans=∑(cnt[x]*(cnt[x]-1))/(r-l+1)*(r-l)

展开化简，可以得到ans=(∑cnt[x]^2-∑cnt[x])/(r-l+1)*(r-l)

题目中没有修改操作，显然用线段树和树状数组是无用功

不妨使用莫队

同时考虑莫队算法过程中指针L和R移动带来的影响

考虑在指针移动时其实就是加入和删除某只袜子的过程。加入袜子时对于一种颜色x，它的贡献是2*cnt[x]+1，反之当删除袜子时，对于一种颜色x，它的贡献是2*cnt[x]-1，那么直接修改ans即可

（其实和上面的ex6一模一样）

最后注意约分和ql==qr情况特判就行了

下面放代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
typedef long long ll;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()//fread一发入魂  
{
    int now=0,f=1;re char c=gc();
    for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now*f;}
const int maxn=50003;
struct query
{
    int l,r,id;
}q[maxn];
struct anwser
{
    ll up,down;
}Ans[maxn];
int n,m,tot,L,R,A[maxn];
ll sum[maxn],ans;
bool cmp1(query x,query y)
{
    return (x.l/tot)^(y.l/tot)?x.l<y.l:(((x.l/tot)&1)?x.r<y.r:x.r>y.r);
}
inline ll gcd(ll a,ll b)
{
    if(!b)return a;
    return gcd(b,a%b);
}
inline void del(int x)
{
    sum[A[x]]--;
    if(sum[A[x]]>0)
        ans+=(-2)*sum[A[x]];
}
inline void add(int x)
{
    sum[A[x]]++;
    if(sum[A[x]]>1)
        ans+=2*(sum[A[x]]-1);
}
int main()
{
    /*
    分析:对于某一次询问,答案为 
    ans=sigma(i:l~r)num[x]*(num[x]-1)/(r-l+1)*(r-l)即 
    ans=sigma(i:l~r)sum[x]^2-sigma(i:l~r)sum[x]/(r-l+1)*(r-l)
    可以发现只需要维护分子 
    那么用莫队来做 
    考虑每次挪动加入元素对答案的贡献为2*num[x]+1
    那么删除同理,贡献为2*num[x]-1
    最后注意gcd约分即可 
    */
    n=read(),m=read(),tot=sqrt(n);
    for(re int i=1;i<=n;i++)
        A[i]=read();
    for(re int i=1;i<=m;i++)
        q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+1+m,cmp1);
    for(re int i=1;i<=m;i++)
        {
            ll ql=q[i].l,qr=q[i].r,x=q[i].id;
            if(ql==qr)
                {
                    Ans[x].up=0,Ans[x].down=1;
                    continue;
                }
            while(L<ql)del(L++);
            while(L>ql)add(--L);
            while(R<qr)add(++R);
            while(R>qr)del(R--);
            if(!ans)
                {
                    Ans[x].up=0,Ans[x].down=1;
                    continue;
                }
            ll g=gcd(ans,(qr-ql+1)*(qr-ql));
            Ans[x].up=ans/g,Ans[x].down=(qr-ql+1)*(qr-ql)/g;
        }
    for(re int i=1;i<=m;i++)
        printf("%lld/%lld\n",Ans[i].up,Ans[i].down); 
    return 0;
}

仍然用的是奇偶块排序。。。普通排序没试过。。。

===============================================================

ex8：P4462 [CQOI2018]异或序列

题目传送门：

https://www.luogu.org/problemnew/show/P4462

一道看起来不是太像莫队的题目。。。

但是转念一想发现几乎是个莫队板子题233

来看一下怎么做

题目要求询问区间[l,r]内满足sum^A[i](i∈[x,y])的(x,y)对数，没有修改

第一眼一看像个线段树题

但是想到没有修改，最后还是放弃了线段树（会多个log）

先来考虑暴力做法

预处理前缀异或和，直接暴力枚举[l,r]的子区间[x,y]，由于异或的神奇性质，sum[y]^sum[x-1]就是区间[x,y]的异或和，直接累加符合答案的(x,y)点对即可

显然这样做的单次复杂度达到了O(n^2)，不可接受

既然都是暴力，不妨考虑莫队

貌似莫队O(n*sqrt(n))可做

其实异或还有一个性质，a^b=c那么c^b=a

基于上面的暴力做法，每次都要枚举一个区间异或和，为什么不把区间异或和存在一个数组中呢？

即我们记cnt[x]表示x在当前区间出现的次数，利用上面的性质，每次只要存在一个x=k^sum[i]，即代表存在一个点对(x,y)符合条件，直接累加次数即可

现在重要的事就转变成了如何维护这个cnt数组

我们使用莫队算法来维护

来考虑莫队算法过程中指针L和R移动带来的影响

考虑在指针移动时其实就是加入和删除某个数字的过程。加入数字x时，显然此时它的贡献是cnt[k^x]，同时令cnt[x]+1，反之当删除数字x时，对于数字x，显然此时它的贡献是-cnt[k^x]，同时令cnt[x]-1，直接修改ans即可

注意：由于异或前缀和的计算方式是sum[r]^sum[l-1]，因此导致每次询问区间[ql,qr]都应改为询问区间[ql-1,qr]（感性理解一下应该能懂吧）

那么下面就放一下代码好了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
typedef long long ll;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()//fread一发入魂  
{
    int now=0,f=1;re char c=gc();
    for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now*f;}
const int maxn=100003;
struct query
{
    int l,r,id;
}q[maxn];
int n,m,K,tot,L,R,A[maxn],sum[maxn],Ans[maxn],ans;
bool cmp1(query x,query y)
{
    return (x.l/tot)^(y.l/tot)?x.l<y.l:(((x.l/tot)&1)?x.r<y.r:x.r>y.r);
}
inline void del(int x)//注意先后顺序
{
    ans-=sum[A[x]^K],sum[A[x]]--;
}
inline void add(int x)//注意先后顺序
{
    ans+=sum[A[x]^K],sum[A[x]]++;
}
int main()
{
    n=read(),m=read(),K=read(),tot=sqrt(n);
    for(re int i=1;i<=n;i++)
        A[i]=A[i-1]^read();
    for(re int i=1;i<=m;i++)
        q[i].l=read()-1,q[i].r=read(),q[i].id=i;
    sort(q+1,q+1+m,cmp1),sum[0]=1;
    for(re int i=1;i<=m;i++)
        {
            int ql=q[i].l,qr=q[i].r,x=q[i].id;
            while(L<ql)del(L++);
            while(L>ql)add(--L);
            while(R<qr)add(++R);
            while(R>qr)del(R--);
            Ans[x]=ans;
        }
    for(re int i=1;i<=m;i++)
        printf("%d\n",Ans[i]); 
    return 0;
}

仍然用的是奇偶块排序。。。还是没测试普通排序

===============================================================

ex9：P4137 Rmq Problem / mex

题目传送门：

https://www.luogu.org/problemnew/show/P4137

一道看起来就不像是莫队的题目

但是第一眼看见的时候，感觉线段树貌似可行？

仔细一想，发现区间的mex值对于线段树来说是不可维护的

因此还是要向暴力（莫队）方向想

于是。。。又用莫队水了一道紫题（大雾）

本题没有修改操作，很容易想到将所有询问离线，排序后用莫队暴力处理

貌似莫队都是一个套路

但是每个数A[i]<=1e9，数组存不下，怎么办呢？

来考虑一下mex的定义：一个区间内最小没有出现过的自然数

emmmm。。。（还是看不出什么）

既然说了mex是自然数，那么对于一个区间，只要这个区间是整个序列的子区间，那么mex的值就一定不会超过整个序列的长度

仔细想一想应该是能看懂这段话的

即，无论A[i]有多大，答案mex一定不会超过n，即每一次询问ans<=n

又由于题目中保证n<=2e5，所以我们可以说那些A[i]>2e5都是没有用的

于是乎用莫队就可以做啦！

再来考虑莫队算法过程中指针L和R移动带来的影响

考虑在指针移动时其实就是加入和删除某个数字的过程。加入数字x时，令cnt[x]+1，若原来的ans=x，那么则从x开始找后面的第一个没出现的数cnt[k]=0即为新的ans，反之当删除数字x时，对于数字x，令cnt[x]-1，若此时cnt[x]=0且ans>x直接令ans=x即可

下面放代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
inline int read()
{
    int p=0,f=1;re char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return f*p;}
const int maxn=200003;
struct query
{
    int l,r,id;
}q[maxn];
int n,m,tot,L=1,R=1,ans,A[maxn],sum[200003],Ans[maxn];
bool cmp1(query x,query y)
{
    return (x.l/tot)^(y.l/tot)?x.l<y.l:(((x.l/tot)&1)?x.r<y.r:x.r>y.r);
}
inline void del(int x)
{
    if(A[x]>n)return ;
    if(!(--sum[A[x]]))ans=min(ans,A[x]);
}
inline void add(int x)
{
    if(A[x]>n)return ;
    sum[A[x]]++;
    if(ans==A[x])while(sum[ans])ans++;
}
int main()
{
    n=read(),m=read(),tot=(int)sqrt(n);
    for(re int i=1;i<=n;i++)
        A[i]=read();
    for(re int i=1;i<=m;i++)
        q[i].l=read(),q[i].r=read(),q[i].id=i;
    sort(q+1,q+1+m,cmp1),add(L);
    for(re int i=1;i<=m;i++)
        {
            int ql=q[i].l,qr=q[i].r,x=q[i].id;
            while(L<ql)del(L++);
            while(L>ql)add(--L);
            while(R<qr)add(++R);
            while(R>qr)del(R--);
            Ans[x]=ans;
        }
    for(re int i=1;i<=m;i++)
        printf("%d\n",Ans[i]);
    return 0;
}

还还还是奇偶块排序。。。仍然不敢写普通排序

过掉了之后才发现，但是貌似这题正解是树套树？

（我不管，反正用莫队水过了）（大雾）

于是乎。。。又水了一道树套树神仙题233

===============================================================

小结：

做完这么多题之后我们能发现：

莫队算法几乎在所有的离线区间问题面前都是无敌的

几乎只要是能离线，用莫队算法都能取得一个令人满意的分数

（当然像noip、chen_zhe、lin_toto那样毒瘤的出题人不算在出题人队伍里）

通常莫队算法不是满分也是高分(80或90分)

暴力碾标算！（大雾）

莫队不像线段树和树状数组，那样需要对维护的信息有所顾虑（必须满足区间可加性），和分块一样，莫队也适用于很多问题，比如中位数和区间众数等问题莫队都是可以做的

但是普通的莫队算法也有缺陷，就是不能修改

为了延续暴力的美德，后人提出了可修改的莫队算法，即带修的莫队算法

接下来我们来讲一下带修莫队

进阶：带修莫队----普通莫队的扩展

由于本人过于菜，看了将近一上午才大概看懂了带修莫队的实现方式

（不得不说也是神奇，为了暴力竟然能想出这么神仙的算法）

众所周知，莫队是一种离线算法，通常不能有修改

对付那些没有修改的区间查询题目，普通莫队可以说是杀手锏

但是如果加上了修改，普通莫队就没有了用武之地

这时，我们就要对普通的莫队算法进行改进，带修莫队就这样横空出世了

那么下面就大概讲一下如何实现带修莫队

带修莫队为了解决修改的问题，仍让沿用了普通莫队的思想，将时间也分割开来，在合理的排序下仍然能保证得到最优的解决方式，这种思想使得算法得到优化和改进，这样莫队算法也能适用于更多的问题

类似于普通莫队的思想，还是维护某个区间[L,R]的答案ans

由于有了修改操作，需要给我们维护的区间加上一维时间轴，即我们现在维护的是[L,R,now]区间，其中now代表已经进行过几次修改操作

仍然基于暴力思想，我们可以想到当L=ql&&R=qr时，若此时还满足now=qt，显然此时答案ans即为询问的答案qans

那么带修的莫队算法就呼之欲出了

带修莫队实现如下：（非常类似于普通莫队）

1.先对原序列进行分块

2.增加一个变量sum_change，来记录对于每一个询问操作，在进行询问之前一共进行了多少次修改，之后对于每一次询问，和普通莫队的L指针和R指针一样新增一个now指针来表示当前进行了多少次修改，而now指针的移动与L指针和R指针也是类似的，最后当三个指针和该次询问的三个量（时间和区间）完全相等时，此时的答案即为该次询问的答案

带修莫队的排序方式：

仍然类似于普通莫队，带修莫队的排序方式是下面这样的：

bool cmp1(query x,query y)
{
    return (x.l/tot)^(y.l/tot)?x.l<y.l:((x.r/tot)^(y.r/tot)?x.r<y.r:x.pre<y.pre);
}

即我们先按照左端点排序，再按照右端点排序，最后按照时间排序

(pre即为每次询问的时间)

貌似在带修莫队里，没有像普通莫队那样神奇的排序方式（奇偶块排序）

（反正都不重要只要背下来就好了）（大雾）

带修莫队的时间复杂度分析

看完上面普通莫队的你应该了解到，莫队算法需要分块

那么，带修莫队时，分块的大小为多少呢？

我们要先分析一下带修莫队的时间复杂度

前方高能预警，请非战斗人员尽快撤离！

不妨设分块的大小为tot=n^x，其中0<x<1

我们来考虑带修莫队算法中3个指针(L,R,now)的移动情况：

1.对于L指针

在块内移动时，每一次移动的复杂度为O(n^x)，共有m次询问，总复杂度为O(n^{x+1})

到下一个块时，每一次移动的复杂度为O(n^x)，又因为块的大小是O(n^x)的，因此总块数为O(\frac n{n^x})，于是总复杂度为O(n)

综上，因L指针移动产生的总复杂度为O(n^{x+1})

2.对于R指针

L$和$R$指针全都在块内移动时，每一次移动的复杂度为$O(n^x)$，由于这样的情况共有$O((\frac n{n^x})^2)$，即共有$O(n^{2-2x})$次，总复杂度为$O(n^{2-x})

当L所在块不变且R移动到下一块时，每一次移动的复杂度为O(n^x)，由于总块数为O(\frac n{n^x})，即O(n^{1-x})，总复杂度为O(n^{2-x})

当L指针移动到下一块时，每一次移动的复杂度为O(n)，由于这样的情况共有O(\frac n{n^x})，即O(n^{1-x})次，总复杂度为O(n^{2-x})

综上，因R指针移动产生的总复杂度为O(n^{2-x})

3.对于now指针

当L和R全都在块内移动时，此时保证K指针是递增的(我们在排序时已经保证了x.k<y.k)，因此总复杂度为O(n)

当L所在块不变且R到下一块时，每一次移动的复杂度为O(n)，这样的情况有O(n^{2-2x})次，因此总复杂度为O(n^{3-2x})

当L指针移动到下一个块时，每一次移动的复杂度应为O(n)，这样的情况共有O(n^{1-x})次，因此总复杂度为O(n^{2-x})

综上，因now指针的总复杂度为O(n^{max(2-x,3-2x)})

综上所述，带修莫队的总时间复杂度为O(n^{max(x+1,2-x,3-2x)})

根据均值不等式可知，存在一个x使max(x+1,2-x,3-2x)最小

显然此时当x取\frac23，即分块的大小为O(n^{\frac23})时，算法时间复杂度最优

即带修莫队算法的总时间复杂度为O(n^{\frac53})

（不得不说时间复杂度证明真的恶心）

光说上面这些可能有些无力，下面结合例题说明

===============================================================

新鲜热乎的（带修）莫队例题：（未完待续）

ex10：P1903 [国家集训队]数颜色 / 维护队列

题目传送门：

https://www.luogu.org/problemnew/show/P1903

据说是一道典型的带修莫队。。。于是就来做一下

（不用带修莫队就要用树套树，我也不会啊QAQ）

这题如果没有修改操作，就和ex5完全一致

但是即使多了修改操作，我们也能用神仙的带修莫队算法搞定

如果你已经看懂上面的带修莫队了，那么这题就是一道板子题了

对于每一个询问，记录下在这次询问前进行了几次修改

对于每一个修改，直接记录

每次维护三个指针L,R,now，不断更新当前区间的答案直至与查询区间完全一致（与询问时间qt，区间[ql,qr]完全相等时），就得到了答案

先来考虑莫队算法过程中指针L和R移动带来的影响

考虑在指针移动时其实就是加入和删除某个数字的过程。加入数字时对于一种颜色x，如果发现cnt[x]==1那么ans++，反之当删除颜色时对于一种颜色x，如果发现cnt[x]==0，那么ans--

再来考虑莫队算法过程中指针now移动带来的影响

对于每一个询问，如果发现时间不同步，我们要将没有执行的修改执行，或者将多执行的修改撤销，同时等效成添加或删除数字，继续维护当前的答案

光说可能有些难懂，下面放代码了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define re register
using namespace std;
typedef long long ll;
inline int read()
{
    int p=0,f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){p=p*10+c-'0';c=getchar();}
    return f*p;}
const int maxn=50003;
struct query
{
    int l,r,pre,id;
}q[maxn];
struct change
{
    int pos,x;
}C[maxn];
int n,m,tot,sum_query,sum_change,L=1,R,now,ans;
int A[maxn],sum[1000003],Ans[maxn];
bool cmp1(query x,query y)
{
    return (x.l/tot)^(y.l/tot)?x.l<y.l:((x.r/tot)^(y.r/tot)?x.r<y.r:x.pre<y.pre);
}
inline void del(int x)
{
    if(!(--sum[A[x]]))ans--;
}
inline void add(int x)
{
    if(++sum[A[x]]==1)ans++;
}
inline void time_go(int p,int id)
{
    if(q[id].l<=C[p].pos&&C[p].pos<=q[id].r)
        {
            if(!(--sum[A[C[p].pos]]))ans--;
            if(++sum[C[p].x]==1)ans++;
        }
//  A[C[p].pos]=C[p].x;
    swap(A[C[p].pos],C[p].x);
    //注意：由于以后还要用到第p次修改，所以只能暂时交换值，不能直接赋值
}
int main()
{
    n=read(),m=read(),tot=(int)pow(n*1.0,2.0/3.0);
    for(re int i=1;i<=n;i++)
        A[i]=read();
    for(re int i=1;i<=m;i++)
        {
            char s[5];
            scanf("%s",s);
            if(s[0]=='Q')
                {
                    sum_query++;
                    q[sum_query].l=read();
                    q[sum_query].r=read();
                    q[sum_query].id=sum_query;
                    q[sum_query].pre=sum_change;
                }
            else if(s[0]=='R')
                {
                    sum_change++;
                    C[sum_change].pos=read();
                    C[sum_change].x=read();
                }
        }
    sort(q+1,q+1+sum_query,cmp1);
    for(re int i=1;i<=sum_query;i++)
        {
            int ql=q[i].l,qr=q[i].r,x=q[i].id,t=q[i].pre;
            while(L<ql)del(L++);
            while(L>ql)add(--L);
            while(R<qr)add(++R);
            while(R>qr)del(R--);
            while(now<t)time_go(++now,i);
            while(now>t)time_go(now--,i);
            Ans[x]=ans;
        }
    for(re int i=1;i<=sum_query;i++)
        printf("%d\n",Ans[i]);
    return 0;
}

如果你看懂了上面带修莫队的一系列操作应该能看懂这份代码了

===============================================================

ex11：CF940F Machine Learning

一道强行拼凑起来的题。。。细节写错结果交了56发之后才过。。。

大概读完之后能发现其实是上面的ex9和ex10合起来的一道题

那就是一道有修改操作的ex9了

直接上带修莫队配合ex9搞掉不就行了吗？？？

由于数据过大，我们需要对原序列进行离散化 之后先开一个$sum$数组记录值为$x$的数出现的次数，再开一个$cnt$数组记录出现次数为$x$的出现次数 先来考虑莫队算法过程中指针$L$和$R$移动带来的影响 考虑在指针移动时其实就是加入和删除某个数字的过程。加入数字$x$时，若原来的$sum[x]>0$，要先让$num[sum[x]]-1$，之后令$sum[x]+1,num[sum[x]]+1$，反之当删除数字$x$时，对于数字$x$，令$num[sum[x]]-1,sum[x]-1$，若此时$sum[x]>0$，要让$num[sum[x]]+1

再来考虑莫队算法过程中指针now移动带来的影响

对于每一个询问，如果发现时间不同步，我们要将没有执行的修改执行，或者将多执行的修改撤销，同时等效成添加或删除数字，继续维护当前的答案

最后的最后，我们直接暴力循环一遍找答案

至于为什么可以暴力循环来找答案，可以给出一个复杂度证明

不妨设我们要找的答案(mex)值为x，那么考虑最坏情况，即x前面的数都恰好出现，即∑(i∈[1,x-1])i<=n，也就是说答案x是O(sqrt(n))级别的，而带修莫队的复杂度是O(n^{\frac53})，相比之下根本构不成影响，因此暴力求mex是没有问题的

本人表述可能有些不太清楚，所以还是看代码好了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<map>
#define re register
using namespace std;
char IN[1<<17],*SS=IN,*TT=IN;
inline char gc(){return (SS==TT&&(TT=(SS=IN)+fread(IN,1,1<<17,stdin),SS==TT)?EOF:*SS++);}
inline int read()//fread一发入魂  
{
    int now=0,f=1;re char c=gc();
    for(;!isdigit(c);c=='-'&&(f=-1),c=gc());
    for(;isdigit(c);now=now*10+c-'0',c=gc());
    return now*f;}
const int maxn=200005;
struct query
{
    int l,r,pre,id;
}q[maxn];
struct change
{
    int pos,x,oldval;
}C[maxn];
int n,m,tot,cnt,sum_query,sum_change,L=1,R=1,now,ans;
int A[maxn],B[maxn],sum[maxn],num[maxn],Ans[maxn];
//sum[x]存的是x的出现次数,num[i]存的是sum值为i的出现次数 
map <int,int> M;
bool cmp1(query x,query y)
{
    return (x.l/tot)^(y.l/tot)?x.l<y.l:((x.r/tot)^(y.r/tot)?x.r<y.r:x.pre<y.pre);
}
inline void del(int x)
{
    num[sum[x]]--,sum[x]--;
    if(sum[x]>0)num[sum[x]]++;
}
inline void add(int x)
{
    if(sum[x]>0)num[sum[x]]--;
    sum[x]++,num[sum[x]]++;
}
inline void time_back(int p,int id)
{
    if(q[id].l<=C[p].pos&&C[p].pos<=q[id].r)
        del(C[p].x),add(C[p].oldval);
    A[C[p].pos]=C[p].oldval;
}
inline void time_go(int p,int id)
{
    if(q[id].l<=C[p].pos&&C[p].pos<=q[id].r)
        del(C[p].oldval),add(C[p].x);
    A[C[p].pos]=C[p].x;
}
int main()
{
    n=read(),m=read(),tot=(int)pow(n*1.0,2.0/3.0);
    for(re int i=1;i<=n;i++)
        {
            A[i]=read();
            if(!M[A[i]])M[A[i]]=++cnt;
            B[i]=A[i]=M[A[i]];
        }
    for(re int i=1;i<=m;i++)
        {
            int flag=read(),x=read(),y=read();
            if(flag==1)
                {
                    sum_query++;
                    q[sum_query].l=x;
                    q[sum_query].r=y;
                    q[sum_query].id=sum_query;
                    q[sum_query].pre=sum_change;
                }
            else if(flag==2)
                {
                    sum_change++;
                    C[sum_change].pos=x;
                    if(!M[y])M[y]=++cnt;
                    C[sum_change].x=y=M[y];
                    C[sum_change].oldval=B[x],B[x]=y;
                }
        }
    sort(q+1,q+1+sum_query,cmp1),add(A[L]);
    for(re int i=1;i<=sum_query;i++)
        {
            int ql=q[i].l,qr=q[i].r,x=q[i].id,t=q[i].pre;
            while(L<ql)del(A[L++]);
            while(L>ql)add(A[--L]);
            while(R<qr)add(A[++R]);
            while(R>qr)del(A[R--]);
            while(now<t)time_go(++now,i);
            while(now>t)time_back(now--,i);
            for(ans=1;num[ans];ans++);
            Ans[x]=ans;
        }
    for(re int i=1;i<=sum_query;i++)
        printf("%d\n",Ans[i]);
    return 0;
}

于是乎，又用莫队暴力过掉了一道紫题

（怎么感觉又在占题目的便宜）（大雾）

===============================================================

总结：

学习完了带修莫队，我才感受到暴力的美妙

（反正只要是暴力能想到解决方法的几乎都能用莫队来实现）

个人感觉，莫队是一种美妙的暴力算法，基于分块实现使得莫队算法在处理离线问题方面具有无与伦比的效率，这是其他更加高级的算法所不能媲美的

如让我果用两个词语来形容莫队算法，那就是朴素与直观

尽管我们上面提到的很多例题都是可以用树套树（或平衡树等）来解决的，但是由于树套树代码量高，常数巨大，实现困难等种种原因，都使得问题变得更加复杂。相比之下，莫队算法为我们提供了一种解决问题的好途径，使得我们能在变化量很小的情况下，快速而简便的得出问题的解，因此可以说，莫队算法是一种是非常优秀的算法

（这上面都是我自己YY出来的，可以略过）

或许这就是算法的美妙所在了吧

突然发现。。。luogu上分块的好题很少，但是莫队的题目还真的很多，有兴趣的同学还可以做一做其他的题目，如果有好题的话请发给我

（大部分莫队题都被chen_zhe卡死了）

学完带修莫队之后，发现其实还有树上莫队和树上带修莫队

这里给出一道树上带修莫队模板题：P4074 [WC2013]糖果公园

学有余力的同学可以去学习一下（我太菜了，目前并不会树上带修莫队QAQ）

由于我太菜了导致并不想再学了（大雾）所以就这两个鸽了吧

行，这篇文章就暂时先写这么多吧，以后可能还会补上一些例题

## 未完待续 （这可能是一个永远也填不完的坑了$233$）