题解：P10365 [PA 2024] Kraniki

· · 题解

考虑计数一个位置在什么情况下会开闸。

我们发现，如果有 cnt_i 个位置开闸可以流到 i，则 i 开闸的要求就是 i 在这 cnt_i 个数里排第一个。

所以每个 i 会有 \frac{1}{cnt_i} 的概率开闸。

根据期望的线性性，\sum \frac{1}{cnt_i} 就是答案。因此，对每个 i 求出 cnt_i 即可。

这个图是个天生的 DAG，我们高层往底层连边，连边代表可以流水。具体的，最上面一个覆盖了左端点的，最上面一个覆盖了右端点的，还有投影完全在这个线段内的，他们流水都会流到这根线段。

我们其实只关心覆盖左端点的线段 L_i 和覆盖右端点的 R_i，相当于统计两端折线内的面积，我们求出一条折线的左侧部分面积，右边折线减左边折线就好了。

接下来问题就是，如果一条线段 j 足够长，覆盖了所有可以流水到线段 i 的，那么折线应该到这里就停了。我们称线段 j 支配了线段 i。

考虑求出这个支配的 j，事实上，他相当于既支配了 L_i 也支配了 R_i 的最低的那条线段。也就是支配树上 L_i 和 R_i 的 LCA。

所以就是个动态加叶子求 LCA，直接倍增即可。

求出具体的 L_i,R_i 也是简单的，从高到低线段树维护区间赋值和单点求值即可。

对于折线范围内的“面积”（其实是范围内有多少线段）统计，本质是一个二维数点，扫描线一下配合树状数组也可以轻松解决。

然后把每一段的面积拼起来，同样可以倍增求解。

至此本题就可以 \mathcal O(n\log n) 时间 \mathcal O(n\log n) 空间做完了。

使用斜二倍增可以 \mathcal O(n\log n) 时间 \mathcal O(n) 空间。实测使用斜二倍增的代码快了一倍。