莫队算法

普通莫队

如果区间 $[l,r]$ 的答案可以在 $O(1)$ 的时间复杂度内转移到 $[l+1,r], [l-1,r], [l, r+1], [l, r-1]$,那么可以通过将区间按平方分块来降低复杂度。

将每个询问按左端点所在块号进行排序,同一个块内的按照右端点进行排序。这样一共只有 $sqrt(n)$ 个块。 我们考虑处理一个块内所有询问的复杂度:假设这个块内有 $q$ 个请求。因为对于一个块内的所有询问都是按右端点进行排序的,那么我们移动右端点的复杂度就是 $O(n)$ 的,移动左端点的复杂度是 $sqrt(n) \times q$。

这也是为什么区间内要按右端点排序的原因,不然的话移动右端点的复杂度就是 $n \times q$。

对于复杂度计算,考虑每个询问都会使左端点移动 $sqrt(n)$;每计算一个块,右端点都会移动 $n$。那么总的时间复杂度就近似为 $Q \times sqrt(n) + n \times sqrt(n)$。

1
2
3
4
5
6
7
8
9
int S = sqrt(n); // 可以根据题目适当调整

struct Query{
int l,r,id;
};
bool cmp(const Query& A,const Query& B){
if(A.l / S == B.l / S) return A.r < B.r;
return A.l < B.l;
}

一道模板题:bzoj 2038

带修改莫队

对于带修改操作的题目,我们要额外记录一维时间戳。那么每个询问可以表示为一个三元组 $(l,r,time)$。

那么它的转移就变成了:

  • $(l+1,r,time)$
  • $(l-1,r,time)$
  • $(l,r+1,time)$
  • $(l,r-1,time)$
  • $(l,r,time+1)$
  • $(l,r,time-1)$

然后它的分块是按照 $n^{\frac{2}{3}}$ 大小为一块,一共分成了 $n^{\frac{1}{3}}$ 块。总的时间复杂度是 $O(n^\frac{5}{3})$。

排序的第一关键字是左端点所在块号;第二关键字是右端点所在块号;第三关键字是时间。

简单证明复杂度:

对于固定的左右端点块,时间移动的复杂度为 $O(n)$,左右端点移动的复杂度为 $O(n^{\frac{2}{3}})$。

左右块的种类数是 $O(n^{\frac{1}{3} \times n^{\frac{1}{3})$。

所以最后的复杂度:$O(n^\frac{5}{3} + n^\frac{4}{3})$

1
2
3
4
5
6
7
8
9
10
11
12
struct Query {
int l, r, t, id;
bool operator<(const Query &rhs) const {
if (l / S == rhs.l / S) {
if (r / S == rhs.r / S)
return t < rhs.t;
else
r < rhs.r;
}
return l < rhs.l;
}
};