柒葉灬 的博客

柒葉灬 的博客

莫队算法入门

posted on 2019-04-11 16:13:41 | under 算法学习 |

莫队算法


功能介绍

莫队就是解决形如询问区间 $[l,r]$ 这样形式的问题

如果答案计算从 $[l-1,r],[l+1,r],[l,r-1],[l,r+1]$ 转移到 $[l,r]$ 的复杂度是 $O(1)$ 的话,

那么莫队可以做到总复杂度 $O(n\sqrt{n})$


具体实现

普通莫队( $S=\sqrt{n}$ )

把每一个询问 $[L,R]$ 按照二元组 $[L/S,R]$ 排序,( $L/S$ 向下取整)

对于一个块来说,每一次询问左端点最多移动 $S$ 次,

右端点总共移动 $n$ 次,(右端点要从小到大)

还有块与块之间的移动最多是 $n$ 次。

所以总复杂度就是 $O(qS+n^2/S)$

$$qS=n^2/S$$

$$S^2=n^2/q$$

$$S=n/\sqrt{q}$$

一般 $q$ 与 $n$ 同阶,所以 $S$ 一般取 $sqrt{(n)}$ 就行了。


带修莫队( $S=n^\frac{2}{3}$ )

带修莫队就相当于多了一维时间,

排序的时候按照 $[block[l],block[r],t]$ 进行排序即可

设块的大小为 $S$

  1. 算上块与块之间移动的复杂度, $O({(\frac{n}{S})}^2n$ ,(实际上远远没有这么大)

  2. 算上每个块第三维移动的复杂度, $O({(\frac{n}{S})}^2m)$

  3. 算上每次询问第一维和第二维移动的复杂度, $O(mS)$

得到:复杂度: $O(mS+{(\frac{n}{S})}^2(m+n))$

算 $n$ 与 $m$ 同阶,则: $O(nS+\frac{n^3}{S^2})$

$$nS=\frac{n^3}{S^2}$$

$$S^3=n^2$$

$$S=n^\frac{2}{3}$$

得到总复杂度就是


普通树上莫队( $S=\sqrt{n}$ )

根据普通莫队,得:

需要让一个端点每次移动产生复杂度不会太高,

所以说每个块内的点必定要联通,

且块内的点不能太多。

可以用一个栈来计算每一个块

每一次 $dfs$ 的时候,当 $dfs$ 儿子的时候

判断增加的点是否超过 $B$ 值

如果有了就弹出,分成一个块。

那么这么做,显然块内点最少是 $B$ ,

最多的点的个数是 $3B$

因为作为一个块,最大的个数是 $2B-1$ ,

而剩余的点最多个数是 $B$ ,

所以最大的块点的个数就是约为 $3B-1$ 。

代码大致长成这样子:

void dfs(int f,int x){
    int t=top;
    for(int i=head[x];i;i=nxt[i]){
        int y=to[i];
        if(y==f)continue;
        dfs(x,y);
        if(top-t>=B){
            id++;
            while(t>top)block[stk[top--]]=id;
        }
    }
    stk[++top]=x;
}
int main(){
    dfs(0,1);
    while(top)block[stk[top--]]=id;
}

树上带修(多维)莫队(与普通带修莫队差不多)

(略