序号 | 标题 | 作者 | 发表时间 | 费用 | 订购数 | 操作 |
---|
Bob 喜欢线段树。
众所周知,ZJOI 的第二题有很多线段树。
Bob 有一棵根为 $[1, n]$ 的广义线段树。Bob 需要在这个线段树上执行 $k$ 次区间懒标记操作,每次操作会等概率地从 $[1, n]$ 的所有 $\dfrac{n(n+1)}{2}$ 个子区间中随机选择一个。对于所有在该次操作中被访问到的非叶子节点,Bob 会将这个点上的标记下推;而对于所有叶子节点(即没有继续递归的节点),Bob 会给这个点打上标记。
Bob 想知道,$k$ 次操作之后,有标记的节点的期望数量是多少。
【具体定义】
线段树:线段树是一棵每个节点上都记录了一个线段的二叉树。根节点记录的线段是 $[1, n]$。对于每个节点,若它记录的线段是 $[l, r]$ 且 $l \neq r$,取 $m = \lfloor \dfrac{l+r}{2} \rfloor$,则它的左右儿子节点记录的线段分别是 $[l, m]$ 和 $[m + 1, r]$;若 $l = r$,则它是叶子节点。
广义线段树:在广义的线段树中,$m$ 不要求恰好等于区间的中点,但是 $m$ 还是必须满足 $l \leq m < r$ 的。不难发现在广义的线段树中,树的深度可以达到 $O(n)$ 级别。
线段树的核心是懒标记,下面是一个带懒标记的广义线段树的伪代码,其中 `tag` 数组为懒标记:
注意,在处理叶子节点时,一旦他获得了一个标记,那么这个标记会一直存在。
你也可以这么理解题意:有一棵广义线段树,每个节点有一个 $m$ 值。一开始 `tag` 数组均为 $0$ ,Bob 会执行 $k$ 次操作,每次操作等概率随机选择区间 $[l, r]$ 并执行 `MODIFY(root,1,n,l,r)`;。 最后所有 `Node` 中满足 `tag[Node]=1` 的期望数量就是需要求的值。