分类：OI

区间除和开方要解决的就是以下两种操作：

1. \(\forall i \in [l, r], \lfloor \frac{a_i}{d} \rfloor \to a_i\)
2. \(\forall i \in [l, r], \lfloor \sqrt{a_i} \rfloor \to a_i\)

正常的标记操作是很难实现这些操作的，然而我们可以把这些操作进行一些转换，因为这些操作在一定的值域范围内是可以批量处理的。换句话说，如果区间内极差小，那么除法或开方的效果在区间内等效，所以可以转化成减法来进行实现。

拿除法举例：在区间\((l, r)\)中，如果\( \max(S) – \lfloor \frac{\max(S)}{d} \rfloor = \min(S) – \lfloor \frac{\min(S)}{d} \rfloor \)，那么我们就可以把这个差值作为减数，用正常的加减方式进行标记。

继续阅读线段树实现区间除和开方