题意
一面墙上有 \(n\) 个平台，每个平台是一条连接 \((h_i, l_i)\) 与 \((h_i, r_i)\) 的线段。
其中 \(l_i, r_i\) 组成一个 \([1, 2n]\) 的排列。
你需要按照某种顺序淹没这些平台，每淹没一个平台，水会顺着线段的两个端点垂直下落。
假设每次淹没的水是无限的，若当前的平台没有水，则在当前平台上倒水。
求所有淹没方案的倒水次数的期望。
\(n \le 5 \times 10 ^ 5\)
Sol
很显然，对于每个平台能到的下一个平台建图。
得到一个 DAG。
平凡地，考虑期望转概率。
注意到一个平台 \(x\) 有贡献当且仅当在排列 \(p\)，\(|p| = n\) 中，所有能够到达 \(x\) 的平台都排在 \(x\) 的后面。
集中注意力，设能到达 \(x\) 的平台有 \(k\) 个，如果我们单独将这 \(k\) 个数字拿出来排列。
不难发现可以合法的方案数显然为 \((k - 1)!\)。
考虑原问题，不难发现方案数显然为 \(\frac{n!}{k}\)。
乘上期望后就没有上面那个 \(n!\) 了，所以问题转化为：求一个 DAG 上每个点能被多少个点到达的逆元之和。
注意到这个问题显然是不可做的，最优的做法是使用 bitset 传递闭包。
可以获得 \(n \le 10 ^ 5\) 的分数。
简单手摸一下可以得到这张图。
注意到中间被左右两个端点覆盖的区间一定都产生贡献。
每一次向上跳都会扩大区间，注意到若当前区间若被 \(w\) 覆盖，会导致上面所有的区间都无法到达 \(u\)。
考虑区间 \(v\)，能到达 \(u\) 的区间的右端点最大的区间。
注意到 \(w\) 必定满足为 \(u\) 的下一次跳跃的区间。
对于 \(u\)，考虑刚才 bitset 传递闭包的做法，可以直接求得。
接下来的事情就很简单了。
如何求得阴影部分的贡献？
使用右边界以左的区间数减去左边界以左的区间数即可。
考虑倍增维护每一次跳跃左边产生贡献的区间数，离线下来跑一边树状数组即可。
时间复杂度：\(O(n \log n)\)
标签：倒水,省选,到达,平台,T2,water,淹没,端点,区间 From： https://www.cnblogs.com/cxqghzj/p/18098673