回滚莫队

FJ_00460 · 2025-03-30 19:23:56 · 个人记录

滚回莫队

引入:

普通莫队在查询转移时，会出现无法快速实现删除或增加操作的情况。

分为增加型，减少型

复杂度一样

增加型

专门解决只能快速增加元素，不能高效删除元素

通过分块，排序和回滚操作，避免了删除操作，优化到 O(n\sqrt n)

使用场景

• 仅支持快速增加（如添加元素时O(1)维护答案）
• 无法高效删除（删除后无法快速更新答案）
• 离线查询，可提前排序

核心思想

• 分块，分为大小为 \sqrt n的块
• 排序查询
  • 按左端点所在块号升序排序
  • 同一块内的查询，按右端点升序排序（确保右指针单调递增）
• 回滚操作
  • 右指针始终向右扩展（只增加元素）。
  • 左指针在同一块内向左扩展，但每次查询后回滚左指针的修改，避免删除操作。
• 分块与排序
  • 分块大小 block = \sqrt n
  • 排序规则
    • 第一关键字：左端点所在块号（升序）
    • 第二关键字：右端点（升序）
• 初始化指针
  • 维护当前区间[cur_l, cur_r]，初始为[block + 1, 0] （块边界右侧）。
  • 记录每个块的右端点R[block]。
• 处理每个查询
  • 假设当前查询为[L, R]
    • 情况1：L 和 R 在同一块内，暴力求解：遍历L, R，统计答案。
    • 情况2：L和R不在同一块
      • （1）扩展右指针：将cur_r移动到R，每一步调用add(cur_r)\维护当前最大值
      • （2）临时扩展左指针：从cur_l-1向左扩展到L，记录临时增加的元素及其计数（不修改全局计数）
      • （3）计算临时答案：利用临时扩展的左指针区间，计算当前最大值。
      • （4）回滚左指针：撤销临时扩展的左指针修改，恢复 cur_l到块边界右侧。

删除型

• 解决快速删除，不能高效增加
• O(n\sqrt n)

实现

• 分块，分为大小为 \sqrt n的块
• 排序查询
  • 按右端点所在块号升序排序
  • 同一块内的查询，按左端点降序排序（确保左指针单调递增）
• 回滚操作
  • 左指针始终向左扩展（只删除元素）。
  • 右指针在同一块内向右扩展，但每次查询后回滚右指针的修改，避免增加操作。
• 分块与排序
  • 分块大小 block = \sqrt n
  • 排序规则
    • 第一关键字：右端点所在块号（升序）
    • 第二关键字：左端点（降序）
• 初始化指针
  • 维护当前区间[cur_l, cur_r]，初始为[block - 1, 0] （块边界左侧）。