制高 题解

思路

设结点 $i$ 在均匀随机选择所有父亲时成为制高点的概率为 $p_i$。根结点必为制高点，所以 $p_1=1$。

对于 $i\ge2$，父亲在 $[l_i,r_i]$ 中等概率选择。只有父亲本身是制高点且高度不超过 $h_i$ 时，结点 $i$ 才是制高点，因此

$$p_i=\frac{1}{r_i-l_i+1}\sum_{j=l_i}^{r_i}[h_j\le h_i]p_j.$$

所有分母都小于模数，可以在模 $998244353$ 意义下使用逆元。设方案总数为

$$D=\prod_{i=2}^n(r_i-l_i+1),$$

则线性期望给出答案 $D\sum_i p_i$。

做法

把结点按 $(h_i,i)$ 从小到大排序，并用树状数组维护已经算出的 $p_i$，下标为结点编号。

处理结点 $i$ 时，树状数组中已经包含所有高度小于 $h_i$ 的结点，以及高度等于 $h_i$ 且编号更小的结点。查询区间 $[l_i,r_i]$ 时，区间中的编号本来就都小于 $i$，所以查询结果恰好是递推式中的和。算出 $p_i$ 后，再在位置 $i$ 加入它。

另一种满分实现可以按编号顺序建立以高度为下标的可持久化线段树。用版本 $r_i$ 减版本 $l_i-1$，即可查询编号区间内高度不超过 $h_i$ 的概率和。

子任务算法

• $n\le10$ 时枚举所有父亲组合并直接统计。
• 当父亲选择数乘积不超过 $10^6$ 时，区间长度大于一的结点很少；所有这些区间长度之和不超过其乘积，可以直接扫描递推式。
• 高度单调不降时，任意父子边都满足高度条件，所有结点都是制高点，答案为 $nD$。
• 高度严格下降时，除根外没有制高点，答案为 $D$。
• $n\le10^3$ 时直接扫描每个父亲区间，时间复杂度为 $O(n^2)$。

正确性证明

对任意非根结点 $i$，它成为制高点的事件可以按父亲选择划分。父亲为 $j$ 的概率为 $1/(r_i-l_i+1)$；在此前提下，结点 $i$ 成为制高点当且仅当 $j$ 是制高点且 $h_j\le h_i$。对所有可能父亲求和，得到上述 $p_i$ 递推式。

按 $(h_i,i)$ 排序处理时，递推式中每个满足 $j<i$ 且 $h_j\le h_i$ 的结点都已经加入树状数组；任何已经加入但编号不在 $[l_i,r_i]$ 中的结点又会被区间查询排除。因此算法求得的区间和与递推式完全一致，所有 $p_i$ 均正确。

每棵可能的树出现概率相同。由期望的线性性，单棵树制高点数量的期望为 $\sum_i p_i$；乘以方案总数 $D$，就得到所有树中制高点数量的总和。故最终答案正确。

复杂度分析

排序和树状数组操作的总时间复杂度为 $O(n\log n)$，空间复杂度为 $O(n)$。