题解 P3924 【康娜的线段树】

2018-08-22 17:23:18


看到样例的第一个操作的解释:

img

(橙色表示改该层每一个节点被进入的概率。可以发现与深度有关)

(画的丑不要在意)

可以发现,叶节点增加相当于把整个从根节点到叶节点的路径全部增加。

那么对每个叶节点维护一下根节点到叶节点的深度(黄字)的和,再求一遍前缀和,记为 $s[]$ 。

现在看蓝字,发现将1~3全部加4,等于把那一片蓝色全部增加。

一般的,对于每一个修改操作 $(x,y,z)$ ,和增加了 $(s[y]-s[x-1])\times z$ 。

那么再求出期望即可。

注意开long long,还要约分。

细节见代码。代码见蒟蒻的blog