B4571 [合肥市初中组 2025 T3] 字符串

民间数据

小 C 有两个集合，分别为单词集 $D$ 和限制集 $R$，初始两个集合都是空集。 小 C 会进行 $m$ 次操作，操作分为以下两种： * `add s`（其中 $s$ 是一个字符串）：表示向单词集 $D$ 中加入一个字符串 $s$。 * `query s x`（其中 $s$ 是一个字符串，$x$ 是一个自然数）：表示向限制集 $R$ 中加入一个限制 $(s, x)$。 一个限制 $(s, x)$ 被满足当且仅当：单词集 $D$ 中至少有 $x$ 个字符串满足 $s$ 是它们的前缀。其中，字符串 $s$ 是 $t$ 的前缀当且仅当可以通过删除 $t$ 尾部的若干个（可以是 $0$ 个）字符得到 $s$。例如，`aaa` 是 `aaab` 的前缀，也是 `aaa` 的前缀。 小 C 想让你告诉他：在每次操作后，限制集 $R$ 中的所有限制是否**全部都被满足**。

第一行包含一个正整数 $m$ —— 表示总的操作次数。 接下来 $m$ 行，每行描述一次操作，格式为 `add s` 或 `query s x`。

输出共 $m$ 行。对于第 $i$ 次操作，如果操作完成后限制集中的所有限制全部都被满足，则在第 $i$ 行输出 `Yes`；否则输出 `No`。

#### ****样例解释**** 以第三次操作为例： 前三次操作完成后，$D = \{a, ab\}$，$R = \{(a, 2)\}$。 考虑 $(a, 2)$ 限制是否被满足：在集合 $D$ 中的字符串里，$a$ 是 $a$ 的前缀，$a$ 是 $ab$ 的前缀，因此恰好有 $2$ 个字符串满足条件。该限制被满足，所以输出 `Yes`。 #### ****其它样例说明**** * **样例 $2$**：见选手附加文件目录下的 `string/string2.in` 与 `string/string2.ans`。该样例满足测试点 $4 \sim 5$ 的约束条件。 * **样例 $3$**：见选手附加文件目录下的 `string/string3.in` 与 `string/string3.ans`。该样例满足测试点 $9 \sim 10$ 的约束条件。 #### ****数据范围**** 定义 $S$ 为所有操作中给定字符串的长度之和。对于所有测试数据，保证 $m \le 10^6$，$S \le 10^6$。 各测试点的附加限制如下表所示： | 测试点编号 | $m \le$ | $S \le$ | 特殊性质 | | :---: | :---: | :---: | :---: | | $1 \sim 2$ | $50$ | $50$ | 无 | | $3$ | $5000$ | $5000$ | 无 | | $4 \sim 5$ | $50$ | $50$ | $A$ | | $6$ | $10^6$ | $10^6$ | $A$ | | $7 \sim 8$ | $100$ | $500$ | $B$ | | $9 \sim 10$ | $10^6$ | $10^6$ | 无 | * **特殊性质 $A$**：所有 `query` 操作都在所有的 `add` 操作之后。 * **特殊性质 $B$**：最多只有一个 `query` 操作。