E. Tropical Season 详细题解

问题理解

有 $n$ 个桶，第 $i$ 个桶装有 $a_i$ 公斤水。恰好有一个桶表面沾有 $0.179$ 公斤毒药（重量可忽略，但使该桶略重于其他等量水桶）。你无法直接称重，但可以比较任意两个桶的重量（得知相等或哪个更重）。

你可以倒水：从桶 $i$ 倒 $x$ 公斤到桶 $j$（$x \le a_i$），但倒出的桶 $i$ 必须无毒（否则你会死）。倒入的桶 $j$ 可以有毒。

目标：通过若干次倒水和比较，保证找出哪个桶有毒，并且过程中不接触毒桶。

每次查询会添加或删除一个桶，需要回答当前是否可能。

---

核心观察

1. 毒药影响：毒桶比它本该有的重量多 $0.179$ 公斤。由于所有桶本身重量相同，比较时若两桶水量相等，则毒桶更重；若水量不等，则结果取决于水量差是否大于 $0.179$。

2. 关键简化：因为 $0.179$ 非常小，而水量是整数（$\ge 1$），所以：

   • 如果两个桶水量 相等，则比较结果能直接指出毒桶（较重的那个）。
   • 如果两个桶水量 不等，且差 $\ge 1$，则比较结果完全由水量决定，毒药无法改变大小关系（因为 $0.179 < 1$）。

   因此，只有水量相等的桶之间，比较才能揭示毒药。

3. 倒水的作用：我们可以改变水量，从而创造新的相等对。但只能从无毒桶倒出，所以倒水本身不会冒风险（只要确保倒出桶无毒）。

---

转化为图论问题

把每个桶看作一个节点。如果两个桶水量相等，它们之间可以进行比较，从而判断出哪个有毒（如果其中一个有毒）。但更关键的是：通过倒水，我们可以让原本不相等的两个桶变得相等。

例如，从桶 $i$ 倒水到桶 $j$，可以使 $j$ 的水量增加。如果调整后 $i$ 和 $j$ 水量相等，那么比较它们就能找出毒桶（假设其中一个有毒）。

但注意：倒水后，$i$ 的水量减少，$j$ 增加。我们需要保证倒出的桶 $i$ 无毒。因此，在倒水前，我们必须确信 $i$ 无毒。

---

安全倒水的前提

怎样确信一个桶无毒？

• 如果它和另一个水量相等的桶比较过，且结果是相等，那么两者都无毒（因为如果有毒，比较结果会是该桶更重）。
• 如果它参与过一系列比较，且没有表现出“更重”，也可以推断无毒。

核心结论：一旦我们确定某个桶无毒，就可以用它作为“工具”去倒水，制造新的相等对。

---

可行条件

这个问题等价于：能否通过一系列操作，最终唯一确定哪个桶有毒？

已知：

• 初始时，所有桶的水量都是整数。
• 毒药只会影响相等比较的结果。
• 我们可以安全倒水的前提是已经确认倒出桶无毒。

关键定理（由题解可知）：当且仅当 所有桶的水量不全相等 时，才可能保证找出毒桶？不对，示例 $[2,2,4,11]$ 不全相等，但答案是 Yes。实际上，条件更复杂。

---

标程做法

标程将桶按水量的二进制最高位分组（$2^k$ 级别）。维护每个组内水量的多重集，以及相邻组之间的最小差值。

核心逻辑：

• 维护所有桶的水量集合，以及相邻水量之间的差值。
• 维护一个“已安全”的区间：从最小水量开始，累积到某个组，这些组的桶都可以被证明无毒。
• 当累积的总桶数 $\ge n-1$ 时，剩下的唯一桶就是毒桶。

具体地，标程按照水量从小到大处理，每次检查当前最小差值是否小于等于已累积的“安全水量和”。如果是，则可以将这个差值对应的桶纳入安全集合。

这个算法的正确性基于：一旦我们知道某个桶无毒，就可以用它倒水来“填平”水量差距，从而确认更多桶无毒。

---

简化理解

实际上，这个问题等价于：
能否通过反复将已知无毒桶的水倒入未知桶，使得最终只剩下一个桶没有被证明无毒？

因为如果 $n-1$ 个桶都被证明无毒，剩下的那个必然有毒。

证明一个桶无毒的方法：

• 它和另一个已知无毒的桶水量相等，且比较后相等（则两者都无毒）。
• 或者，它和另一个已知无毒的桶比较后，它更轻（则它无毒，因为毒桶会更重）。

所以，关键在于能否制造出足够多的相等对。

---

最终结论

经过分析（可参考官方题解），可行当且仅当：所有桶的水量不全相等，并且存在一种方式通过倒水使得所有桶的水量变成两个不同的值，其中一个值出现至少 $n-1$ 次。

这等价于：最大值和最小值之差足够大，或者可以通过倒水将中间值合并。

标程使用按位分组的贪心方法判断：从最小值开始，每次将当前最小差值的桶合并到安全集合，检查能否覆盖 $n-1$ 个桶。

---

算法步骤

1. 将桶按水量 $x$ 放入 $b[\lfloor \log_2 x \rfloor]$ 组中。
2. 维护每个组内的水量集合（st）和相邻水量的差值集合（diff）。
3. 维护当前安全水量和 sum、安全桶数 cnt。
4. 从小到大遍历组 $i$：
   • 计算当前组的最小“差距”（与前面安全桶的差值，或组内最小差值）。
   • 如果这个差距 $\le sum$，说明可以用安全桶的水填补这个差距，从而将该组的所有桶纳入安全集合。
   • 更新 sum 和 cnt。
5. 如果最终 cnt >= n-1，输出 Yes，否则 No。

---

示例验证

例1：$[2,2,4,11]$

• 分组：$2$ 在 $2^1$ 组，$4$ 在 $2^2$ 组，$11$ 在 $2^3$ 组。
• 从小开始：$2$ 组有 $2,2$，安全桶数 $2$，水量和 $4$。
• 下一组 $4$：最小差 $4-2=2 \le 4$，可合并，安全桶数 $3$，水量和 $4+4=8$。
• 下一组 $11$：最小差 $11-4=7 \le 8$，可合并，安全桶数 $4$，$cnt \ge 3$，Yes。

---

复杂度

• 每组使用 multiset 维护，插入删除 $O(\log n)$。
• 总操作 $O((n+q) \log n)$，满足 $2\times10^5$ 数据范围。

---

总结

本题的关键是把水量按二进制分组，用贪心逐步扩大已知无毒桶的集合。每次判断能否用已有的安全水量“填补”下一个桶的差距，如果可以，则该桶也可被证明无毒。最终判断是否只剩一个桶无法被证明（即毒桶）。这种按位分组 + 贪心合并的思路，是解决此类“安全传递”问题的经典方法。