← 返回题目列表

Codeforces · 494/C

C. 帮助别人

中文机器翻译题面 查看原题

马利克是个有钱人。他也非常慷慨。这就是为什么他决定把钱分给穷人。某慈善机构认识n名贫困人口,编号从1到n。该研究所给了 Malek q 推荐。推荐是像[l,r]这样的人群,这意味着研究所建议马利克给这个人群中的每个人一美元。

然而,这个慈善机构对推荐有非常奇怪的规则。由于这些规则,建议的给出方式是,对于每两个建议 [a, b] 和 [c, d],以下条件之一成立:

- 两个片段完全不相交。更正式地说,a ≤ b < c ≤ d 或 c ≤ d < a ≤ b
- 两个段之一位于另一个段内。更正式地说,a ≤ c ≤ d ≤ b或c ≤ a ≤ b ≤ d。

慈善机构的善意是一个人在马利克捐完钱后所拥有的最大金钱的价值。该研究所知道每项建议马利克接受的概率是多少。他们想知道这个慈善机构的善行的预期价值。所以他们向你寻求帮助。

您已获得推荐列表以及每项推荐被 Malek 接受的概率。您还知道每个人最初拥有多少钱。你必须找到善良的期望值。

输入

在第一行中给出了两个空格分隔的整数 n, q (1 ≤ n ≤ 105, 1 ≤ q ≤ 5000)。

在第二行中,给出了 n 个空格分隔的整数 a1, a2, ..., an (0 ≤ ai ≤ 109),这意味着编号 i 的人最初拥有 ai 美元。

接下来的 q 行包含三个空格分隔的数字 li、ri、pi (1 ≤ li ≤ ri ≤ n, 0 ≤ p ≤ 1),其中 li 和 ri 是描述推荐段的两个整数,pi 是一个实数,精确到小数点后三位,等于 Malek 接受该推荐的概率。

请注意,某个片段可能会在推荐中出现多次。

输出

输出所寻求的值。如果您的答案的绝对或相对误差小于 10 - 6,则视为正确。

示例

输入 #1

5 2
1 7 2 4 3
1 3 0.500
2 2 0.500

输出 #1

8.000000000

输入 #2

5 2
281 280 279 278 282
1 4 1.000
1 4 0.000

输出 #2

282.000000000

输入 #3

3 5
1 2 3
1 3 0.500
2 2 0.250
1 2 0.800
1 1 0.120
2 2 0.900

输出 #3

4.465000000