先考虑如何处理单个询问，看到了最大值最小，不难想到二分
但是为了整体二分的方便，这个check函数必须这么写：先将果汁以美味度排序，然后以价格为下标建立树状数组，将美味度不低于\(mid\)的果汁扔进树状数组里面（注意有两个树状数组，一个用来几率体积，另一个用来记录体积乘以价格），然后再二分价格，用第一个树状数组找到能买到当前所需要的体积的果汁的最小价格（i.e，如果买的果汁的价格低于这个价格，那么就算把低于这个价格的果汁全买了，得到的体积也比所需要的体积小，而把不超过这个价格的所有果汁都买了就能得到不低于所需要体积的果汁），然后再利用另一个树状数组判断买下这些果汁是否超过已有钱数
整体二分的话，这里就不能像之前那样子将果汁分成两部分了，因为每次check都需要用到整个果汁序列的，只能将小朋友分成两个部分；然而为了减少时间复杂度，我们假设在刚进入函数solve(int lval,int rval,int st,int ed)（表示对于属于\(st\) ~ \(ed\)的小朋友，他们的答案在\(lval\)和\(rval\)之间）时，树状数组存储了大于\(rval\)的果汁信息，于是我们就要先将\([mid+1,rval]\)的果汁信息扔进树状数组里面，而且在进入solve(mid+1,rval,st+lt,ed)之前要还原树状数组（注意进入solve(lval,mid,st,st+lt-1)不用还原）
具体可以见代码
这道题目就告诉我们不一定非要将序列分成两部分，有可能是会用到整个序列的，这个时候在必要时还原就好了
标签：树状,int,rval,混合,CTSC2018,数组,果汁,st From： https://www.cnblogs.com/dingxingdi/p/18301876