algorithm - 下降段以概率与其他段重聚，确定该段的预期中等长度

Question

这是一个非常棘手的问题，只是一个提示。

---

我们有N段，编号从 1至 N并由它们的左右点定义，{Left[i],Right[i]} .

i -th 段位于高度 N-i .第一段(最高的一段)开始下降，而其他段保持不变。如果在秋季期间有一段 i与另一段相交 j至少有一点，那么两人重逢的概率是P[j]/Q[j] ，得到的线段会一直下降。来自两个片段的重聚，{A,B}和 {C,D} , 获得的段将是 {min(A,C),max(B,D)} .

您需要确定第一个片段的预期中等长度(即在它达到小于任何其他片段高度的高度之后)。如果这个答案是有理数U/V , 你被要求确定 X这样 X*V=U (mod 10^9+7)

---

限制:

• 0 < P < Q < 1 000
• 0 < Left < Right < 1 000 000
• N ≤ 100 000
• time : 2.5 sec
• memory : 32768 kbytes

`

---

输入包含N在第一行，然后在下面 N行有 4 个整数:Left, Right, P, Q,代表i第-段[Left, Right]概率P/Q与坠落的片段重逢。示例:

input:
5
35 64 58 873
41 70 407 729
18 90 165 628
10 57 33 104
60 69 152 466

output:
779316733

答案大约是 49.813963。

---

Answer 1

想法1

最终段的长度为 R-L，其中 R 是右端的位置，L 是左端的位置。

期望是线性运算所以

E(长度) = E(R) - E(L)

我们可以分别计算 E(R) 和 E(L)，然后合并结果。

想法2

我们可以迭代计算左端位置的 PDF。

它从第一段 (Left[1]) 的左端开始，概率为 1。

当它落在第 i 段时，如果左端在 Left[i] 和 Right[i] 之间，将会发生有趣的碰撞。我们将有趣的碰撞定义为影响左端位置的碰撞。

这里的重点是，如果我们需要知道右端的当前位置来判断是否发生碰撞，那么就不是有趣的碰撞了!这是因为如果我们需要知道右端，那么线段i必须完全在起点的右边，因此它不会影响左边缘的位置。

因此，为了更新 PDF，我们收集了 Left[i] 和 Right[i] 之间的所有概率质量，乘以碰撞概率，并将结果添加到 Left[i]。 (这些位置的现有质量按碰撞概率按比例缩小。)

想法3

目前我们有一个 O(n^2) 算法，由 O(n) 的 n 次迭代组成，用于计算和修改每个范围内的质量。

但是，我们可以使用数据结构，例如 segment tree允许我们在 O(logn) 时间内执行每次迭代，总时间复杂度为 O(nlogn)。