CF138C Mushroom Gnomes - 2

有一天，Natalia 在森林中散步时遇到了一只小蘑菇侏儒。侏儒给她讲了这样一个故事： 众所周知，蘑菇侏儒的力量来源于生长在他们家乡森林中的魔法蘑菇。森林里有 $n$ 棵树和 $m$ 个魔法蘑菇：第 $i$ 棵树生长在一条直线上的坐标 $a_{i}$ 处，高度为 $h_{i}$，第 $j$ 个蘑菇生长在坐标 $b_{j}$ 处，拥有魔法力量 $z_{j}$。 但有一天，蘑菇侏儒的死敌——野生蘑菇吞噬者，在他们的家乡森林中掀起了一场可怕的风暴。结果，一些树开始倒下并压碎了魔法蘑菇。蘑菇侏儒的至高神谕者提前计算出了每棵树向左倒、向右倒或保持不倒的概率。如果一棵坐标为 $x$、高度为 $h$ 的树向左倒下，那么属于右开区间 $[x-h, x)$ 的所有蘑菇都会被摧毁；如果树向右倒下，则属于左开区间 $(x, x+h]$ 的蘑菇会被摧毁。只有那些没有被任何一棵树砸中的蘑菇才能幸存。 已知所有树倒下的方向彼此独立（即所有事件相互独立，且树的倒下不会影响其他树的倒下方向），至高神谕者还能迅速计算出风暴过后幸存蘑菇的总魔法力量的期望值。正是这些计算最终拯救了蘑菇侏儒们免于灭顶之灾。 Natalia 作为一名优秀的奥赛程序员，对这个故事产生了兴趣，她决定想出一种快速计算幸存蘑菇力量总和期望值的方法。

第一行包含两个整数 $n$ 和 $m$（$1 \leq n \leq 10^{5}$，$1 \leq m \leq 10^{4}$），分别表示树和蘑菇的数量。 接下来的 $n$ 行，每行包含四个整数 $a_{i}$、$h_{i}$、$l_{i}$、$r_{i}$（$|a_{i}| \leq 10^{9}$，$1 \leq h_{i} \leq 10^{9}$，$0 \leq l_{i}, r_{i}, l_{i} + r_{i} \leq 100$），分别表示第 $i$ 棵树的坐标、高度、向左倒和向右倒的概率百分比（剩余的概率为该树保持不倒）。 接下来的 $m$ 行，每行包含两个整数 $b_{j}$、$z_{j}$（$|b_{j}| \leq 10^{9}$，$1 \leq z_{j} \leq 10^{3}$），分别表示第 $j$ 个蘑菇的坐标和魔法力量。 同一个点上可以有任意数量的树和蘑菇。

输出一个实数，表示幸存蘑菇的总魔法力量的期望值。结果允许相对或绝对误差为 $10^{-4}$。

认为坐标为 $x$ 的蘑菇属于右开区间 $[l, r)$ 当且仅当 $l \leq x < r$。同理，坐标为 $x$ 的蘑菇属于左开区间 $(l, r]$ 当且仅当 $l < x \leq r$。 在第一个测试中，蘑菇以 $50\%$ 的概率幸存，具体取决于唯一一棵树倒向哪一侧。 在第二个测试中，蘑菇只有在两棵树都没有砸中它时才能幸存。该概率为 $50\% \times 50\% = 25\%$。 预测试第12组是一个包含 $10^{5}$ 棵树和一个蘑菇的大数据测试。 由 ChatGPT 4.1 翻译