「提高 - 59」基础莫队

莫队

莫队算法是一种对询问进行分块的离线算法。

具体步骤

设询问的区间均位于 $[1, n]$。

我们将$[1, n]$ 分为 $\sqrt n$ 块，每块的长度为 $\sqrt n$。

对所有的询问按照左端点进行排序，左端点位于同一块（上面的分块）的询问属于同一组，我们再对每一组内部按照右端点升序排列。

int len = sqrt(n);
sort(p + 1, p + m + 1, [len](const node &a, const node &b) {
  int x = a.l / len, y = b.l / len;
  if (x == y) return a.r < b.r;
  return x < y;
});

对排序后的询问，我们暴力计算从 $[l, r]$ 变为区间 $[l', r']$，对答案的影响。如果能够以 $O(1)$ 的代价计算出 $[l, r]$ 转化为 $[l, r + 1]$、$[l, r - 1]$、$[l + 1, r]$、$[l - 1, r]$。那么从 $[l, r]$ 更新为区间 $[l', r']$ 的代价便是左右端点的变化之和。因为每一块内，左端点每次最多变化 $\sqrt n$，所有 $n$ 次询问的总代价为 $O(n\sqrt n)$。右端点因为在每块内部从 $1$ 一直递增，最多变为 $n$。一共有 $\sqrt n$ 块，所以总共的时间复杂度 $O(n\sqrt n)$。

下面的代码是查询区间和。

int l = 1, r = 0;
int sum = 0;
for (int i = 1; i <= m; i++) {
  while (l > p[i].l) sum += A[--l];
  while (r < p[i].r) sum += A[++r];
  while (l < p[i].l) sum -= A[l++];
  while (r > p[i].r) sum -= A[r--];
  Ans[p[i].id] = sum;
}

在移动区间端点时，建议先执行扩张操作，再执行收缩操作。这样可以保证每次删除的元素一定已经被加入过当前区间，避免在区间临时变空或左右端点交错时，对未加入过的元素执行删除操作，导致计数数组或答案状态出错。

---

比如说上一个区间为 $[1, 2]$, 当前区间为 $[4, 5]$。如果我们先收缩区间的话，会出现把 $1、2、3$ 从区间删除的操作，在查询区间和虽然不会出问题，但是在另一些问题中就可能影响答案或程序运行错误。

合理的步骤是先将 $[1, 2]$ 扩充为 $[1, 5]$，再收缩为 $[4, 5]$。