莫队算法简介

用途

莫队算法是一种专门用于处理离线区间查询问题的算法框架。它特别擅长解决那些区间信息难以快速合并的问题（即不满足线段树、树状数组所需结合律的问题）。

典型的应用场景包括：
* 区间内不同元素的个数。
* 区间内出现次数为 k 的元素个数。
* 区间内每个数出现次数的平方和。
* 给定一棵树，查询一条路径上的某些信息（树上莫队）。

总而言之，只要一个问题允许离线处理，并且能快速计算出在当前区间 [L, R] 的基础上，增加/删除一个元素（即移动到 [L-1, R], [L+1, R], [L, R-1], [L, R+1]）后新区间的答案，就可以考虑使用莫队算法。

优势

通用性强：适用范围广，对于许多不满足特定代数性质的区间问题，莫队是为数不多的高效解法之一。
思维直观：其核心思想“暴力移动指针”非常朴素，易于理解。难点通常在于设计 add 和 remove 函数，而非算法框架本身。
代码实现相对简单：相比于主席树、树套树等复杂数据结构，莫队算法的框架固定，代码量较小，在比赛中更易实现且不易出错。
“优雅的暴力”：它将朴素的 O(N*Q) 暴力优化至 O((N+Q)√N) 级别，在常规数据范围下（如 2e5）足以通过。

劣势

强制离线：这是莫队算法最大的限制。它必须预先知道所有的查询，无法处理强制在线（即必须立即回答当前查询才能接收下一个查询）的问题。
不支持修改：基础的莫队算法无法处理区间修改或单点修改操作。对于带修改的问题，需要使用更复杂的“带修莫队”，实现难度和常数都会增加。
效率瓶颈：O(N√N) 的复杂度在 N 和 Q 规模更大时（如 5e5 或更高），可能会超时。它通常劣于线段树等对数级复杂度 O(Q log N) 的算法（当后者可用时）。

用法

莫队算法的实现步骤非常固定，可以视为一个模板：

问题转化：思考如何维护区间信息。核心是设计 add(index) 和 remove(index) 两个函数，它们负责在 O(1) 或 O(log N) 的时间内，将 index 位置的元素加入或移出当前窗口，并更新答案。
封装查询：将每个查询封装成一个结构体，至少包含三个成员：左端点 l、右端点 r 和原始输入顺序 id。
```
struct Query {
    int l, r, id;
};
```
分块与排序：
- 计算块的大小 block_size = sqrt(n)。
- 对所有查询进行排序。排序规则是算法的精髓：
  - 主关键字：按左端点 l 所在的块编号 l / block_size 升序排序。
  - 次关键字：如果块编号相同，则按右端点 r 排序。
排序优化（奇偶性排序）：为了进一步减少右指针的大幅度回跳，在块编号相同时，可以根据块编号的奇偶性决定 r 的排序方式。
- 如果块编号是奇数，r 按升序排。
- 如果块编号是偶数，r 按降序排。
  这会让右指针在处理完一个块后，能以较小的移动成本过渡到下一个块，如同“S”形移动。
```
sort(queries.begin(), queries.end(), [&](const Query& a, const Query& b) {
    int block_a = a.l / block_size;
    int block_b = b.l / block_size;
    if (block_a != block_b) return block_a < block_b;
    if (block_a % 2) return a.r < b.r;
    return a.r > b.r;
});
```
双指针移动：
- 初始化当前窗口 [current_l, current_r]（通常为 [0, -1] 或 [1, 0]）。
- 遍历排序后的查询数组。
- 对于每个查询 q，通过四个 while 循环，将 [current_l, current_r] 移动到 [q.l, q.r]。移动过程中不断调用 add 和 remove 函数更新状态。
```
int l = 0, r = -1;
for (const auto& q : queries) {
    while (l > q.l) add(--l);
    while (r < q.r) add(++r);
    while (l < q.l) remove(l++);
    while (r > q.r) remove(r--);
    // 此时 current_answer 就是 q 对应的答案
    answers[q.id] = current_answer;
}
```
存储并输出答案：
- 创建一个 answers 数组，用于存储结果。
- 在处理完一个查询后，根据其原始 id，将答案存入 answers[q.id]。
- 所有查询处理完毕后，按 0 到 q-1 的顺序遍历并输出 answers 数组。

注意事项和特点

特点：离线算法。必须先读入所有查询才能开始处理。
特点：分块思想。通过分块来指导排序，是性能优化的关键。
特点：贪心排序。排序规则是一种贪心策略，旨在最小化指针移动的总距离。
特点：“优雅的暴力”。本质上是对暴力枚举的智能优化，而非利用特定数据结构性质。
注意：处理 1-based 和 0-based 下标的转换，避免边界错误。
注意：add 和 remove 函数的实现必须正确且高效，这是算法性能的核心。
注意：移动指针的四个 while 循环的顺序可以调整，但扩展区间的 while（r < q.r, l > q.l）最好写在收缩区间（r > q.r, l < q.l）之前，可以避免窗口变为空的边界情况。
注意：对于多组测试数据，每次 solve 函数开始前，务必重置全局状态（如计数数组、当前答案等）。
注意：答案的数据范围可能超过 int，需要使用 long long。