CF1742F Smaller

Alperen 有两个字符串 $s$ 和 $t$，它们最初都等于 "a"。 他将对给定的字符串进行 $q$ 次两种类型的操作： - $1\;\;k\;\;x$ — 在字符串 $s$ 的末尾追加字符串 $x$ 恰好 $k$ 次。换句话说，$s := s + \underbrace{x + \dots + x}_{k \text{ 次}}$。 - $2\;\;k\;\;x$ — 在字符串 $t$ 的末尾追加字符串 $x$ 恰好 $k$ 次。换句话说，$t := t + \underbrace{x + \dots + x}_{k \text{ 次}}$。 每次操作后，判断是否可以重新排列 $s$ 和 $t$ 的字符，使得 $s$ 的字典序严格小于 $t$。 注意，字符串在每次操作后都会发生变化，不会回到初始状态。 $^\dagger$ 简单来说，字典序就是单词在字典中的排列顺序。形式化定义如下：如果存在某个位置 $i$，使得 $p_i < q_i$，并且对于所有 $j < i$，都有 $p_j = q_j$，那么字符串 $p$ 的字典序小于字符串 $q$。如果不存在这样的 $i$，那么当 $p$ 的长度小于 $q$ 的长度时，$p$ 的字典序也小于 $q$。例如，$\texttt{abdc} < \texttt{abe}$，$\texttt{abc} < \texttt{abcd}$。我们记 $p < q$ 表示 $p$ 的字典序小于 $q$。

输入的第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。 每个测试用例的第一行包含一个整数 $q$（$1 \leq q \leq 10^5$）——表示 Alperen 将要执行的操作次数。 接下来的 $q$ 行，每行包含两个正整数 $d$ 和 $k$（$1 \leq d \leq 2$；$1 \leq k \leq 10^5$）以及一个非空的小写英文字母字符串 $x$，分别表示操作类型、追加字符串 $x$ 的次数和需要追加的字符串。 保证所有测试用例中 $q$ 的总和不超过 $10^5$，所有输入字符串 $x$ 的总长度不超过 $5 \cdot 10^5$。

对于每次操作，如果可以重新排列两个字符串使得 $s$ 的字典序严格小于 $t$，输出 "YES"；否则输出 "NO"。

在第一个测试用例中，字符串最初为 $s = $ "a"，$t = $ "a"。 第一次操作后，字符串 $t$ 变为 "aaa"。由于 "a" 的字典序已经小于 "aaa"，所以本次操作的答案应为 "YES"。 第二次操作后，字符串 $s$ 变为 "aaa"，而 $t$ 也等于 "aaa"，无法重新排列使 $s$ 的字典序严格小于 $t$，所以答案为 "NO"。 第三次操作后，字符串 $t$ 变为 "aaaaaa"，$s$ 已经小于 $t$，所以答案为 "YES"。 第四次操作后，$s$ 变为 "aaabb"，无论如何排列都无法使其字典序小于 "aaaaaa"，所以答案为 "NO"。 第五次操作后，$t$ 变为 "aaaaaaabcaabcaabca"，我们可以将字符串重新排列为："bbaaa" 和 "caaaaaabcaabcaabaa"，此时 $s$ 的字典序小于 $t$，所以答案为 "YES"。 由 ChatGPT 4.1 翻译