123
G
首先考虑一个序列的价值怎么求，注意到 \(A_1\) 是必须选的（必须为左括号），从 \(A_2\) 开始，我们两个两个考虑数字，先假设其全为右括号，然后将目前所有的右括号中选择价值最大的一个，变为左括号。这样操作得到的序列必然合法且价值最大。
考虑如何求期望，做一个差分，令 \(f(x)\) 表示将所有 \(\leq x\) 的数看成 \(0\)，所有 \(>x\) 的数看成 \(1\) 的期望，那么最终的期望就是 \(\int_0^\infty f(x)dx\)。
现在只需要考虑如何计算 \(f\)。考虑所有 \(L_i\) 和 \(R_i\) 将实数轴分成若干段，我们独立计算每一段中 \(f(x)\) 的形式。在每一段中，\(f(x)\) 都是一个多项式。 不妨令 \(dp_{i,j}\) 表示考虑前 \(i\) 个数 (\(i\) 为奇数)，此时优先队列中还剩 \(j\) 个 \(1\) 的概率多项式。转移枚举当前的数字是 \(0\) 还是 \(1\)，并且乘以对应的概率。
最终计算答案的时候进行一个容斥，计算 \(n-\# 0\) 即可，其中 \(\#0\) 的计算由 \(dp_{i,0}\) 乘上后面两个数都为 \(0\) 的概率取得。