搞点抽象的
yangzichen1203
·
·
算法·理论
点
如在序列上的点，在树上的点，在二维平面上的点等。
范围
如区间，子树，链，半平面等。
等价类
等价类是点和范围产生的。点和范围是对偶的。
范围的等价类
假设有 m 个范围。则一个等价类代表一个点集，满足在所有 m 个范围内外情况完全一致。
我们设 m 个范围最多产生 P(m) 个等价类，显然要求 P(i)\le n。
点的等价类
假设有 n 个点。则一个等价类代表一个范围集，满足在对所有 n 个点的包含情况完全一致。
我们设 n 个点最多产生 P'(n) 个等价类，显然要求 P'(i)\le m。
范围修改查询
信息可以快速合并。
存在两个集合 D,O。（Data，Operation）
信息可以以以下 3 种方式合并：
-
-
-
有 n 个点，每个点上有一个定义在 D 上的信息。
有 m 次操作，每次操作给定一个范围。如果是修改操作，则有一个定义在 O 上的操作 X，需要对范围中所有点 a\to a\times X；如果是查询操作，则需要回答范围中所有点信息合并后的结果。
可以认为每次合并需要 1 份代价。
范围划分树
就是一棵能把范围划分成较少节点的有根树，满足任何一个节点只有 O(1) 个儿子，任何一个节点的信息可以由其所有子节点的信息合并而来。
代价
如果能将任何一个范围划分成 O(T) 个节点，即可做到在线 O(mT) 范围修改查询。
证明：使用懒标记即可。
等价类分治
是一种最优的离线范围修改查询算法。
具体见 https://www.luogu.com.cn/article/rs8zdm83 。
代价
离线范围修改查询的代价为
\boxed{O\left(m\max_{i=1}^{m} \dfrac{P(i)}{i}\right)}
证明：见 https://qoj.ac/files/ISAAC_2021_paper_100.pdf 。
近最优的在线范围修改查询算法
是一种近最优的在线范围修改查询算法。
具体见 https://www.luogu.com.cn/article/o6pe9wm3 。
代价
在线范围修改查询的代价为
\boxed{\tilde{O}\left(m\max_{i=1}^{m} \dfrac{P(i)}{i}\right)}
证明：见 https://www.luogu.com.cn/article/o6pe9wm3 。
莫队
信息不可快速合并。
普通莫队
给定初始 n 个点和 m 个范围 S_{1\sim m}。
要求找到一个范围的排列，使得代价 \sum_{i=0}^{m-1}|S_i\oplus S_{i+1}| 尽可能地小。
代价（莫队大定理）
莫队的转移代价为
\boxed{\tilde{O}\left(n\max_{i=1}^{n} \dfrac{P'(i)}{i}\right)}
证明：见 https://www.luogu.com.cn/article/o6pe9wm3 。
回滚莫队
给定初始 n 个点和 m 个范围 S_{1\sim m}。
需要维护一个集合，只允许向该集合加入一个点或回退上一次操作，使得该集合到达过所有范围。
代价
如果存在代价为 O(T) 的普通莫队，则存在代价为 O(T\log m) 的回滚莫队。
证明：在普通莫队构造出的排列上建立一棵线段树，每个线段树节点存放两儿子的交集，进行线段树分治即可做到 O(T\log m) 的代价。
在线化莫队
需要在线的得到一些范围。
代价
不是很清楚，应该能达到范围修改查询的代价下界。
附表
| 范围 |
等价类函数 |
对偶范围等价类函数 |
范围修改查询时间复杂度 |
莫队时间复杂度 |
| 区间 |
O(\min(i,n)) |
O(\min(i^2,m)) |
O(m\log n) |
O(n\sqrt m) |
| 子树 |
O(\min(i,n)) |
O(\min(i,m)) |
O(m\log n) |
O(n\log m) |
| 链 |
O(\min(i,n)) |
O(\min(i^2,m)) |
O(m\log n) |
O(n\sqrt m) |
| 正交矩形 |
O(\min(i^2,n)) |
O(\min(i^4,m)) |
O(m\sqrt n) |
O(nm^{\frac{3}{4}}) |
| 半平面 |
O(\min(i^2,n)) |
O(\min(i^2,m)) |
O(m\sqrt n) |
O(n\sqrt m) |