滚回莫队

引入:

增加型

使用场景

• 仅支持快速增加（如添加元素时$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]$ （块边界左侧）。