根号算法重谈

根号算法太多了只写了这次复习比较 edu 的内容，所以这并不是对根号算法的总结，而是魔怔（？）。

总的来说大多数根号算法就是套路化的平衡规划思想，虽然不知道为什么这玩意儿在大纲里是【9】级，NOIP 超纲了。

1 回滚莫队

提供一种写法。除了第一次学的时候照着抄的，我都用的我这个写法。

考虑回滚莫队本质上是按左端点分块之后，将左端点同块的询问放到一起，从右边的第一个整块开始对右端点扫描线，然后在查询的时候单独加入左端点所在散块的 \(B\) 个点，所以复杂度是 \(O(\frac{n^2}{B}+qB)\)，取 \(B=\frac{n}{\sqrt q}\) 得 \(O(n\sqrt q)\)。

那我想为什么一定要囿于莫队的形式，直接把左端点同块的拿出来跑扫描线不就行了。如果左右端点在同一个块直接跑暴力，这个暴力可以和单独加入左端点散块的暴力写成一个函数。

一个参考实现：

inline void BF(int id) {//这是暴力，id 表示当前询问编号
	DS::save();
	for (int i = ql[id]; i <= qr[id]; ++i) DS::insert(i);
	ans[id] = DS::query();
	DS::undo();//回滚
}

inline void solve(int id) {//做左端点都在 id 块内的询问
	sort(p[id].begin(), p[id].end(), [&](int x, int y) { return qr[x] < qr[y]; });//按右端点排序
	auto pos = p[id].begin();
	DS::init();
	for (int i = st[id + 1]; i <= n && pos != p[id].end(); ++i) {//对右端点扫描线
		DS::insert(i);
		while (pos != p[id].end() && qr[*pos] == i) qr[*pos] = ed[id], BF(*pos), ++pos;
	}
}

优点：感觉很好写啊，思路也会清晰一点。而且这东西可以跳出莫队维护信息的惯性思维，如【候选队互测2022】可爱多的字符串。

缺点：（可能是我的问题）常数有点大。

2 时间轴分块

核心思想是通过定期 \(S\) 时间重构将单次询问的修改降到 \(O(S)\) 级别，就可以在询问时暴力修改。一般来说时间复杂度需要在重构 \(O(\frac{q}{S})\) 次，修改 \(O(qS)\) 次，查询 \(O(q)\) 次之间平衡。

一般来说对于一般的数据结构难以修改/查询的信息，可以考虑时间轴分块。时间轴分块也是一种将复杂静态问题动态化的方法。

比如说对 DAG 可达性统计进行修改/查询，我说的不是 recall，是 QOJ1851 Directed Acyclic Graph。这个题比较 educational 的地方是，时间轴分块的定期重构除了将修改降到 \(O(S)\) 级别之外，还可以同时发挥维护修改/查询复杂的时间轴上区间信息的作用。

还有一个用途是时间轴分块之后 \(S\) 个修改把维护的数轴劈成 \(O(S)\) 段，平面劈成 \(O(S^2)\) 段之类的，代表有 [Ynoi2006] rmpq。有些情况下即使看起来没有修改也可以使用。

更多细节可以拜读 yzq 的文章。

3 带修莫队

带修莫队本质上是加了一维时间轴变成了三指针莫队。

考虑三指针莫队的另一种做法，对其中一维隔 \(S\) 时间做时间轴分块，以单次询问额外 \(O(S)\) 次修改的代价砍掉一维，然后在同一时间块内跑双指针的普通莫队。假设插入删除都是 \(O(1)\)，那么时间轴分块额外的修改总复杂度为 \(O(qS)\)，跑 \(\frac{q}{S}\) 遍 \(S\) 次询问的普通莫队复杂度为 \(O(\frac{q}{S}\cdot n\sqrt S)\)，其中普通莫队的块长取 \(B=\frac{n}{\sqrt S}\)。平衡 \(qS=\frac{q}{S}\cdot n\sqrt S\) 得到 \(S=B=n^{\frac{2}{3}}\) 时总复杂度为 \(O(qn^{\frac{2}{3}})\)，和我们学的带修莫队的块长以及复杂度分析一模一样，非常 interesting。

优点：感觉思路更加清晰，而且具有扩展意义，因为做了一个时间轴分块。可能会节省一些空间。时间复杂度分析也更简单，虽然一般来说都取固定块长。

缺点：（可能是我的问题）常数有点大。

有的时候可能某一维可能有一些特殊性质，这个做法可以多平衡一些复杂度，比如说 [Ynoi Easy Round 2019] 黑川赤音。