普通莫队的时间复杂度分析:设块长为 \(B\),\(l\) 的移动次数是 \(O(mB)\) 的,\(r\) 的移动次数是 \(O(\frac{n}{B}n)\) 的,所以总时间复杂度为 \(O(mB+\frac{n}{B}n)\),考虑时间复杂度的平衡,取 \(B=\frac{n}{\sqrt{m}}\),则总时间复杂度为 \(O(n\sqrt{m})\)。
带修改的莫队的时间复杂度分析:设块长为 \(B\),\(l\) 的移动次数是 \(O(mB)\) 的,\(r\) 的移动次数是 \(O(\frac{n}{B}n+mB)\) 的,时间戳的移动次数是 \(O(\frac{n^2}{B^2}c)\)(\(c\) 为修改次数),\(B\) 取 \(O(n^{2/3})\) 最优,总时间复杂度为 \(O(n^{5/3})\)(设 \(n,m,c\) 同级)。
回滚莫队和普通莫队的时间复杂度分析类似,均为 \(O(n\sqrt{m})\),这里不再阐述。
树上莫队?拍扁放在数列上处理不香吗?
二次离线?不会。。。
bitset
配合莫队?这有一道板子 P3674 小清新人渣的本愿。
二维莫队?这个东西大概率不是正解。
标签:frac,mB,复杂度,次数,时间,莫队 From: https://www.cnblogs.com/dadidididi/p/17813955.html