<div class="blogpost-body" id="cnblogs_post_body">
<h1><a id="_0"></a>题目链接</h1>
<p><a href="https://www.lydsy.com/JudgeOnline/problem.php?id=5461">https://www.lydsy.com/JudgeOnline/problem.php?id=5461</a></p>
<h1><a id="_4"></a>题解</h1>
<p>线段树合并，线段树每个区间<span class="katex--inline"><span class="katex"><span class="katex-mathml">[l,r][l,r]</span><span class="katex-html"><span class="base"><span class="strut" style="vertical-align:-.25em;"></span><span class="mopen">[</span><span class="mord mathit">l</span><span class="mpunct">,</span><span class="mspace"></span><span class="mord mathit">r</span><span class="mclose">]</span></span></span></span></span>代表取到第<span class="katex--inline"><span class="katex"><span class="katex-mathml">ll</span><span class="katex-html"><span class="base"><span class="strut" style="vertical-align:0em;"></span><span class="mord mathit">l</span></span></span></span></span>小到第<span class="katex--inline"><span class="katex"><span class="katex-mathml">rr</span><span class="katex-html"><span class="base"><span class="strut" style="vertical-align:0em;"></span><span class="mord mathit">r</span></span></span></span></span>小的权值的概率，对于每一个节点，线段树由两个端点合并，容易发现在点<span class="katex--inline"><span class="katex"><span class="katex-mathml">uu</span><span class="katex-html"><span class="base"><span class="strut" style="vertical-align:0em;"></span><span class="mord mathit">u</span></span></span></span></span>，对于第<span class="katex--inline"><span class="katex"><span class="katex-mathml">ii</span><span class="katex-html"><span class="base"><span class="strut" style="vertical-align:0em;"></span><span class="mord mathit">i</span></span></span></span></span>小的权值，假设这个权值是由左儿子贡献而来，取到这个权值的概率是<br><span class="katex--display"><span class="katex-display"><span class="katex"><span class="katex-mathml">fu,i=fls,i(∑j&lt;ipifrs,j+∑j&gt;i(1pi)frs,j) f_{u,i}=f_{ls,i}(\sum_{j&lt;i}p_if_{rs,j}+\sum_{j&gt;i}(1-p_i)f_{rs,j}) </span><span class="katex-html"><span class="base"><span class="strut" style="vertical-align:-.286108em;"></span><span class="mord"><span class="mord mathit">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span style="margin-left:-.10764em;"><span class="pstrut"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathit mtight">u</span><span class="mpunct mtight">,</span><span class="mord mathit mtight">i</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist"></span></span></span></span></span><span class="mspace"></span><span class="mrel">=</span><span class="mspace"></span></span><span class="base"><span class="strut" style="vertical-align:-1.41378em;"></span><span class="mord"><span class="mord mathit">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span style="margin-left:-.10764em;"><span class="pstrut"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathit mtight">l</span><span class="mord mathit mtight">s</span><span class="mpunct mtight">,</span><span class="mord mathit mtight">i</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist"></span></span></span></span></span><span class="mopen">(</span><span class="mop op-limits"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span style="margin-left:0em;"><span class="pstrut"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathit mtight">j</span><span class="mrel mtight"><</span><span class="mord mathit mtight">i</span></span></span></span><span class="pstrut"></span><span class="mop op-symbol large-op">∑</span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist"></span></span></span></span><span class="mspace"></span><span class="mord"><span class="mord mathit">p</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span style="margin-left:0em;"><span class="pstrut"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mathit mtight">i</span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist"></span></span></span></span></span><span class="mord"><span class="mord mathit">f</span><span class="msupsub"><span class="vlist-t vlist-t2"><span class="vlist-r"><span class="vlist"><span style="margin-left:-.10764em;"><span class="pstrut"></span><span class="sizing reset-size6 size3 mtight"><span class="mord mtight"><span class="mord mathit mtight">r</span><span class="mord mathit mtight">s</span><span class="mpunct mtight">,</span><span class="mord mathit mtight">j</span></span></span></span></span><span class="vlist-s"></span></span><span class="vlist-r"><span class="vlist"></span></span></span></span></span><span class="mspace"></span><span class="mbin">+</span><span class="mspace"></span></span><span class="base"><span class="strut" style="vertical-align:-1.41378em;"></span><sp |
|
转播
