线段树例题

ShelTeR_Pr1me · 2022-07-20 19:40:12 · 个人记录

1. 给定一个序列，求一个区间内是否存在两个数的和为给定的 w。

两个数和能否为一个数，维护一个 pre 代表一个数可以与另一个数和为 w 的最靠右位置，维护 pre 最大值进行比较即可。

2. 给定一个序列，要求支持区间除法。

并查集快速找数然后朴素除。可以证明，在 a_i \le 2^{32} 次方下顶多除个 32 次，朴素解决即可，而快速找出哪些需要被除的数可以利用并查集解决（反正也没有修改操作）。

3. 给定一个序列，要求支持区间取模。

换成取模的话，维护区间最大值，如果连最大值都小于 p 就不用管，考虑解决掉比 p 大的数，然后更新最大值，直到最大值小于 p，这样时间复杂度是 \mathcal{O}(n \log a_i \log n)。其实暴力改就可以了。

4. 给定一个序列，有区间加，要求支持区间求 \gcd。

更相减损术，弄一个差分数组，维护差分数组的最大公约数，区间修改类似于差分考虑，也可以用单点修改两个点来解决问题。时间复杂度为 \mathcal{O}(n \log n \log a_i)。

5. 给定一个序列，有单点修改，要求求出一个区间上是否有一段差值为 k 的等差数列。

等差数列性质：

2. 无重复数字，维护 \operatorname{pre}。
3. 所有数 \bmod k 是同一个数，转换成差分维护区间 \gcd。