← 返回题目列表

Codeforces · 2066/E

E. 热带季节

中文机器翻译题面 查看原题

你有 $$$n$$$ 个无限容量的桶。第 $$$i$$$ 个桶最初含有 $$$a_i$$$ 公斤水。在这个问题中,我们假设所有桶的重量相同。

你知道,其中一个桶的表面分布着少量的热带毒物,总重量为$$$0.179$$$公斤。然而,你不知道哪个桶里装有毒药。你的任务是识别这个有毒的桶。

所有的桶都在秤上。不幸的是,秤并没有显示每个桶的确切重量。相反,对于每对桶,它们显示了这些桶的重量之间的比较结果。因此,对于任意两个桶,您可以确定它们的重量是否相等,如果不相等,则确定哪个桶更重。毒药和水都包含在桶的重量中。

秤始终处于开启状态,并且秤中的信息可以无限次使用。

你还有倒水的能力。您可以将任意数量的水从任意桶倒入任意其他桶中。

然而,要倒水,你必须用手触摸你倒水的桶,所以如果那恰好是有毒的桶,你就会死。必须避免这种结果。

但是,你可以将水倒入有毒的桶中而不接触它。

换句话说,你可以选择数字 $$$i, j, x$$$ ($$$i \neq j, 1 \leq i, j \leq n, 0 < x \leq a_i$$$,编号为$$$i$$$的桶——不是有毒的)并执行 $$$a_i := a_i - x$$$, $$$a_j := a_j + x$$$。其中 $$$x$$$ 不一定是整数。

是否可以通过倾倒和秤的信息来保证识别哪个桶含有毒物并保持活力?您知道毒药正好位于其中一个桶上。

此外,我们要求您处理 $$$q$$$ 查询。在每个查询中,要么删除一个现有的桶,要么添加一个装有一定量水的额外桶。每次询问后,您需要回答是否可以保证毒桶的识别,前提是确实有一个。

输入

第一行包含两个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^6$$$) — 现有桶中的水量。

接下来的 $$$q$$$ 行包含查询,每行一个。每个查询的形式都是 + x 或 - x,这分别意味着添加和删除装有 $$$x$$$ 公斤水的桶。保证当进行查询 - x 时,现有桶之一的体积为 $$$x$$$,并且在整个查询过程中始终至少剩余一个桶。在所有查询中,$$$1 \leq x \leq 10^6$$$。

输出

输出$$$q+1$$$行,所有查询之前和每个查询之后问题的答案。如果可以识别有毒桶,则输出“Yes”;否则,输出“No”。您可以在任何情况下输出答案(上限或下限)。例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定响应。

示例

输入 #1

4 7
2 2 4 11
- 2
+ 4
+ 30
+ 40
- 4
+ 2
+ 2

输出 #1

Yes
No
Yes
No
Yes
No
No
Yes

输入 #2

6 7
5000 1000 400 400 100 99
+ 1
- 5000
- 1
- 400
- 400
- 100
- 99

输出 #2

No
Yes
Yes
Yes
No
No
No
Yes

注意

在第一个测试中,在进行任何查询之前,桶的重量为 $$$[2, 2, 4, 11]$$$。您可以比较第一桶和第二桶的值。如果结果不相等,则可以明确得出重量较大的桶有毒的结论。如果结果相同,则两个桶都是无毒的。然后你可以将第一个桶中的所有内容物倒入第二个桶中。之后,第二桶和第三桶都将含有 $$$4$$$ 公斤水。现在我们来比较一下第二桶和第三桶的数值。如果结果不相等,则重量较大的桶有毒。否则,两个桶都是无毒的。唯一可能有毒的桶是 4 号桶。因此,通过这种策略,无论重量如何,我们都可以安全地确定有毒桶。