卧薪尝胆，厚积薄发。
水题
Date: Sun Mar 31 08:41:06 CST 2019
In Category:
Description：
给一棵树，每个点有点权，多次询问
$u,k$
表示在子树
$u$
中
$k$
次把一个数变成
$\big\lfloor\frac x2\big\rfloor$
，最小子树和。
$1\leqslant n\leqslant 10^5$
Solution：
每次操作会得到
$\big\lceil\frac x2\big\rceil$
的收益，不难发现这个收益是单调不降的，因此我们可以直接用主席树取前
$k$
大就行了。
也就是说如果收益递减，那么直接选前
$k$
大也能保证顺序。
Code：
没有代码
In tag:
数据结构-主席树
Timeline
About
Toolbox
Friends
Copyright © 2020
wjh15101051
ღゝ◡╹)ノ♡