题解：「ROI 2023 Day2 T3」Яблоки по корзинам（基于提供代码）

核心思路总览

本题通过 预处理关键阈值 + 二分查找 + 条件判断 高效响应查询，核心是提前计算苹果重量的“覆盖能力阈值”，将每组查询转化为阈值对比和二分查找，实现 $O(n\log n + q\log n)$ 复杂度，适配 $3 \times 10^5$ 规模数据。

关键概念与预处理逻辑

1. 核心问题转化

要判断 $(a, b)$ 是 $k$-完美的，本质是判断“重量≤k”的苹果集合，能否覆盖所有 $0 \leq x \leq a$、$0 \leq y \leq b$ 的数对。代码通过拆分苹果集合为“基础覆盖部分”和“扩展部分”，分别计算覆盖能力。

2. 预处理步骤拆解

（1）基础排序与前缀和

• 对苹果重量 升序排序（w[1..n]），方便后续按 $k$ 筛选苹果。
• 计算前缀和数组 sw，sw[t] 表示前 $t$ 个苹果（重量最小的 $t$ 个）的总重，用于快速获取“重量≤k”的苹果总重。

（2）计算基础覆盖阈值（p, mx, s0）

这一步是核心，筛选出能实现“连续覆盖”的基础苹果集合：

• 定义“基础集合”为前 $p-1$ 个苹果，满足“总重的一半 ≥ 下一个苹果重量 - 1”（s/2 >= w[p] - 1）。
• 核心逻辑：当苹果总重 $s$ 满足 $s \geq 2w_{i} - 1$ 时，这些苹果可组合出 $0 \sim s/2$ 之间的所有整数（类似“硬币找零”的连续覆盖特性）。
• 最终得到：
  • p：基础集合的边界（前 $p-1$ 个为基础苹果）。
  • s0：基础集合的总重。
  • mx：基础集合的最大连续覆盖值（mx = s0 / 2），即基础集合可独立覆盖 $0 \sim mx$ 的所有单篮子重量。

（3）计算扩展覆盖阈值（xx, x 数组）

基础集合之外的苹果（从 $p$ 开始）为“扩展苹果”，其重量较大，需单独计算对覆盖能力的贡献：

• 遍历扩展苹果，记录每个苹果加入后，总覆盖能力的变化，存储到 xx 数组（xx[i] = (l, d)，l 为覆盖阈值，d 为扩展部分总重）。
• 对 xx 数组去重、排序，得到精简后的 x 数组，用于快速查询扩展部分的最大可用重量。

代码核心函数解析（Calc(k, a, b)）

该函数是查询判断的核心，输入 $k, a, b$，返回是否为 $k$-完美，步骤如下：

1. 筛选“重量≤k”的苹果

通过 upper_bound 二分查找，找到重量≤k的苹果个数 t（前 t 个苹果）。

2. 简化判断条件

交换 $a$ 和 $b$，确保 $a \leq b$，减少后续判断的分支（只需关注较小值的覆盖情况）。

3. 分情况判断覆盖能力

情况1：仅使用基础集合（t < p）

此时可用苹果均为基础集合内的苹果，总重为 sw[t]。

• 核心条件：基础集合的总重需 ≥ $a + b$（因为基础集合可连续覆盖到 sw[t]/2，若总重≥$a+b$，则可拆分出任意 $x \leq a$、$y \leq b$ 且 $x+y \leq sw[t]$ 的数对）。
• 满足则返回 true，否则返回 false。

情况2：使用基础集合+部分扩展集合（t ≥ p）

此时可用苹果包含全部基础集合和部分扩展集合：

• d0：扩展部分中重量≤k的苹果总重（sw[t] - sw[p-1]）。
• d1：通过二分查找 x 数组，找到基础集合可支持的最大扩展贡献（即扩展部分中可利用的最大重量）。
• 核心条件：
  1. 基础集合的最大覆盖值 mx ≥ a（确保 $a$ 可被基础集合覆盖）。
  2. 基础集合剩余能力 + 扩展部分可用重量 ≥ $b$（s0 - a + min(d0, d1) ≥ b），确保 $b$ 可被覆盖。
• 两个条件均满足则返回 true，否则返回 false。

查询处理流程

1. 生成查询参数

根据输入的 j, c, d 和历史正确查询编号之和 v，生成实际查询的 $k, a, b$（k = j - v*z，a = c - v*z，b = d - v*z）。

2. 调用 Calc 函数判断

若返回 true，输出 Yes 并更新 v（累加当前查询编号）；否则输出 No。

关键验证（结合样例1）

样例1中苹果重量排序后为 [1,1,2,3,5,6,17,100]，预处理后：

• 基础集合 p 对应前若干个苹果，mx = s0/2 较大，可覆盖大部分小值 a。
• 第一个查询 k=6, a=15, b=3（交换后 a=3, b=15）：
  • 重量≤6的苹果总重 sw[6] = 1+1+2+3+5+6=18，t=6 ≥ p。
  • mx ≥ 3（满足），s0 - 3 + min(d0, d1) ≥15（满足），故输出 Yes。

复杂度分析

• 预处理阶段：排序 $O(n\log n)$，前缀和 $O(n)$，基础集合和扩展集合计算 $O(n)$，总复杂度 $O(n\log n)$。
• 查询阶段：每组查询包含两次二分查找（upper_bound 和 lower_bound），复杂度 $O(\log n)$，$q$ 组查询总复杂度 $O(q\log n)$。
• 整体复杂度 $O(n\log n + q\log n)$，可高效处理 $3 \times 10^5$ 规模数据。

关键结论

本题的核心是利用“连续覆盖阈值”预处理，将复杂的“双篮子覆盖问题”转化为“基础覆盖+扩展贡献”的条件判断。通过提前计算阈值和前缀和，结合二分查找，实现了查询的快速响应，避免了对每个查询的暴力模拟。