Smaller

题意翻译

你有两个字符串 $s$ 和 $t$，它们初始都为 a，你会对字符串进行 $q$ 次操作两种类型的操作： $1 k x$ ，在 $s$ 末尾添加字符串 $k$ 恰好 $x$ 次 $2 k x$ ，在 $t$ 末尾添加字符串 $k$ 恰好 $x$ 次 求每次操作之后，是否可以重新排列 $s$ 和 $t$ 的字符，使 $s$ 字典序比 $t$ 小，如果可以，则输出“YES”，否则输出“NO”。

题目描述

Alperen has two strings, $ s $ and $ t $ which are both initially equal to "a". He will perform $ q $ operations of two types on the given strings: - $ 1 \;\; k \;\; x $ — Append the string $ x $ exactly $ k $ times at the end of string $ s $ . In other words, $ s := s + \underbrace{x + \dots + x}_{k \text{ times}} $ . - $ 2 \;\; k \;\; x $ — Append the string $ x $ exactly $ k $ times at the end of string $ t $ . In other words, $ t := t + \underbrace{x + \dots + x}_{k \text{ times}} $ . After each operation, determine if it is possible to rearrange the characters of $ s $ and $ t $ such that $ s $ is lexicographically smaller $ ^{\dagger} $ than $ t $ . Note that the strings change after performing each operation and don't go back to their initial states. $ ^{\dagger} $ Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. A formal definition is as follows: string $ p $ is lexicographically smaller than string $ q $ if there exists a position $ i $ such that $ p_i < q_i $ , and for all $ j < i $ , $ p_j = q_j $ . If no such $ i $ exists, then $ p $ is lexicographically smaller than $ q $ if the length of $ p $ is less than the length of $ q $ . For example, $ \texttt{abdc} < \texttt{abe} $ and $ \texttt{abc} < \texttt{abcd} $ , where we write $ p < q $ if $ p $ is lexicographically smaller than $ q $ .

输入输出格式

输入格式

The first line of the input contains an integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The first line of each test case contains an integer $ q $ $ (1 \leq q \leq 10^5) $ — the number of operations Alperen will perform. Then $ q $ lines follow, each containing two positive integers $ d $ and $ k $ ( $ 1 \leq d \leq 2 $ ; $ 1 \leq k \leq 10^5 $ ) and a non-empty string $ x $ consisting of lowercase English letters — the type of the operation, the number of times we will append string $ x $ and the string we need to append respectively. It is guaranteed that the sum of $ q $ over all test cases doesn't exceed $ 10^5 $ and that the sum of lengths of all strings $ x $ in the input doesn't exceed $ 5 \cdot 10^5 $ .

输出格式

For each operation, output "YES", if it is possible to arrange the elements in both strings in such a way that $ s $ is lexicographically smaller than $ t $ and "NO" otherwise.

输入输出样例

输入样例 #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

说明

In the first test case, the strings are initially $ s = $ "a" and $ t = $ "a". After the first operation the string $ t $ becomes "aaa". Since "a" is already lexicographically smaller than "aaa", the answer for this operation should be "YES". After the second operation string $ s $ becomes "aaa", and since $ t $ is also equal to "aaa", we can't arrange $ s $ in any way such that it is lexicographically smaller than $ t $ , so the answer is "NO". After the third operation string $ t $ becomes "aaaaaa" and $ s $ is already lexicographically smaller than it so the answer is "YES". After the fourth operation $ s $ becomes "aaabb" and there is no way to make it lexicographically smaller than "aaaaaa" so the answer is "NO". After the fifth operation the string $ t $ becomes "aaaaaaabcaabcaabca", and we can rearrange the strings to: "bbaaa" and "caaaaaabcaabcaabaa" so that $ s $ is lexicographically smaller than $ t $ , so we should answer "YES".

**题目大意：**

有两个初始都为 "a" 的字符串 s 和 t。进行 q 次操作，有两种操作类型：

1. $1 \; k \; x$：将字符串 x 添加到 s 的末尾恰好 k 次。
2. $2 \; k \; x$：将字符串 x 添加到 t 的末尾恰好 k 次。

每次操作后，判断是否可以通过重新排列 s 和 t 的字符，使得 s 的字典序小于 t。如果可以，输出 “YES”，否则输出 “NO”。

**输入输出数据格式：**

**输入格式：**

第一行包含一个整数 t（$1 \leq t \leq 10^4$）—— 测试用例的数量。

每个测试用例的第一行包含一个整数 q（$1 \leq q \leq 10^5$）—— 要执行的操作数。

然后是 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”。**题目大意：** 有两个初始都为 "a" 的字符串 s 和 t。进行 q 次操作，有两种操作类型： 1. $1 \; k \; x$：将字符串 x 添加到 s 的末尾恰好 k 次。 2. $2 \; k \; x$：将字符串 x 添加到 t 的末尾恰好 k 次。 每次操作后，判断是否可以通过重新排列 s 和 t 的字符，使得 s 的字典序小于 t。如果可以，输出 “YES”，否则输出 “NO”。 **输入输出数据格式：** **输入格式：** 第一行包含一个整数 t（$1 \leq t \leq 10^4$）—— 测试用例的数量。 每个测试用例的第一行包含一个整数 q（$1 \leq q \leq 10^5$）—— 要执行的操作数。 然后是 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”。