20260105 莫队总结

莫队

莫队是一种高效的离线处理区间查询问题的算法，本质是一种经过优化的暴力算法，该算法基于以下核心思想：当已知区间 [l, r] 的答案时，可以以 O(k) 的时间复杂度（k 通常为 1 或 log n）计算出相邻区间 [l±1, r] 和 [l, r±1] 的答案。

算法流程

1. 读取所有查询请求
2. 按照特定规则对查询进行排序
3. 依次处理每个查询，通过增量调整的方式从上一个区间移动到当前区间

示例移动路径：
[1, 3] → [1, 4] → [2, 4]

排序

采用双关键字排序：

1. 第一关键字：左端点 l 所在的块编号
2. 第二关键字：右端点 r 的值

时间复杂度

设块大小为 B，序列长度为 n，查询次数为 m：

• 左端点移动次数：O(mB)
• 右端点移动次数：O(n²/B)

当取 B = √(n²/m) 时，达到最优时间复杂度。通过合理选择块大小，可以确保整体复杂度为 O(n√m)。

代码

intcmp(qq a,qq b){//蝶形优化if(pos[a.l]^pos[b.l]){returnpos[a.l]<pos[b.l];}if(pos[a.l]&1){returna.r<b.r;}returna.r>b.r;}intmain(){sort(q+1,q+1+m,cmp);for(inti=1;i<=m;i++){while(l<q[i].l)ans-=!--t[a[l++]];while(l>q[i].l)ans+=!t[a[--l]]++;while(r<q[i].r)ans+=!t[a[++r]]++;while(r>q[i].r)ans-=!--t[a[r--]];cnt[q[i].id]=ans;}}