题意：Q组样例。每组给出n、m，接下来一行n个数a[i]。对于每个 $_math_inline$i\in[1, n]$math_inline_$ ，输出需要删除最少的个数，使得 $_math_inline$\sum_{j=1}^{i-1}a[i]\leq m$math_inline_$
对于每个i，删除最少个数 = i-1-留下的最多的个数。我们建一个权值线段树，因为 $_math_inline$q\leq w[i] \leq 10^9 且 1 \leq n \leq 2 \times 10^5$math_inline_$ ，所以需要离散化。
我们能留下的数的和最大为m-a[i]。那么题目转化为用最多的权值线段树中的数凑出m-a[i]这个数。
那么我们凑的时候，如果左子树上的数的和已经够用，那么肯定只用左子树上的数；否则我们肯定要全用左子树上的数+右子树凑出 m-a[i]-左子树上数的和。
注意当递归到叶节点时，那么表明我们只能用这个数去凑val，取 $_math_inline$\text{min}\left(\text{tree[cur].num}, \frac{\text{val}}{\text{b[tree[cur].l]}}\right)$math_inline_$ 即可。查询完再更新个数即可
Code
1cout << "Hello World" << endl;
除另有声明外，本博客文章均采用 知识共享 (Creative Commons) 署名 4.0 国际许可协议 进行许可。转载请注明原作者与文章出处。