莫队二次离线

发表于 更新于 分类于 阅读次数：

莫队算法可以通过单点增量的方式以 \(O(n\sqrt{n}K)\) （认为 \(n, q\) 同阶）的复杂度离线处理若干区间信息询问。 其中每次单点增量，即每次端点移动的复杂度为 \(O(K)\) 。

大多数情况下端点移动的复杂度是 \(O(1)\) 的，这样的问题一般是统计区间内的“数”。 而统计区间内的“数对”这样的问题往往难以 \(O(1)\) 处理端点移动。

莫队二次离线或许能处理这样的问题。

什么用

一般莫队有 \(O(n\sqrt{n})\) 次端点移动，如果要用数据结构维护信息的话， 就有 \(O(n\sqrt{n})\) 次修改和 \(O(n\sqrt{n})\) 次查询。

而莫队二次离线能够优化为成 \(O(n)\) 次修改和 \(O(n\sqrt{n})\) 次查询， 从而允许使用一些修改复杂度大而查询复杂度小的方式来维护信息。 例如分块，如果能 \(O(\sqrt{n})\) 修改和 \(O(1)\) 查询的话，总的复杂度就是 \(O(n\sqrt{n})\) 。

但是有两个前提：

  • 维护的信息有一定可减性，换句话说必须保证每次询问 \([l, r]\) 与 \(r + 1\) 产生的贡献时， 需要能够用 \([1, r]\) 与 \(r + 1\) 产生的贡献减去（或者其他方式）\([1, l)\) 与 \(r + 1\) 产生的贡献代替。
  • 维护的信息有一定可加性，换句话说在每次询问前在不知道当前的 Ans 的情况下可以得到 Ans 的改变量（或某种改变方式）。

怎么用

考虑每次右端点右移的过程（右端点左移以及左端点移动是类似的）。

每次右端点 \(r\) 从 \(r_0\) 移动到 \(r_1\) 时，对于其中的每一个 \(r\) ，都需要查询 \([l, r - 1]\) 与该点产生的贡献。 考虑差分，利用上面提到过的可减性，查询 \([1, r]\) 与 \(r + 1\) 产生的贡献和 \([1, l)\) 与 \(r + 1\) 产生的贡献。

Part 1

\([1, r]\) 与 \(r + 1\) 产生的贡献只与 \(r\) 有关，可以记为 \(f_r\) 。 那么预处理 \(f_r\) 只需从小到大一个个加点维护当前的 \([1, r]\) 并询问出 \(f_r\) 。

这个过程需要 \(O(n)\) 次修改和 \(O(n)\) 次查询。

参考实现：

1
2
3
4
5
// a[i] 是第 i 个元素
for(int i = 1; i <= n; i ++) {
	f[i] = Query(a[i]);
	Modify(a[i]);
}

另外如果需要卡常，可以将 \(f\) 做一遍前缀和，这样后续查询 \([r_0, r_1]\) 总的贡献就可以 \(O(1)\) 计算了（不影响复杂度）。

Part 2

\([1, l)\) 与 \(r + 1\) 产生的贡献可以二次离线，在 \(l\) 处存下 \(r + 1\) 之后再考虑计算。 这样做的空间复杂度是 \(O(n\sqrt{n})\) 的， 但事实上每次只需把 \([r_0, r_1]\) 这个区间存进 \(l\) 处而不是把每个数存进去就可以做到 \(O(n)\) 的空间复杂度了， 这样询问的时候也只需求 \([r_0, r_1]\) 整体的贡献，常数上还能少一个 \(O(n\sqrt{n})\) 的瓶颈。

离线处理上述的贡献，也和求 \(f_r\) 的过程类似，每次从小到大一个个加点维护当前的 \([1, l)\) ， 并对于 \(l\) 处存下的每一个数逐个询问 \([1, l)\) 与其产生的贡献即可。 这个过程需要 \(O(n)\) 次修改和 \(O(n\sqrt{n})\) 次查询。

参考实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int l = 1, r = 1;
for(int i = 1; i <= q; i ++) {
	int L = query[i].l, R = query[i].r; // 排序后的询问
	if(r < R) {
		vector[l].push_back(std::make_pair(r + 1, R));
		r = R;
	}
}

for(int i = 1; i <= n; i ++) {
	for(auto par : vector[i])
		for(int k = par.first; k <= par.second; k ++)
			Query(a[k]); // 这里用什么东西存一下结果就好了
	Modify(a[i]);
}