莫队算法的耗时

序列莫队的复杂度证明

讨论

1. 对于同一块内的所有询问，右端点的移动是$O(n)$的，左端点的移动是$O(\sqrt n) \times O(\sqrt n)=O(n)$
2. 对于$q_i$和$q_{i+1}$再不在同一块中的询问，左端点移动$O(\sqrt n)$，右端点移动$O(n)$。这样的询问一共有$\sqrt n$个。总复杂度为$\sqrt n \times (O(\sqrt n)+O(n))=O(n\sqrt n)$

总复杂度为$O(n\sqrt n)$

思考

再确定莫队以后，要想怎样才能减小转移的时间消耗。比如，在我看来，树上莫队要用$DFS$序的话就会很慢，因为块内的节点可能隔的很远，而且可能排成很长的一条链。