T2:
单独考虑每个点的贡献是一种期望技巧。
相关性。单点贡献与其他点无关。
思路：先把问题拆分，化成a[1]+sigma:f[i].
既然能把问题拆分，考虑能否把贡献拆分，单独算。
只考虑一部分贡献，拿去无关的。
则式子只与a[i]及a[1]有关。
注意：假设a[i],a[1]都未取净，概率是1/2.
若取净概率无法算。
解决：1-其他情况的概率（已算出）
技巧：求概率用1减去已知得到未知。
考场柿子问题：
想把除a[1]外数压到一起，转化成多维，从（0,0,0走到（a[1],[2],[3])方案数
但每个方案概率不同。
选a[1]与选其他的概率不是1:1，是1:cnt.所以不能简单乘1/2。
想到期望单点算贡献而非dp:
Dp无法描述。数据范围大。
当然暴力部分分可以DP。优于搜索。
细节：i=0也有概率。
组合数处理到1e6. 是5e5+5e5
T3：
变量名uv和xy用混，暴力写挂30分。
大神题，暂未改出来。
T1：调试2h。注意：单调栈1、斜率递增，2、交点递减。
原文：https://www.cnblogs.com/seamtn/p/11855916.html