原文链接https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round5-F.html

题目传送门 - https://www.nowcoder.com/acm/contest/143/F

题意

　　有 n 个箱子，第 i 个箱子有 p[i] 的概率出现大小为 d[i] 的钻石。现在 小A 一开始手里有一个大小为 0 的钻石，他会根据 i 从小到大打开箱子，如果箱子里有钻石且比小 A 手中的大，那么小 A 就会交换手中的钻石和箱子里的钻石。

　　求期望的交换次数。

　　$1\leq n\leq 10^5$

题解

　　貌似有比我更简洁的做法。

　　先鸽一鸽。

代码

2018牛客网暑假ACM多校训练赛（第五场）F take 线段树,概率

原文：https://www.cnblogs.com/zhouzhendong/p/NowCoder-2018-Summer-Round5-F.html