回滚莫队

回滚莫队

用途

有时区间问题只方便插入或只方便删除，若允许离线，则我们可以考虑回滚莫队。

方法

将询问按左端点块递增为第一关键字，右端点递增为第二关键字的方式排序。

每次左端点所在块更新时，我们将区间初始化为[块的右端点+1，块的右端点]。

  1. 左右端点在同一块内
    直接扫一遍区间求出答案。
  2. 左右端点不在同一块内
    先递增右端点，再递增左端点，回答询问后左端点回滚至块的右端点+1处。

时间

(O(n sqrt{n}))

【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/BunnyLutts/p/14622177.html