莫队

一、普通莫队算法

1. 基础思想

若存在序列上的一个区间[l,r]，若其维护的信息可以以极小的时间代价^1扩展到[l-1,r]，[l+1,r]，[l,r-1]，[l,r+1](即区间[l,r]的相邻区间)，那么这样可以保证在O(n{\sqrt{m}}) ^2的时间内完成多组询问的回答，是一种基于分块思想的解题方式。

[范例(可以用$\log{n}$移动)](https://www.luogu.com.cn/problem/P1533) $^2$：在$n,m$同阶时，有$O(n{\sqrt{n}})$时间复杂度；此类情况皆是以$O(1)$的转移代价分析的。 ### 2. 具体实现 将询问离线，离线后排序，顺序处理每个询问，暴力从上一个区间的答案转移到下一个区间答案（一步一步移动即可）。 ### 3. 排序规则 以询问左端点所在块的编号从小到大为第一关键字，询问的右端点从从小到大为第二关键字。 ### 4. 复杂度证明 若预处理分块过程： 时间复杂度为$O({\sqrt{n}}·{\sqrt{n}}{\log{\sqrt{n}}}+n\log{n})=O(n\log{n})$ 。 莫队核心过程： 令每一块中最大值为$max_1,max_2,…max_i,…max_{\sqrt{n}}$ 。 由第一次排序显然可知：$max_1<max_2<…max_i<…max_{\sqrt{n}}$ 。 显然暴力求出每一个询问的时间是$O(n)$的。 考虑$R$： 在每一块中$R$的移动是$O(n)$的，总体有${\sqrt{n}}$个块，总体时间复杂度是$O(n{\sqrt{n}})$的。 重点分析$L$： $L$在每一块内的移动是$|max_i-max_{i-1}|$的， 则在同一个块内的时间复杂度是$O({\sqrt{n}|max_i-max_{i-1}|})$的。 将每一块中的$L$进行合并得： $O( {\sqrt{n}}(max_1-1)+{\sqrt{n}}(max_2-max_1)+…+{\sqrt{n}(max_n-max_{n-1})} ) =O({\sqrt{n}}(max_n-1))

显然max_n 的最值为n，故L的时间复杂度最坏也是O(n{\sqrt{n}})的 。

5. 块长选择

对于m的不同取值，不同的分块方式会产生不同的效果。

不妨设块长为S，对于多次块内移动的询问，移动的距离为S,移动的块数为{\frac{n}{S}}，总次数就是{\frac{n^2}{S}}。

移动还可能跨越块，所以还要加上mS的复杂度。

总复杂度即为O(mS+{\frac{n^2}{S}})

由不等式分析 在S={\frac{n}{\sqrt{m}}}时 时间复杂度最优。

6. 实现

struct Query{
    int id,l,r;
    bool operator < (const Query &tmp) const { return l/B==tmp.l/B?r<tmp.r:l/B<tmp.l/B;} 
}q[N];
void add(int pos,int &Ans) {/*新增节点信息,记录Ans*/} 
void del(int pos,int &Ans) {/*删除节点信息,记录Ans*/}  
void solve(){
    int l=1,r=0,Ans=0; // 初始为空 
    sort(q+1,q+m+1);  
    For(i,1,m){
        const Query &que=q[i];
        // 优先进行区间的扩张,防止区间为空产生不必要错误  
        while(l>que.l) add(--l,Ans);
        while(r<que.r) add(++r,Ans);
        // ------------------------- 
        while(l<que.l) del(l++,Ans);
        while(r>que.r) del(r--,Ans);
        ans[que.id]=Ans;
    }
}
int main(){
    read(n); read(m);
    For(i,1,n) read(n);
    B=n/sqrt(m); if(!B) B=sqrt(n); // 防止 n<sqrt(m) 导致块长为 0 
    For(i,1,m) q[i].id=i,read(q[i].l),read(q[i].r);
    solve();
    For(i,1,m) Print(ans[i]),putchar('\n'); 
    return 0;
}

7. 优化

(1). 奇偶排序优化

排序时将偶数块的询问右端点从小到大排序，奇数块的询问右端点从小到大排序，以减少右端点的移动范围。

//   奇偶化排序 优化  
inline bool operator < (const Query &tmp) const {
    if(l/B!=tmp.l/B) return l<tmp.l;
    if((l/B)&1) return r<tmp.r;
    return r>tmp.r;
}

(2). 固定块长

将块长设置为某个常数，可能对于代码运行速度会有一定的提升。

二、带修莫队

1. 基础思想

普通的莫队是不支持修改操作的。

但我们可以强行为莫队添加一维时间轴，对于每个修改状态下的答案都进行计算。

区间由[l,r] 演变为[l,r,time]

区间移动演变为六个行为：

$[l,r-1,time]$,$[l,r+1,time]$, $[l,r,time-1]$,$[l,r,time+1]$。 ### 2. 具体实现 对于每一个修改操作和询问操作分别记录，为询问增添时间标记，记录其发生在第几个操作之后。 转移时相较普通莫队，只需要多考虑时间轴移动的影响即可。 ### 3. 排序规则 以询问左端点所在块为第一关键字，询问右端点从小到大为第二关键字，时间从小到大为第三关键字。 ### 4. 复杂度证明和块长选择 不妨设块长为$S$，每个块内询问$q_{i,j}$，端点移动复杂度为$O(S)$，时间单调，复杂度$O(t)$。 总复杂度即为： ${\sum_{i=1}^{\frac{n}{S}}} {\sum_{j=i+1}^{\frac{n}{S}}} (q_{i,j}·S+t) =mS+({\frac{n}{S})^2t}

当块长取S={\frac{n^{\frac{2}{3}}t^{\frac{1}{3}}}{m^{\frac{1}{3}}}}。

认为n,m同阶，则S=(nt)^{\frac{1}{3}}。

时间复杂度可以达到 O(n^{\frac{5}{3}})。

5. 实现

int n,m,B; 
struct Query{
    int id,l,r,t;
    bool operator < (const Query &tmp) const {
        if(l/B!=tmp.l/B) return l<tmp.l;
        if(r/B!=tmp.r/B) return r<tmp.r;
        return t<tmp.t;
    } 
}q[N];
struct Change{int p,c;}c[N]; 
void add(int pos){/*插入信息*/} 
void del(int pos){/*删除信息*/} 
void solve(){
    int l=1,r=0,tim=0;
    sort(q+1,q+kp+1);
    For(i,1,kp){
        const Query& que=q[i];
        while(l>que.l) add(--l);
        while(r<que.r) add(++r);
        while(l<que.l) del(l++);
        while(r>que.r) del(r--);
        while(tim<que.t){
            tim++;
            if(c[tim].p>=l&&c[tim].p<=r){
                // del(), add();
            }
        } 
        while(tim>que.t){
            if(c[tim].p>=l&&c[tim].p<=r){
                // del(),add(); 
            }
            tim--;
        }
        ans[que.id]=Ans;
    }
}
int main(){
    read(n),read(m);
    For(i,1,n) read(a[i]);
    For(i,1,m){
        int op,x,y; read(op),read(x),read(y);
        if(op==1) c[++tot]=(Change){x,y};
        else q[++kp]=(Query){kp,x,y,tot};
    }
    B=cbrt(1.0*n*max(1,tot))+1;  // == pow(1.0*n*tot,1.0/3); 
    solve();
    For(i,1,kp) Print(ans[i]),putchar('\n');
    return 0;
}

三、树上莫队

1. 基础思想

普通的莫队只能针对于序列问题进行求解。

处理树上问题时，有一种显然的想法是将树转录为一段序列。

如何将树转录为序列，是将算法进行扩展的瓶颈所在。

用平时使用的dfs序进行转录，发现并不能保证路径序列[l,r]可以扩展到相邻的区间。

这时，欧拉序列的功能就体现出来了。

欧拉序列(又名括号序)：

树上每个节点第一次遍历和回溯时，都将其加入序列，以此方式产生的序列即为欧拉序列。

以此树为例：

欧拉序列为：A B C D D E E C B F G H H G F A

这时我们可以发现，对于树上路径问题，

第一次经过节点时将它计入答案，第二次经过则删除它，中间的节点不会对询问产生实际影响，

这样做同时保证了答案向周围区间扩展是成立的。

故 基于欧拉序列，树上莫队是完全可以实现的。

2. 具体实现

询问离线，维护树的欧拉序列，维护莫队操作即可。

特别的，在树上[u,v]之间的路径中会产生两种不同询问：

不妨设 first_u<first_v

1. 若lca(u,v) {\ne} u 访问欧拉序列时，会发现lca还没有回溯，答案会少统计lca的信息，故需要额外加上lca的贡献，访问区间为[last_u,first_v]。

2. 若lca(u,v)=u 访问欧拉序列无误，访问区间为[first_u,first_v]。

处理询问时：

第一次经过节点则计入新的信息，第二次经过则将信息删除即可。

此过程可以用vis数组进行维护，每次经过节点u，就将vis_u{\oplus}=1，每次判断vis_u是0或1即可。

3. 实现

int n,m,B,f[N],cnt;
struct Edge{int v,nxt;}e[N<<1];
void insert(int u,int v){e[++cnt]=(Edge){v,f[u]}; f[u]=cnt;} 
struct Query{
    int id,l,r;
    int p; // 存储lca  
    bool operator < (const Query &tmp) const { return l/B==tmp.l/B?r<tmp.r:l/B<tmp.l/B;} 
}q[N];
int dep[N],fa[N][18],top,seq[N],first[N],last[N];
void dfs(int u){
    seq[++top]=u; first[u]=top;
    dep[u]=dep[fa[u][0]]+1;
    for(int i=1;i<=15;i++) fa[u][i]=fa[fa[u][i-1]][i-1];
    for(int i=f[u];i;i=e[i].nxt){
        int v=e[i].v;
        if(v!=fa[u][0]){ 
            fa[v][0]=u;
            dfs(v);
        }
    }
    seq[++top]=u; last[u]=top;
}
int lca(int u,int v){
    if(dep[u]<dep[v]) swap(u,v);
    for(int i=15;i>=0;i--) if(dep[fa[u][i]]>=dep[v]) u=fa[u][i];
    if(u==v) return u;
    for(int i=15;i>=0;i--){
        if(fa[u][i]!=fa[v][i]){
            u=fa[u][i];
            v=fa[v][i];
        }
    }
    return fa[u][0];
}
void rev(int pos,int &Ans){
    vis[pos]^=1;
    if(!vis[pos]){/*删除信息*/} 
    else{/*插入信息*/ } 
} 
void solve(){
    int l=1,r=0,Ans=0;
    sort(q+1,q+m+1);
    For(i,1,m){
        const Query &que=q[i];
        while(l>que.l) rev(seq[--l],Ans);
        while(r<que.r) rev(seq[++r],Ans);
        while(l<que.l) rev(seq[l++],Ans);
        while(r>que.r) rev(seq[r--],Ans);
        if(que.p) rev(que.p,Ans);
        ans[que.id]=Ans;
        if(que.p) rev(que.p,Ans);
    }
}
int main(){
    read(n); read(m);
    For(i,1,n) read(a[i]);
    For(i,1,n-1){
        int u,v; read(u),read(v);
        insert(u,v),insert(v,u);
    }
    dfs(1);  B=sqrt(top);
    For(i,1,m){
        int u,v; read(u),read(v);
        if(first[u]>first[v]) swap(u,v);
        int p=lca(u,v);
        if(u==p) q[i]=(Query){i,first[u],first[v],0};
        else q[i]=(Query){i,last[u],first[v],p};
    }
    solve();
    For(i,1,m) cout<<ans[i],putchar('\n'); 
    return 0;
}

4. 补充：

(1). 树上带修莫队

在树上莫队化树上问题为序列问题的思想基础下，将莫队以带修莫队的方式进行维护。

块长 ：S=(nt)^{\frac{1}{3}}

复杂度 O(n^{\frac{5}{3}})

(2). 真·树上莫队

上文是将树上问题转化为序列问题，下文将补充直接在树上操作的树上莫队。

(但 真·树上莫队 的泛用性似乎并不多，故不重点介绍。)

排序方式：

基于树分块思想：

令 lim 为希望块的大小，对于整个树 dfs，当子树的大小大于 lim 时，就将它们分在一块。

容易想到：对于根，可能会剩下一些点，于是将这些点分在最后一个块里。

操作方法：

用栈维护当前节点作为父节点访问它的子节点，

当从栈顶到父节点的距离大于希望块的大小时，

弹出这部分元素分为一块，最后剩余的一块单独作为一块。

最后的排序方法：

若第一维时间戳大于第二维，交换它们，按第一维所属块为第一关键字，第二维时间戳为第二关键字排序。

四、回滚莫队

1. 基础思想

普通莫队在处理某些问题时，如区间最大值等。

会发现莫队的插入操作很容易实现，但删除操作难以快速进行。

这时，我们可以放弃删除操作，只进行插入操作，恢复过程交给回滚来进行。

同理，增加操作难以进行时，仍然可以采取此类思想处理问题。

2. 具体实现

以只进行增加的回滚莫队为例。

排序后，按顺序处理询问：

枚举每一个对于询问分出的块，将莫队区间左右端点分别设为块的左端点加1和块的左端点；

如果询问的左右端点所属的块相同，那么直接扫描区间回答询问；

如果询问的左右端点所属的块不同：

如果询问的右端点大于莫队区间的右端点，那么不断扩展右端点直至莫队区间的右端点等于询问的右端点；

不断扩展莫队区间的左端点直至莫队区间的左端点等于询问的左端点；

回答询问；

撤销莫队区间左端点的改动，使莫队区间的左端点回滚到 B 的右端点加 1。

3. 复杂度证明和块长选取

假设回滚莫队的分块大小是 S：

对于左、右端点在同一个块内的询问，可以在 O(S) 时间内计算；

对于其他询问，考虑左端点在相同块内的询问，它们的右端点单调递增，移动右端点的时间复杂度是 O(n)，

而左端点单次询问的移动不超过 S，因为有 {\frac{n}{b}} 个块，所以总复杂度是 O(mb+\frac{n^2}{b})的，取 S=\frac{n}{\sqrt{m}} 最优，时间复杂度为 O(n\sqrt{m})。

4. 实现

struct Query{
    int id,l,r;
    bool operator < (const Query &tmp) const {return P[l]==P[tmp.l]?r<tmp.r:P[l]<P[tmp.l];} 
}q[N];
int Tot,L[N],R[N];
void build(){
    B=n/sqrt(m); if(B==0) B=sqrt(n); // 防止 n<sqrt(m) 导致 B=0  
    Tot=n/B; // 预处理块的左右端点 
    For(i,1,Tot) L[i]=(i-1)*B+1, R[i]=i*B; 
    if(R[Tot]<n) Tot++, L[Tot]=R[Tot-1]+1, R[Tot]=n;
    For(i,1,Tot) For(j,L[i],R[i]) P[j]=i; 
}
void solve(){ 
    sort(q+1,q+m+1);
    for(int i=1,p=1;p<=Tot;p++){ // 枚举块
        //  清空标记 执行新的块内的操作 
        int l=R[p]+1,r=R[p],Ans=0;
        for(;P[q[i].l]==p&&i<=m;i++){ 
            const Query &que=q[i];
            if(P[que.l]==P[que.r]){ 
                // 在块内的区间暴力进行操作
                continue ;
            }
            while(r<que.r){
                ++r;add_R();   // 扩展右端点
            }
            int l_=l; long long tmp=Ans;
            while(l>que.l){
                --l;add_L();  // 扩展左端点
            }
            ans[que.id]=Ans;
            while(l<l_){  // 以下回滚
                Delete_sth(); // 还原状态 如将数组恢复原状
                l++;
            }
            Ans=tmp;
        }
    }
}

5. 备注

由于回滚莫队本身访问顺序的不同，

故在实际运用中一般不与奇偶排序优化一同使用。

五、 莫队二次离线

暂无
(蒟蒻作者还没学会)

六、莫队优化 以及 搭配技巧

1. 值域分块

一些简单的莫队问题可以在完成区间移动后直接O(1)的访问答案。

但像以下问题，如：

1. 在 [l,r] 这段区间中数值在 [a,b] 中的数的个数，

2. 求在区间[l,r]中满足l{\le}i{\le}r ，b{\ge}p_i 或 p_i{\le}a的 i 的个数。

此类问题难以以O(1)的时间直接访问答案，可以采取值域分块的方式用O({\sqrt{n}})的时间进行答案的访问。

示例

void init(){ // 值域分块  
    B=sqrt(n); Tot=n/B;
    For(i,1,Tot) L[i]=(i-1)*B+1, R[i]=i*B;
    if(R[Tot]<n) Tot++, L[Tot]=R[Tot-1]+1, R[Tot]=n; 
    For(i,1,Tot) For(j,L[i],R[i]) P[j]=i;
}
int cnt[N],bl[N],blo[N];
PII ask(int l,int r){
    int res=0,kp=0;
    if(P[l]==P[r]){
        For(i,l,r){
            if(cnt[i]) res++;
            kp+=cnt[i];
        }
    }
    else{
        For(i,l,R[P[l]]){
            if(cnt[i]) res++;
            kp+=cnt[i];
        }
        For(i,L[P[r]],r){
            if(cnt[i]) res++;
            kp+=cnt[i];
        }
        For(i,P[l]+1,P[r]-1){
            res+=bl[i];
            kp+=blo[i];
        }
    }
    return make_pair(kp,res);
}
void solve(){
    int l=1,r=0;
    sort(q+1,q+m+1);
    For(i,1,m){
        const Query &que=q[i];
        while(l>que.l) add(s[--l]);
        while(r<que.r) add(s[++r]);
        while(l<que.l) del(s[l++]);
        while(r>que.r) del(s[r--]);
        ans[que.id]=ask(que.a,que.b);
    }
}