「Luogu-P3924」康娜的线段树
读完题目以后，首先一种简单的想法就是建一颗线段树然后模拟，每个节点维护它所管理的区间内所有数的和以及他自身被访问的概率，以及它和它的子树内所有节点的前两个属性的乘积之和。然后你再一看数据范围：
对于 $70\%$ 的数据，保证 $1\leqslant n,m\leqslant 10^{5}$。
对于 $100\%$ 的数据，保证 $1\leqslant n,m\leqslant 10^{6}$。
也就是说，上述做法最多只能拿 $70$ 分。为什么说「最多」呢？因为这道题在中间运算过程中需要使用浮点数，而浮点数是自带大常数的，如果你的程序写得再丑一点常数再大一点，说不定 $70$ 分都拿不到了。
Updated on 2018-10-09
不好意思时间复杂度算错了我太菜了。
但反正线段树需要卡常才能过（
我们来想办法优化。考虑到，对于线段树的每一个非叶子节点，它所维护的区间和也只是原序列中某一段数字的和，如果我们能把这些节点被访问的概率下推到它的每一个叶子节点，也许就能达到优化的目的。
定义 $E_i$ 为叶子节点 $[i,i]$ 对答案的贡献，$c_i$ 为其所有祖先节点被访问的概率之和，不难发现 $c_ia_i=E_i$。我们只要预处理出 $c_i$，计算出 $\prod_{i=1}^{n}c_ia_i$，然后处理出 $c_i$ 的前缀和，每次操作直接查询操作区间内 $c_i$ 的和，再乘以他给的那个数，累加到答案上就可以了。
稍加分析，我们不难得出如下结论。设根节点深度为 $0$，则任意一个节点，就比如说 $x$，被访问的概率为 $2^{-dep[x]}$，其中 $dep[x]$ 表示 $x$ 的深度。而对于 $x$ 子树内的每一个叶子节点 $[i,i]$，我们执行一次 $c_i+=2^{-dep[x]}$ 即可。我们可以用一次类似于树形 DP 的 DFS 来完成这一过程。需要注意的是，我们肯定不能暴力枚举所有叶子节点，在 DFS 时，我们实际上修改的是 $c$ 数组的差分数组，DFS 结束后再还原出 $c$ 数组即可。
以及，最后一句话。
这道题卡精度。