Helping People

题意翻译

有一个长为 $n$ 的数列，初始时为 $a_{1..n}$。 给你 $q$ 个操作，第 $i$ 个操作将 $[l_i,r_i]$ 内的数全部加一，有 $p_i$ 的概率被执行。保证区间不会交错，即：$\forall i,j\in[1,q],l_i\le r_i<l_j\le r_j$ 或 $l_i\le l_j\le r_j\le r_i$ 或 $l_j\le r_j<l_i\le r_i$ 或 $l_j\le l_i\le r_i\le r_j$ 。 求操作完成后数列的最大值的期望。 ### 输入格式 第一行 $n,\,q\,(1\le n\le10^5,\,1\le q\le 5000)$。 第二行 $a_1,\,a_2,\,\cdots,\,a_n\,(0\le a_i\le10^9)$。 接下来 $q$ 行，每行 $l_i,\,r_i,\,p_i\,(1\le l_i\le r_i\le n,\,0\le p_i\le1)$。 ### 输出格式 一个实数，表示答案，绝对/相对误差在 $10^{-6}$ 内算对。 Translated by ouuan.

题目描述

Malek is a rich man. He also is very generous. That's why he decided to split his money between poor people. A charity institute knows $ n $ poor people numbered from $ 1 $ to $ n $ . The institute gave Malek $ q $ recommendations. A recommendation is a segment of people like $ \[l,r\] $ which means the institute recommended that Malek gives one dollar to every person whose number is in this segment. However this charity has very odd rules about the recommendations. Because of those rules the recommendations are given in such a way that for every two recommendation $ \[a,b\] $ and $ \[c,d\] $ one of the following conditions holds: - The two segments are completely disjoint. More formally either $ a<=b<c<=d $ or $ c<=d<a<=b $ - One of the two segments are inside another. More formally either $ a<=c<=d<=b $ or $ c<=a<=b<=d $ . The goodness of a charity is the value of maximum money a person has after Malek finishes giving his money. The institute knows for each recommendation what is the probability that Malek will accept it. They want to know the expected value of goodness of this charity. So they asked you for help. You have been given the list of recommendations and for each recommendation the probability of it being accepted by Malek. You have also been given how much money each person initially has. You must find the expected value of goodness.

输入输出格式

输入格式

Malek is a rich man. He also is very generous. That's why he decided to split his money between poor people. A charity institute knows $ n $ poor people numbered from $ 1 $ to $ n $ . The institute gave Malek $ q $ recommendations. A recommendation is a segment of people like $ \[l,r\] $ which means the institute recommended that Malek gives one dollar to every person whose number is in this segment. However this charity has very odd rules about the recommendations. Because of those rules the recommendations are given in such a way that for every two recommendation $ \[a,b\] $ and $ \[c,d\] $ one of the following conditions holds: - The two segments are completely disjoint. More formally either $ a<=b<c<=d $ or $ c<=d<a<=b $ - One of the two segments are inside another. More formally either $ a<=c<=d<=b $ or $ c<=a<=b<=d $ . The goodness of a charity is the value of maximum money a person has after Malek finishes giving his money. The institute knows for each recommendation what is the probability that Malek will accept it. They want to know the expected value of goodness of this charity. So they asked you for help. You have been given the list of recommendations and for each recommendation the probability of it being accepted by Malek. You have also been given how much money each person initially has. You must find the expected value of goodness.

输出格式

Output the sought value. Your answer will be considered correct if its absolute or relative error is less than $ 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