这题很简单，普通的主席树上二分，除了思维有点难度就是版，紫题里也是下位哪来的黑 本贴将会讲解两种解法。 没错，主席树 前排提醒：这只是主席树的一种做法 步骤： 1.一眼二分法。比答案小的所有美味度都能符合要求，比答案大的美味度不能，符合单调性。 2.考虑进行一次询问。每次 check 应尽量取美味度大于 midmidmid 、单价最小的果汁，取完体积再判断价格是否符合标准。可以建立值域线段树，以单价为下标，维护区间体积和与区间花费和（将区间所有果汁买下的花费），在值域线段树上进行线段树二分，可用体积小于等于左子树则向左递归，大于则更新可用体积并向右递归，最后返回消费和。如何维护美味值大于等于 midmidmid 的约束条件？注意到每次只有美味值在区间 [mid,maxn][mid,maxn][mid,maxn] 的元素可用，形成一个后缀关系。将美味值从大到小排列，将后缀关系转化为前缀关系，只考虑前缀的所有元素，明显可用主席树维护。具体编码时先从大到小排序美味度，然后建立主席树，二分某种果汁之前的所有果汁是否可用（而不用对美味度值域建树），再按上述步骤二分。注意到每次 check 复杂度为 O(logN)O(logN)O(logN) ,一次二分答案为 O(log2N)O(log^2N)O(log2N).推广到多次询问，可以用整体二分直接在线对每一个询问回答即可。总复杂度 O(Nlog2N)O(Nlog^2N)O(Nlog2N)。 哪有人两步推出解法的 Code:Code:Code: 没错，整体二分 注意你谷有很多复杂度假的整体二分，也就是 O(Nlog3N)O(Nlog^3N)O(Nlog3N) 甚至 O(N2log2N)O(N^2log^2N)O(N2log2N),请以我学习的这种思路和代码为参考，或者自己证明自己做法的复杂度。 貌似可以一次二分中再二分符合要求的价格，但是这样就会是二分套二分套整体二分，复杂度为 O(Nlog3N)O(Nlog^3N)O(Nlog3N). 1.与上述一样。 2.用整体二分套值域线段树。利用值域线段树二分，判断询问分到哪组。区别是不像主席树开一瞬千树一堆线段树，而是一次性使用，用的时候插元素进去，用完清空。但是如果每次都从 midmidmid 的果汁插到 rrr 的果汁复杂度会假，因此每次都复用原来的权值线段树 ，往左就插入更多元素，往右就删掉一些元素。如何证明复杂度？ 注意到整体二分使用了递归，本质上是从值域的左到右执行操作，而不是同时进行，可以依此证明。 插入的用时分为从该轮递归跳到同一层递归和从该轮递归跳到更高层的递归。每层插入复杂度为左右层相加再加上左层最底部跳到右层最顶部的复杂度。计算得如下式： t(N)=2t(N/2)+N/2t(N)=2t(N/2)+N/2 t(N)=2t(N/2)+N/2 计算次数为 O(NlogN)O(NlogN)O(NlogN) ,每次插入 O(logN)O(logN)O(logN) ,故总插入复杂度为 O(Nlog2N)O(Nlog^2N)O(Nlog2N),高于一般整体二分的 O(NlogN)O(NlogN)O(NlogN),但是加上询问为 O((N+Q)log2N)O((N+Q)log^2N)O((N+Q)log2N),依旧达标。使用小技巧优化只能优化少数极端情况或递归开销。 整体二分可能比主席树更难理解，但是…… Code!Code!Code! 时间复杂度：O(NlogNlogV)O(NlogNlogV)O(NlogNlogV) 本题其它解法：树状数组套树状数组 O(Nlog3N)O(Nlog^3N)O(Nlog3N)