线段树实现区间除和开方

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

  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 \),那么我们就可以把这个差值作为减数,用正常的加减方式进行标记。

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