P10350 [PA 2024] Modernizacja Bajtocji

PA 2024 1A

**题目译自 [PA 2024](https://sio2.mimuw.edu.pl/c/pa-2024-1/dashboard/) Runda 1 [Modernizacja Bajtocji](https://sio2.mimuw.edu.pl/c/pa-2024-1/p/mod/)** Byteland 正在走向现代化。最新的政府项目旨在为那些没有电脑的村镇居民提供电脑。Byteasar 正在监督该计划中的一个村庄——Bytetown——的现代化进程，目前那里没有一个居民拥有电脑。 Bytetown 有 $n$ 个居民，为了简单起见，Byteasar 将他们用 $1$ 到 $n$ 的整数编号。最初没有一个居民拥有电脑。Byteasar 的任务是处理三种形式的事件： - $\texttt{+}\ a_i\ b_i$：将一台电脑送给 Bytetown 的居民。然而，Byteasar 并不知道电脑是送给了编号为 $a_i$ 还是 $b_i$ 的居民。可能会出现 $a_i = b_i$ 的情况——在这种情况下，电脑肯定送给了编号为 $a_i$ 的居民。可以确定的是，电脑被送到了目前还没有电脑的居民手中。 - $\texttt{-}\ c_i$：编号为 $c_i$ 的居民的电脑坏了。可以肯定的是，该居民曾经拥有一台电脑（但现在不再拥有，因此将来可能会收到一台新电脑）。 - $\texttt{?}\ d_i$：Byteasar 需要（利用**迄今为止**获得的所有信息）确定编号为 $d_i$ 的居民：肯定有电脑，肯定没有电脑，还是不确定他是否有电脑。 请编写一个程序，帮助 Byteasar 回答所提出的问题！ 注：在居民的电脑坏掉的前一刻，Byteasar 不一定可以确定这个居民是否有电脑。换句话说，在某居民电脑坏掉之前，不一定可以从之前的事件中确定他是否有电脑。

第一行包含两个整数 $n$ 和 $q\ (1\le n\le 300\, 000, 1\le q\le 1\,000\,000)$，分别表示 Bytetown 的居民人数和 Byteasar 需要处理的事件数量。 接下来的 $q$ 行描述了题目中的连续发生的事件。在所有事件中，$1 \le a_i,b_i,c_i,d_i \le n$。 保证 Byteasar 至少会被问及一次他知道的内容，即输入中至少包含一个 `?`，还保证至少有一次电脑送出过程，在这个过程中，电脑总会给一个目前不拥有电脑的人，且保证对于电脑坏掉事件中的居民，电脑坏掉时总会拥有一台电脑。

输出一个字符串，其长度等于 `?` 事件的个数。如果在第 $i$ 次查询时，该居民肯定有电脑，则该字符串中的第 $i$ 个字符为 `1`。如果该居民肯定没有电脑，则该字符串中的第 $i$ 个字符应为 `0`。如果不能确定该居民是否拥有电脑，则该序列中的第 $i$ 个字符应为 `?`。

最初没有人有电脑，所以第一个询问的答案为「否」，输出的第一个字符是 `0`。然后送出了两台电脑，我们又被问到另一位居民是否有电脑。有可能迄今为止送出的两台电脑中有一台是送给他的，但也有可能电脑是分别送给第一位和第三位居民的。因此，我们无法最终确定第二位居民是否有电脑，所以答案是 `?`。需要注意的是，在下一次送出之后，第二位居民肯定已经拥有了一台电脑，但在询问 Byteasar 时，他并不知道这一点。