莫队算法分块大小取 sqrt(n)是为了使总时间复杂度最优，此时左端点移动代价为 m×sqrt(n)，右端点为 n×sqrt(n)，合计 o((n+m)×sqrt(n))；实际常用 ceil(sqrt(n)) 并特判 block≥1。
莫队算法的分块大小为什么取 sqrt(n)
分块大小直接决定莫队的时间复杂度。设序列长为 n，查询数为 m，若块大小设为 B，则左端点在块内移动总代价 ≤ m × B，右端点跨块单调移动总代价 ≤ (n / B) × n。两者相加后对 B 求导得最小值点在 B = sqrt(n)，此时总复杂度为 O((n + m) × sqrt(n))。实际中常用 B = ceil(sqrt(n)) 或 B = static_cast<int>(sqrt(n)) + 1</int>，避免除零或整数截断导致块数错误。
离线查询排序的关键：按左端点所在块升序，同块内右端点奇偶分治
标准排序逻辑是：l / block 升序；同块时，若块编号为偶数，r 升序；若为奇数，r 降序。这个奇偶分治能显著减少右端点来回跳动——实测比单纯“同块按 r 升序”快 15%~30%。注意：必须用整数除法（/），不能用 floor(l * 1.0 / block)，否则浮点误差可能让相邻 l 落入不同块。
常见错误包括：
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 把
block定义成double或未取整，导致l / block类型不匹配 - 排序比较函数里漏写
return false在相等情况（C++ 中 strict weak ordering 要求） - 用
vector::sort但没传自定义 comparator，仍按默认字典序排
struct Query 的设计与排序实现细节
典型结构体需包含原始索引 id、左右端点 lr，以及预计算的块号 blk（可选，避免排序时重复除法）。排序代码通常长这样：
int block = sqrt(n);
sort(qs.begin(), qs.end(), [block](const Query& a, const Query& b) {
if (a.l / block != b.l / block)
return a.l / block b.r) : (a.r <p>这里用 <code>a.l / block & 1</code> 判断奇偶比 <code>(a.l / block) % 2 == 1</code> 更安全，避免负数除法（虽然题目通常 l ≥ 1）。如果输入下标从 0 开始且 <code>n</code> 很小（比如 <code>n=1</code>），<code>block</code> 可能为 0，必须提前特判：<code>block = max(1, (int)sqrt(n));</code></p><h3>莫队排序后移动指针的实际开销在哪</h3><p>真正影响性能的不是排序本身（<code>O(m log m)</code>），而是后续 <code>add()</code>/<code>del()</code> 函数的常数和缓存友好性。例如用 <code>unordered_map</code> 维护频次会拖慢 3 倍以上，改用数组+偏移（如值域集中）或 <code>vector<int></int></code> 直接下标访问更稳。另外，<code>l</code> 和 <code>r</code> 指针应声明为局部变量并反复复用，避免每次查询都 new 临时变量。一个容易被忽略的点是：初始状态的 <code>l=1, r=0</code>（空区间）必须保证 <code>add()</code> 对单点有效，否则第一次扩展就出错。</p>C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
