题目理解

我们需要处理多个区间查询，对于每个区间 $[l, r]$，定义事件种类 $t$ 的重要度为 $t \times (\text{该种类在区间内的出现次数})$，要求输出所有种类重要度的最大值。

关键难点

• 直接对每个询问暴力计算是 $O(NQ)$，不可行。
• 重要度计算不满足区间可加性，即不能简单通过前缀和或线段树合并信息。

核心思路

使用回滚莫队（Rollback Mo's Algorithm），一种离线分块算法。

算法步骤

1. 离散化

由于 $X_i$ 范围很大（最大 $10^9$），但实际不同种类数不超过 $N$，先将其映射到 $1 \dots M$（$M \le N$）。

2. 分块与排序

• 将序列分成大小为 $B \approx \sqrt{N}$ 的块。
• 将询问按左端点所在块编号分组，同一块内按右端点升序排序。

3. 处理同一块的询问

• 设当前块编号为 $blk$，该块的右边界为 $R_{blk} = (blk+1) \times B - 1$。
• 初始化右指针 $r = R_{blk}$，左指针 $l = R_{blk} + 1$。
• 对于该块内的每个询问 $[L, R]$：
  • 如果 $R \le R_{blk}$（询问完全在块内），直接暴力计算，复杂度 $O(B)$。
  • 否则：
    • 先移动右指针 $r$ 从 $R_{blk}$ 到 $R$（只增不减）。
    • 记录当前状态（称为快照），然后移动左指针 $l$ 从 $R_{blk}+1$ 到 $L$（只增不减，但会破坏计数）。
    • 计算当前区间答案。
    • 回滚左指针移动：恢复计数数组和最大值到快照状态。

4. 复杂度分析

• 右指针在每个块内单调右移，总移动 $O(N)$。
• 左指针每次询问移动 $O(B)$，总移动 $O(QB)$。
• 取 $B = \sqrt{N}$，总复杂度 $O((N+Q)\sqrt{N})$。

为什么用回滚莫队

普通莫队在移动指针时需支持添加和删除操作，但此问题中删除一个元素后，最大值可能难以快速更新（需要知道次大值等）。回滚莫队通过避免删除操作，只需支持添加和回滚，简化了最大值维护。

总结

通过离散化、分块排序、右指针单调移动、左指针回滚的技巧，在 $O((N+Q)\sqrt{N})$ 时间内高效解决所有查询，适用于 $N, Q \le 10^5$ 的数据规模。