分析
权值线段树。
给每个节点赋一个值 $val$ 和 $a_i=val$ 的 $b_i$ 之和。
修改 $a_x$ 的时候先将 $a_x$ 的出现次数在树上剪掉 $b_x$,再在 $y$ 上面加上;修改 $b_x$ 的时候直接加上变化量 $y-b_x$。
由于我们是要取前 $x$ 大的 $a_i$ 之和,在询问的时候有限考虑右儿子,然后在是当前节点和左儿子。$\sum b_i \le x-1$ 的情况就是整棵树的第二个值的和不足 $x$。如果离散化,注意一下 $a_i$ 的值即可。
复杂度 $O((n+q)\log(n+q))$。
代码
Link.
标签:abc287,val,题解,Update,Query,Balance From: https://www.cnblogs.com/harmisyz/p/18054678