莫队算法入门

# 莫队算法 ----- ## 功能介绍 #### 莫队就是解决形如询问区间$[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$。 代码大致长成这样子： ```cpp 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; } ``` ------- ### 树上带修（多维）莫队（与普通带修莫队差不多） （略