CF1461C Random Events

Ron 拥有一个长度为 $n$ 的排列 $a$。 长度为 $n$ 的排列是一个包含 $1$ 到 $n$ 的 $n$ 个互不相同整数的数组，顺序任意。例如，$[2,3,1,5,4]$ 是一个排列，但 $[1,2,2]$ 不是排列（$2$ 在数组中出现了两次），$[1,3,4]$ 也不是排列（$n=3$，但数组中有 $4$）。  Ron 的排列要进行 $m$ 次如下类型的实验：$(r_i, p_i)$。这意味着区间 $[1, r_i]$（即长度为 $r_i$ 的前缀）会以概率 $p_i$ 被升序排序。所有实验按输入顺序依次进行。 例如，考虑排列 $[4, 2, 1, 5, 3]$ 和实验 $(3, 0.6)$。经过该实验后，有 $60\%$ 的概率排列变为 $[1, 2, 4, 5, 3]$，有 $40\%$ 的概率排列保持不变。 你需要计算经过 $m$ 次实验后，排列最终完全升序排列的概率。

每组测试数据包含一个或多个测试用例。第一行包含测试用例数 $t$（$1 \le t \le 100$）。 每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 10^5$），分别表示排列的长度和实验次数。 每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示排列的内容。 接下来 $m$ 行，每行包含一个整数 $r_i$ 和一个实数 $p_i$（$1 \le r_i \le n, 0 \le p_i \le 1$），分别表示前缀长度和该前缀被排序的概率。所有概率最多保留 $6$ 位小数。 保证所有测试用例中 $n$ 的总和与 $m$ 的总和不超过 $10^5$（$\sum n, \sum m \le 10^5$）。

对于每个测试用例，输出一个实数，表示经过所有实验后排列最终完全升序排列的概率。你的答案将被认为是正确的，如果其绝对误差或相对误差不超过 $10^{-6}$。 形式化地，设你的答案为 $a$，标准答案为 $b$。当且仅当 $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$ 时，你的答案才会被接受。

第一个测试用例的解释：可以证明，最终排列是否有序只取决于在 $(4, 0.6)$ 这个实验中是否进行了排序。 由 ChatGPT 4.1 翻译