线段树实现区间除和开方

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

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

Continue reading →

LibreOJ 2187:「SHOI2014」三叉神经树 – 题解

主要思路

先建好树,大概思考一下应该可以推导出:倍增找标记点,然后根到区间修改。然而正解也是这样写,只不过细节有点多,我在这里提一下:回答询问\(x\)时,先把他父亲提到根,然后找最近的点;找到了就把深度大的全部打标记反过来。

Continue reading →

P2597:「ZJOI2012」灾难 – 题解

主要思路

这道题就是 DAG 求支配树裸题,过程是这样的:先做一遍拓扑排序,然后对于第\(i\)个点\(u\)而言,前\(i – 1\)个点已经完成,所以其支配树上的父亲就是入边起点的 LCA。稍稍处理一下即可。然后再在支配树上进行 DFS 求出每个子树的大小即可。

Continue reading →