#PQJ472x426. QOJ 472_426

    ID: 2988 传统题 4000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:ZJOI 2020线段树模拟

QOJ 472_426

2 传统艺能 2.1 题目描述 Bob 喜欢线段树。 众所周知,ZJOI 的第二题有很多线段树。 Bob 有一棵根为[1, n] 的广义线段树。Bob 需要在这个线段树上执行k 次区间懒标记操作, 每次操作会等概率地从[1, n] 的所有n(n+1) 2 个子区间中随机选择一个。对于所有在该次操作中 被访问到的非叶子节点,Bob 会将这个点上的标记下推;而对于所有叶子节点(即没有继续递 归的节点),Bob 会给这个点打上标记。 Bob 想知道,k 次操作之后,有标记的节点的期望数量是多少。 2.2 具体定义 线段树:线段树是一棵每个节点上都记录了一个线段的二叉树。根节点记录的线段是[1, n]。 对于每个节点,若它记录的线段是[l, r] 且l̸ = r,取m = ⌊l+r 2 ⌋,则它的左右儿子节点记录的 线段分别是[l, m] 和[m + 1, r];若l = r,则它是叶子节点。 广义线段树:在广义的线段树中,m 不要求恰好等于区间的中点,但是m 还是必须满足 l ≤m < r 的。不难发现在广义的线段树中,树的深度可以达到O(n) 级别。 线段树的核心是懒标记,下面是一个带懒标记的广义线段树的伪代码,其中tag 数组为懒 标记: 1: function Pushdown(Node) 2: if tag[Node]= 1 then 3: tag[Lson(Node)]←1 4: tag[Rson(Node)]←1 5: tag[Node]←0 6: end if 7: end function 8: 9: function Modify(Node, l, r, ql, qr) 10: if [l, r] ∩[ql, qr] = ∅then 11: return 12: end if 13: if [l, r] ⊆[ql, qr] then 14: tag[Node] ←1 15: return 16: end if 17: m ←GetM(Node) 18: Pushdown(Node) 19: Modify(Lson(Node),l, m, ql, qr) 20: Modify(Rson(Node),m + 1, r, ql, qr) 21: end function 注意,在处理叶子节点时,一旦他获得了一个标记,那么这个标记会一直存在。 4

你也可以这么理解题意:有一棵广义线段树,每个节点有一个m 值。一开始tag 数组均为 0,Bob 会执行k 次操作,每次操作等概率随机选择区间[l, r] 并执行MODIFY(root,1,n,l,r);。 最后所有Node 中满足tag[Node]=1 的期望数量就是需要求的值。 2.3 输入格式 第一行输入两个整数n, k。 接下来输入一行包含n −1 个整数ai:按照中序遍历的顺序,给出广义线段树上所有非叶 子节点的划分位置m。你也可以理解为从只有[1, n] 根节点开始,每次读入一个整数后,就将 当前包含这个整数的节点做一次拆分,最后获得一棵有2n −1 个节点的广义线段树。 保证给定的n −1 个整数是一个排列,不难发现通过这些信息就能唯一确定一棵[1, n] 上 的广义线段树。 2.4 输出格式 输出一行一个整数,代表期望数量对p = 998244353 取模后的结果。即,如果期望数量的 最简分数表示为a b,你需要输出一个整数c 满足c × b ≡a (mod p) 2.5 样例输入1 3 1 1 2 2.6 样例输出1 166374060 2.7 样例解释1 输入的线段树为[1, 3], [1, 1], [2, 3], [2, 2], [3, 3]。 若操作为[1, 1]/[2, 2]/[3, 3]/[2, 3]/[1, 3],标记个数为1。若操作为[1, 2],标记个数为2。故 答案为7 6 2.8 样例输入2 5 4 2 1 3 4 5

2.9 样例输出2 320443836 2.10 样例输入输出3 见下发文件。 2.11 数据范围与约定 测试点 n k 其他约定 1 ≤10 ≤4 无 2 ≤10 ≤100 3 ≤5 无 4 无 =1 5 = 32 无 输入的线段树为完全二叉树 6 = 64 7 = 4096 8 ≤5000 每个m 均在[l, r −1] 内均匀随机 9 ≤100000 无 10 无 对于100% 的数据,1 ≤n ≤200000, 1 ≤k ≤109。 6