这是问题的困难版本。两个版本之间的差异在于对所有变量的约束。只有当问题的两个版本都得到解决时,你才能进行黑客攻击。
Tsovak 和 Narek 正在玩游戏。它们有一个数组 $$$a$$$ 和一个整数矩阵 $$$b$$$,其中包含 $$$n$$$ 行和 $$$m$$$ 列,从 $$$1$$$ 开始编号。第 $$$i$$$ 行和第 $$$j$$$ 列中的单元格为 $$$(i, j)$$$。
他们依次寻找$$$a$$$的元素;佐瓦克首先开始。每次玩家在矩阵中查找包含 $$$a$$$ 当前元素的单元格(Tsovak 查找第一个,然后 Narek 查找第二个,等等)。假设玩家选择了单元格 $$$(r, c)$$$。下一个玩家必须在子矩阵中选择他的单元格,从 $$$(r + 1, c + 1)$$$ 开始,到 $$$(n, m)$$$ 结束(如果 $$$r=n$$$ 或 $$$c=m$$$ ,子矩阵可以为空)。如果玩家找不到这样的单元格(或者剩余的子矩阵为空)或数组结束(前一个玩家选择了最后一个元素),那么他就输了。
您的任务是在玩家发挥最佳的情况下确定获胜者。
注意:由于输入很大,您可能需要针对此问题优化输入/输出。
例如,在 C++ 中,在 main() 函数的开头使用以下几行就足够了:
输入
输入的第一行包含 $$$t$$$ ($$$1 \le t \le 1500$$$) – 测试用例的数量。
每个测试用例的第一行包含三个整数 $$$l$$$、$$$n$$$ 和 $$$m$$$ ($$$1 \le l, n, m \le 1500$$$) – 数组的大小和矩阵的大小。
第二行包含 $$$l$$$ 整数 $$$a_1, a_2, a_3, \ldots a_l$$$ ($$$1 \le a_i \le n \cdot m$$$) – 数组 $$$a$$$ 的元素。
最后 $$$n$$$ 行中的第 $$$i$$$ 包含 $$$m$$$ 整数 $$$b_{i,1}, b_{i,2}, b_{i,3}, \ldots b_{i,m}$$$ ($$$1 \le b_{i,j} \le n \cdot m$$$) – 表示矩阵的 $$$i$$$ 行。
保证所有测试用例的 $$$n \cdot m$$$ 总和不超过 $$$3 \cdot 10^6$$$。
保证所有测试用例的$$$l$$$总和不超过$$$1500$$$。
输出
您应该输出 $$$t$$$ 行,其中第 $$$i$$$ 包含一个代表第 $$$i$$$ 测试用例答案的字符:如果 Tsovak 获胜则为“T”,否则为“N”(不带引号)。
示例
输入 #1
3 2 2 3 1 2 1 3 6 4 6 2 2 2 4 1 2 1 1 3 2 4 2 5 1 2 4 2 1 2 3 4 5 6 7 8 8 8
输出 #1
N T N
注意
在第一个示例中,Tsovak 首先查找 $$$1$$$。 $$$1$$$ 在 $$$(1,1)$$$ 处只出现一次,因此他选择了它。然后 Narek 需要在 $$$(2, 2)$$$ 的子矩阵中查找 $$$2$$$,该子矩阵仅包含最后两个元素:$$$6$$$ 和 $$$2$$$。他选择了$$$2$$$,然后Tsovak 输了,因为阵列已经结束。
在第二个示例中,Tsovak 需要选择 $$$1$$$。单元格 $$$(n,m)$$$ 处有一个 $$$1$$$,因此他选择了该单元格。然后,由于 $$$(n + 1, m + 1)$$$ 的子矩阵为空,Narek 找不到 $$$2$$$,所以他输了。