P17751 「RSOI-2D」星光 / star

题目来源：【HT-124-Div.3】核桃 CSP-J 组模拟赛

一所幼儿园里有 $30$ 颗魔法星星，编号从 $1$ 到 $30$。每颗星星都可以是亮或灭两种状态，分别对应 `1` 和 `0`。 一个星光组合是一个长度为 $30$ 的只由 `0` 和 `1` 组成的字符串，字符串的每一位分别表示每颗星星的状态。幼儿园里的小朋友各自喜欢**一个**星光组合，且任意两名小朋友喜欢的星光组合**互不相同**。 今天，老师指定了两个星光组合 $k$ 和 $r$。对于任意两个喜欢的星光组合为 $u$ 和 $v$ 的小朋友，当且仅当同时满足以下两个条件时，他们会成为好朋友： - 第一个条件：在 $r$ 中所有星星是亮着的位置上，$u$ 和 $v$ 亮着的星星数量相同（换句话说，对于 $1 \le i \le 30$，满足 $r_i = 1$ 且 $u_i = 1$ 的 $i$ 的数量，与满足 $r_i = 1$ 且 $v_i = 1$ 的 $i$ 的数量相等）； - 第二个条件：下面两个情况**至少**有一个成立： - 第一种情况：$u$ 和 $v$ 状态不同的星星总数是奇数； - 第二种情况：$u$ 和 $v$ 状态不同的星星恰好就是 $k$ 中亮着的那些星星（换句话说，对于任意 $1 \le i \le 30$，$u_i$ 和 $v_i$ 不同当且仅当 $k_i = 1$）。 初始时，幼儿园里没有小朋友。接下来会发生 $q$ 个事件，每次事件为以下两种情况之一： - `+ x`：喜欢的星光组合为 $x$ 的小朋友来到幼儿园（保证这位小朋友此时不在幼儿园中）。 - `- x`：喜欢的星光组合为 $x$ 的小朋友离开幼儿园（保证这位小朋友此时在幼儿园中）。 每次事件发生后，你需要回答：当前在幼儿园的小朋友中，是否存在**至少**三个小朋友，他们两两互为好朋友。如果存在，则答案为 `YES`；否则答案为 `NO`。

第一行，包含一个整数 $q$，表示事件的数量。 第二行，包含两个长度为 $30$ 的字符串 $k$ 和 $r$，仅包含字符 $0$ 和 $1$，中间用一个空格隔开。字符串的从左到右第 $i$ 个字符对应星星 $i$ 的状态。 接下来 $q$ 行，每行一个字符（`+` 或 `-`）和一个长度为 $30$ 的字符串 $x$，中间用空格隔开，表示一个事件。字符串 $x$ 仅包含 $0$ 和 $1$，第 $i$ 个字符对应星星 $i$ 的状态。

共 $q$ 行，每行一个字符串 `YES` 或 `NO`，表示每次事件对应的答案。

**【样例解释 #1】** > 注：下文“仅 $30$ 亮”中“$30$”的指的是编号为 $30$ 的星星，其他类似表述亦然。 - `+ 000000000000000000000000000000`：当前仅有一位小朋友，显然没有至少三人两两为友，答案为 `NO`。 - `+ 000000000000000000000000000001`：两位小朋友的星光组合分别为全灭和仅 $30$ 亮。在 $r$ 中亮着的星星 $30$ 上，两者均为灭，亮星数相同，满足第一个条件；两者状态不同的星星数量是奇数（有 $1$ 颗星星状态不同），满足第一种情况。因此，两人成为好朋友。虽然两人互为好友，但题目要求至少三人，因此答案为 `NO`。 - `+ 000000000000000000000000000101`：三位小朋友的组合分别为全灭、仅 $30$ 亮和 $29, 30$ 亮。其中 `0`（此处省略前导 `0`，下同）和 `101` 状态不同的星星与 $k$ 中亮着的星星（$29, 30$）相同，满足第二种情况，成为朋友。`1` 和 `101` 状态不同的星星有 $1$ 颗（星星 $29$），满足第一种情况，成为朋友。加上已有的 `0` 和 `1` 的朋友关系，三人两两为友，构成一个三角形友谊，答案为 `YES`。 - `- 000000000000000000000000000001`：组合为 `1` 的小朋友离开，剩余两人人数不足，因此答案为 `NO`。 剩余一个事件不再解释。 **【数据范围】** 对于所有测试数据，保证：$1 \le q \le 2 \times 10^5$，$k, r, x$ 的长度为 $30$ 且仅包含 `0` 和 `1`。$k$ 不全为 `0`； > 注：下表中“前 $t$ 位为 `0`”是指字符串**从左到右**的**前** $t$ 个字符均为 `0`； > > “无特殊限制”指除了**对于所有测试数据的限制**和**特殊性质**以外，没有其他限制。 | 测试点编号 | $q \le$ | $k$ | $r$ | 所有 $x$ | 特殊性质 | | :---: | :---: | --- | --- | --- | --- | | $1 \sim 4$ | $2\times 10^2$ | 前 $22$ 位为 `0` | 前 $22$ 位为 `0` | 前 $22$ 位为 `0` | 无 | | $5 \sim 8$ | $2\times 10^3$ | 前 $19$ 位为 `0` | 前 $19$ 位为 `0` | 前 $19$ 位为 `0` | 无 | | $9$ | $5\times 10^3$ | 前 $16$ 位为 `0` | 前 $16$ 位为 `0` | 前 $16$ 位为 `0` | $r$ 全为 `0` | | $10 \sim 12$ | $10^5$ | 前 $16$ 位为 `0` | 前 $16$ 位为 `0` | 前 $16$ 位为 `0` | 无 | | $13 \sim 15$ | $2 \times 10^5$ | 前 $10$ 位为 `0` | 前 $10$ 位为 `0` | 前 $10$ 位为 `0` | 无 | | $16$ | $2 \times 10^5$ | 无特殊限制 | 无特殊限制 | 无特殊限制 | $k$ 中 `1` 的个数为奇数 | | $17 \sim 20$ | $2 \times 10^5$ | 无特殊限制 | 无特殊限制 | 无特殊限制 | 无 |