莫队

介绍

对于区间查询问题，通过离线对询问排序，配合序列分块和双指针移动，以均摊复杂度。

原理

序列分块

和普通分块一样，分成 $\sqrt n$ 个块，每个块的大小为 $\sqrt n$

排序规则

• 先按照区间左端所属块排序
• 左端在同一块的，按右端排序

双指针移动

• 左指针
  • 在一个块里来回移动，每次 $O(\sqrt n)$，最多 $q$ 次
  • 需要换块时 $O(n)$，换块最多 $\sqrt n$ 次
  • 总共移动 $O((q + n) \sqrt n)$
• 右指针
  • 左指针在同一块时，右指针单调递增，最多 $n$ 次
  • 左指针换块时，右指针 $O(n)$，换块最多 $\sqrt n$ 次
  • 总共移动 $O(n \sqrt n + n) = O(n \sqrt n)$

复杂度

总共 $O((q + n) \sqrt n)$

实现

查询区间和为例

数据结构

• 查询结构

struct Query{
    // 闭区间 [l, r]
    int id, l, r;
};
vector<Query> query;

• 块结构

struct Block{
    int l, r;
}
vector<Block> block;
vector<int> belong;

• 原始序列和查询结果

vector<int> org, ans;
int sum = 0;

功能函数

• 排序

bool cmp(Query &a, Query &b){
    // 左端在同一个块里，按右端排序
    if(belong[a.l] == belong[b.l]) return a.r < b.r;
    // 左端在不同块里，按块排序
    return belong[a.l] < belong[b.l];
}

• 指针移动

// 纳入
void include(int x){
    sum += org[x];
}
// 排除
void exclude(int x){
    sum -= org[x];
}

主函数

void mo(){
    sort(query.begin(), query.end(), cmp);
    // 空区间 [1, 0]
    int l = 1, r = 0;
    for(auto &q: query){
        // 先扩展
        while(l > q.l) include(--l);
        while(r < q.r) include(++r);
        // 再收缩
        while(l < q.l) exclude(l++);
        while(r > q.r) exclude(r--);
        // 记录结果
        ans[q.id] = sum;
    }
}

奇偶排序

问题

• 一块查询中，右指针开始时偏左，最后偏右
• 左指针同块时，右指针一直向右
• 左指针换块时，右指针猛回头到下一块查询右端的最左位置，效率低

优化

• 奇偶排序
  • 奇数块，右端升序
  • 偶数块，右端降序
• 换块时右指针波浪形走位，无效步数减少

实现

只需要修改排序规则

bool cmp(Query &a, Query &b){
    // 左端不在一个块里，按块排序
    if(belong[a.l] != belong[b.l]) 
       return belong[a.l] < belong[b.l];
    // 左端在同一个块里，按右端奇偶排序
    return (belong[a.l] & 1) ? a.r < b.r : a.r > b.r;
}