2020-2021:teams:looking_up_at_the_starry_sky:推荐 [CVBB ACM Team]

2020-2021:teams:looking_up_at_the_starry_sky:推荐

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。

====== 2020牛客暑期多校训练营（第九场）Groundhog and Gaming Time ======

题意，n个区间，每个区间有$\frac{1}{2}$的概率被选，每一种方案的值为交集长度的平方 ，求这个值的期望。

分类：数据结构，数学

题解：转化为算所有情况的和，然后 / $2^n$。交集里面的每两个点都会对答案产生1的贡献。答案等价于枚举两个点，假设有k个区间覆盖了这两个点，那么这两个点对答案的贡献是 $2^k-1$。考虑枚举一个点i，然后维护另一个点j在所有位置的取值，在线段树上进行这个操作。把与i相交的区间加入进来，更新所有j处的取值。$2^{k+1}-1 = (2^{k}-1)*2+1$ ，所以用支持区间乘和区间加的线段树维护一下。$O(nlogn)$

comment：转化比较妙

2020-2021/teams/looking_up_at_the_starry_sky/推荐.txt · 最后更改: 2020/08/14 18:11 由 zzy