← 返回题目列表

Codeforces · 2021/C2

C2. 调整演示文稿(硬版)

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

这是问题的困难版本。两个版本中,$$$q$$$ 的约束和时间限制是不同的。在此版本中,$$$0 \leq q \leq 2 \cdot 10^5$$$。只有当问题的所有版本都得到解决后,你才能进行黑客攻击。

由 $$$n$$$ 成员组成的团队,编号从 $$$1$$$ 到 $$$n$$$,准备在大型会议上演示幻灯片。幻灯片放映包含 $$$m$$$ 幻灯片。

有一个长度为$$$n$$$的数组$$$a$$$。最初,成员从前到后按照 $$$a_1、a_2、\ldots、a_n$$$ 的顺序站成一排。幻灯片放映将从幻灯片 $$$1$$$ 到幻灯片 $$$m$$$ 顺序呈现。每个部分都将由排在前面的成员进行介绍。每张幻灯片放映完毕后,您可以将排在前面的成员移动到队列中的任何位置(不改变其余成员的顺序)。例如,假设成员行是 $$$[\color{red}{3},1,2,4]$$$。成员 $$$3$$$ 展示当前幻灯片后,您可以将成员行更改为 $$$[\color{red}{3},1,2,4]$$$、$$$[1,\color{red}{3},2,4]$$$、$$$[1,2,\color{red}{3},4]$$$ 或 $$$[1,2,4,\color{red}{3}]$$$。

还有一个长度为$$$m$$$的数组$$$b$$$。如果可以使成员$$$b_i$$$在这些约束下为从$$$1$$$到$$$m$$$的所有$$$i$$$呈现幻灯片$$$i$$$,则幻灯片放映被认为是好的。

然而,你烦人的老板想要对数组 $$$b$$$ 进行 $$$q$$$ 更新。在第 $$$i$$$ 次更新中,他将选择幻灯片 $$$s_i$$$ 和成员 $$$t_i$$$ 并设置 $$$b_{s_i} := t_i$$$。请注意,这些更新是持久的,即对数组 $$$b$$$ 所做的更改将在处理将来的更新时应用。

对于数组 $$$b$$$ 的每个 $$$q+1$$$ 状态、初始状态以及每个 $$$q$$$ 更新后,确定幻灯片是否良好。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n, m \le 2 \cdot 10^5$$$; $$$0 \leq q \leq 2 \cdot 10^5$$$) — 成员数量和部分数量。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le n$$$) - 成员从前到后的初始顺序。保证从 $$$1$$$ 到 $$$n$$$ 的每个整数在 $$$a$$$ 中恰好出现一次。

每个测试用例的第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \ldots, b_m$$$ ($$$1 \le b_i \le n$$$) - 应该呈现每个部分的成员。

接下来的 $$$q$$$ 行包含两个整数 $$$s_i$$$ 和 $$$t_i$$$ ($$$1 \le s_i \le m$$$, $$$1 \le t_i \le n$$$) — 更新的参数。

保证所有测试用例的$$$n$$$之和、$$$m$$$之和以及$$$q$$$之和分别不超过$$$2 \cdot 10^5$$$。

输出

对于每个测试用例,输出与数组 $$$b$$$ 的 $$$q+1$$$ 状态相对应的 $$$q+1$$$ 行。如果幻灯片放映良好,则输出“YA”,否则输出“TIDAK”。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“yA”、“Ya”、“ya”和“YA”将被识别为肯定响应。

示例

输入 #1

3
4 2 2
1 2 3 4
1 1
1 2
1 1
3 6 2
1 2 3
1 1 2 3 3 2
3 3
2 2
4 6 2
3 1 4 2
3 1 1 2 3 4
3 4
4 2

输出 #1

YA
TIDAK
YA
YA
TIDAK
YA
TIDAK
YA
YA

注意

对于第一个测试用例,您不需要移动成员,因为两张幻灯片都是由成员 $$$1$$$ 演示的,他已经位于队列的前面。之后,设置$$$b_1 := 2$$$,现在幻灯片$$$1$$$必须由会员$$$2$$$呈现,这是不可能的,因为会员$$$1$$$将首先呈现幻灯片$$$1$$$。然后,设置$$$b_1 = 1$$$,$$$b$$$ 与最初的$$​​$b$$$ 相同,从而可以进行良好的演示。