CF2021C2 Adjust The Presentation (Hard Version)

这是该问题的困难版本。在两个版本中，$q$ 的约束和时间限制不同。在本版本中，$0 \leq q \leq 2 \cdot 10^5$。只有在所有版本的问题都被解决后，你才能进行 hack。 有一个由 $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$。如果可以在上述规则下，使得第 $i$ 页幻灯片由成员 $b_i$ 展示（对于所有 $i$，$1 \leq i \leq m$），则称这场幻灯片展示是好的。 然而，你那令人讨厌的老板想对数组 $b$ 进行 $q$ 次更新。在第 $i$ 次更新中，他会选择一页幻灯片 $s_i$ 和一名成员 $t_i$，并将 $b_{s_i}$ 设为 $t_i$。注意，这些更新是持久的，即对 $b$ 的更改会影响后续的所有更新。 对于数组 $b$ 的每一个状态（初始状态及每次 $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$），表示成员从前到后的初始顺序。保证 $a$ 是 $1$ 到 $n$ 的一个排列。 第三行包含 $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$。

对于每个测试用例，输出 $q+1$ 行，分别对应数组 $b$ 的 $q+1$ 个状态。若该状态下幻灯片展示是好的，输出 "YA"，否则输出 "TIDAK"。 输出不区分大小写。例如，"yA"、"Ya"、"ya" 和 "YA" 都被视为肯定回答。

对于第一个测试用例，你不需要移动成员，因为两页幻灯片都由成员 $1$ 展示，他已经在队伍最前面。之后，设置 $b_1 := 2$，此时第 $1$ 页必须由成员 $2$ 展示，但成员 $1$ 会先展示第 $1$ 页，这是不可能的。再将 $b_1 = 1$，此时 $b$ 又回到初始状态，幻灯片展示再次变得可行。 由 ChatGPT 4.1 翻译