1. 算法核心思路

问题转化

我们要找到一个满足条件（总花费 $\le g$，总体积 $\ge L$）的混合果汁，使其“美味度最小值”最大。 这依然是一个典型的二分答案问题。假设我们二分检查美味度 $D$，则意味着我们只能选用美味度 $\ge D$ 的所有果汁。在这些果汁中，我们为了尽可能满足体积和预算限制，策略一定是贪心地优先选择价格最低的果汁。

排序策略

代码中的结构体比较函数是：

bool operator < (const Node b) const {
    return d < b.d; // 按美味度从小到大排序
}

这意味着数组 $a$ 被升序排列。

• $a[1]$ 是美味度最低的。
• $a[n]$ 是美味度最高的。
• 对于任意下标 $i$，区间 $[i, n]$ 中的所有果汁美味度都 $\ge a[i].d$。

后缀主席树

为了快速查询“只考虑下标在 $[i, n]$ 范围内的果汁时的最小花费”，代码构建了后缀主席树。

• rt[i]：表示插入了果汁 $a[i], a[i+1], \dots, a[n]$ 后的线段树版本。
• 线段树的域：线段树的下标对应果汁的价格（$1 \sim 10^5$）。节点维护该价格区间内的总体积 (siz) 和总价格 (sum)。
• 构建过程：从 $n$ 到 $1$ 倒序插入。rt[i] 是在 rt[i+1] 的基础上插入果汁 $a[i]$ 得到的。

2. 代码函数详解

1. 数据结构

struct node {
    int ls, rs; // 左右子节点编号
    int siz;    // 该价格区间内的果汁总体积
    int sum;    // 该价格区间内的果汁总花费
} t[32 * N];

2. 修改操作 (update)

这是一个标准的主席树插入操作。

• fz(p)：复制节点 $p$，实现可持久化。
• 递归过程中，根据当前果汁的价格 a[x].p 决定向左子树还是右子树递归。
• 沿途更新节点的体积 siz 和总价 sum。

int update(int l, int r, int x, int p) {
    p = fz(p); // 复制节点
    t[p].siz += a[x].l; // 增加体积
    t[p].sum += a[x].p * a[x].l; // 增加花费
    // ... 递归左右子树 ...
    return p;
}

3. 查询操作 (query)

这是贪心策略的体现。在给定的线段树版本中（即限定了可选果汁的美味度范围），查询购买 $k$ 升果汁的最小花费。

• 优先向左子树（低价格区）走。
• 如果左子树的体积足够 (t[t[p].ls].siz >= k)，则全在左边买。
• 如果不够，先买光左子树的所有果汁（花费 t[t[p].ls].sum），剩下的体积去右子树买。

int query(int l, int r, int k, int p) {
    if (l == r) return k * l; // 叶子节点：单价 * 需要的体积
    // ...
    int sum = t[t[p].ls].siz; // 左子树的总量
    if (sum >= k) return query(..., t[p].ls); // 左边够用
    return query(..., k - sum, t[p].rs) + t[t[p].ls].sum; // 左边全买，去右边补
}

4. 主流程 (main)

1. 读入与排序：按美味度升序排序。
2. 构建主席树：

   rt[n + 1] = build(1, n); // 初始化空树（注：这里build参数其实应为价格范围，但空树影响不大）
   for (int i = n; i >= 1; -- i) // 倒序插入，构建后缀树
       rt[i] = update(1, 1e5, i, rt[i + 1]); 
   

   此时 rt[i] 代表了“只选用美味度 $\ge a[i].d$ 的果汁”所构成的权值线段树。
3. 处理询问（二分答案）：
   • 我们要找最大的美味度，即在排序后的数组中找最大的下标 res，使得后缀 $[res, n]$ 能满足小朋友的需求。
   • 二分范围 L=1, R=n。
   • check 逻辑：

     // 1. 检查总存量是否足够 L 升
     // 2. 检查买 L 升的最小花费是否 <= g
     if (t[rt[mid]].siz >= l && query(1, 1e5, l, rt[mid]) <= g) {
         res = mid;   // 记录答案
         L = mid + 1; // 尝试寻找更大的下标（更高的美味度）
     } else {
         R = mid - 1; // 没法满足，必须引入美味度更低的果汁（减小下标）
     }
     

3. 复杂度分析

• 时间复杂度：
  • 排序：$O(N \log N)$。
  • 建树：插入 $N$ 次，每次涉及 $O(\log (\max P))$ 个节点，总计 $O(N \log (\max P))$。
  • 查询：$M$ 次询问，每次二分 $O(\log N)$，二分内部查询主席树 $O(\log (\max P))$，总计 $O(M \log N \log (\max P))$。
• 空间复杂度：
  • 主席树节点数约为 $N \log (\max P)$。代码中开了 32 * N，对于 $10^5$ 的数据量是足够的。