← 返回题目列表

Codeforces · 1742/F

F. 较小

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

Alperen 有两个字符串,$$$s$$$ 和 $$$t$$$,它们最初都等于“a”。

他将对给定的字符串执行两种类型的 $$$q$$$ 操作:

- $$$1 \;\; k \;\; x$$$ — 在字符串 $$$s$$$ 末尾追加字符串 $$$x$$$ 恰好 $$$k$$$ 次。换句话说,$$$s := s + \underbrace{x + \dots + x}_{k \text{ times}}$$$。
- $$$2 \;\; k \;\; x$$$ — 在字符串 $$$t$$$ 末尾追加字符串 $$$x$$$ 恰好 $$$k$$$ 次。换句话说,$$$t := t + \underbrace{x + \dots + x}_{k \text{ times}}$$$。

每次操作后,确定是否可以重新排列 $$$s$$$ 和 $$$t$$$ 的字符,使得 $$$s$$$ 按字典顺序小于 $$$^{\dagger}$$$ 小于 $$$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”。

示例

输入 #1

3
5
2 1 aa
1 2 a
2 3 a
1 2 b
2 3 abca
2
1 5 mihai
2 2 buiucani
3
1 5 b
2 3 a
2 4 paiu

输出 #1

YES
NO
YES
NO
YES
NO
YES
NO
NO
YES

注意

在第一个测试用例中,字符串最初为 $$$s = $$$ "a" 和 $$$t = $$$ "a"。

第一次操作后,字符串 $$$t$$$ 变为“aaa”。由于“a”按字典顺序已经小于“aaa”,因此此操作的答案应该是“YES”。

第二个操作字符串$$$s$$$变成“aaa”后,由于$$$t$$$也等于“aaa”,我们不能以任何方式排列$$$s$$$使其在字典顺序上小于$$$t$$$,所以答案是“NO”。

在第三个操作字符串 $$$t$$$ 变为“aaaaaa”之后,$$$s$$$ 按字典顺序已经小于它,因此答案为“YES”。

第四次操作后 $$$s$$$ 变为“aaabb”,并且无法使其按字典顺序小于“aaaaaa”,因此答案为“NO”。

第五次操作后,字符串$$$t$$$变为“aaaaaaabcaabcaabca”,我们可以将字符串重新排列为:“bbaaa”和“caaaaaabcaabcaabaa”,以便$$$s$$$按字典顺序小于$$$t$$$,因此我们应该回答“YES”。