距离出发去秦皇岛还有1天的时间，突然昨天的一场考试暴露了很多问题，
例如T1二分条件写反挂掉80pts，T2数组开小挂了20pts，这么弱智的问题真的不应该出现，
何况现在距离CSP仅剩2天，考场上一定要认真检查低错，检查数组大小和内存限制，不要仅仅相信对拍
标签：
单调栈维护凸包
题解：
首先发现这个其实是一个假的二次函数，因为它没有常数项，所以可以提出一个x，维护两个凸包，在凸包上二分即可
也可以把询问离线做到O(n)
标签：
期望
题解：
首先考虑把贡献分开统计，即:
$ ans=a[1]+\sum\limits_{i=2}^{n}f[i] $
其中f[i]表示在a[1]取完之后i取走的期望个数
现在的问题在于求f[i]，可以枚举a[i]的个数为j
但是我们发现假如a[i]在j-1之前已经选完，概率会发生改变，
所以需要分类讨论:
1>a[1]先选完:
$ val=\sum_{j=0}^{a[i]-1}\frac{C(j+a[1]-1,j)}{2^{(a[1]+j)}} $
2>a[i]先选完:
$ val=a[i]*(1-\sum_{j=0}^{a[i]-1}\frac{C(a[1]+k-1,k)}{2^{(a[1]+k)}}) $
这里的概率无法直接得出，所以需要用1减去i选了小于a[i]个的概率
(对于n<=2可以Dp得出概率，只要不开小数组便可以得到20pts)
标签:
倍增
题解：
坐等charm神AC写题解
原文：https://www.cnblogs.com/AthosD/p/11855841.html