---

题意重述（数学化）

有 $n$ 个人的初始排列 $a_1, a_2, \dots, a_n$（队头到队尾）。
有 $m$ 张幻灯片，第 $i$ 张需要由 $b_i$ 讲解。
流程：

1. 开始时队头的人讲当前幻灯片。
2. 讲完后，可以把这个人插入到队伍中的任意位置（其余人顺序不变）。
3. 重复直到所有幻灯片讲完。

问：是否存在一种移动方式，使得 $b_i$ 确实在第 $i$ 步讲。

---

核心观察

设 $p[x]$ 表示成员 $x$ 在初始队伍 $a$ 中的位置（1-based）。

在演示过程中，未讲过的人在队伍中的相对顺序保持为他们在 $a$ 中的顺序，因为：

• 只有讲完的人可以移动。
• 未讲过的人从未被移动过（他们只在轮到他们讲时才会成为队头并随后被移动，但一旦他们讲完就变成“已讲过”）。

因此，在任意时刻，未讲过的人在队伍中按照 $p$ 值递增排列（队头是 $p$ 最小的人）。

---

关键条件

假设我们按顺序处理 $b_1, b_2, \dots, b_m$，并维护一个集合 $S$ 表示已经讲过的人。

• 如果 $b_i \in S$，那么它之前已经讲过，我们可以把它放到队头（因为上一轮结束后我们可以任意移动它），所以这一步总是可行。
• 如果 $b_i \notin S$（第一次出现），那么它必须在当前未讲过的人中位于队头。
  队头 = 未讲过的人中 $p$ 最小的那个。
  因此必须满足：$$p[b_i] = \min\{p[u] \mid u \notin S\}$$ 即 $b_i$ 必须是当前未出现的人中初始位置最靠前的那个。

---

算法实现（Easy Version）

我们不需要显式维护集合 $S$，只需要一个指针 ptr 指向初始队伍中下一个尚未出现的人。

初始化：

$$ptr = 1$$

含义：当前未出现的人中 $p$ 最小的是 $a[ptr]$。

遍历 $i = 1 \dots m$：

• 如果 $b_i$ 已经出现过（可以用一个 bool used[] 标记），直接继续。
• 否则（第一次出现）：
  • 如果 $b_i \neq a[ptr]$，则失败 → 输出 "TIDAK"。
  • 如果 $b_i = a[ptr]$，则：
    • 标记 $b_i$ 为已用过。
    • $ptr \leftarrow ptr + 1$（下一个未出现的人）。

如果整个遍历没有失败，输出 "YA"。

---

正确性证明

必要性：
若 $b_i$ 第一次出现且不等于 $a[ptr]$，则 $a[ptr]$ 是未出现的人中 $p$ 最小的，他一定在队头。
而 $b_i$ 在后面，无法在不移动未出现的人的情况下到队头 → 不可能。

充分性：
若每次第一次出现的 $b_i$ 都等于 $a[ptr]$，我们可以这样构造移动：

• 对于已出现过的 $b_i$，我们总能在上一轮结束后把它放到队头（因为上一轮结束时的队头是 $b_{i-1}$，我们可以把 $b_i$ 放到它前面）。
• 对于第一次出现的 $b_i$，它本来就是队头（因为 $a[ptr]$ 在队头），讲完后可以把它插到任意位置，不影响未出现的人的相对顺序。

因此条件充分。

---

复杂度

• 时间：$O(n + m)$
• 空间：$O(n)$

---

代码框架（C++）

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m, q;
    cin >> n >> m >> q; // q = 0
    vector<int> a(n), b(m);
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < m; i++) cin >> b[i];

    vector<bool> used(n + 1, false);
    int ptr = 0; // 指向 a[ptr] 是下一个未出现的人
    bool ok = true;

    for (int i = 0; i < m; i++) {
        if (used[b[i]]) {
            continue;
        }
        // 第一次出现
        if (b[i] != a[ptr]) {
            ok = false;
            break;
        }
        used[b[i]] = true;
        ptr++;
    }

    cout << (ok ? "YA" : "TIDAK") << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

---

示例验证

例1

n=4, m=2, a=1 2 3 4, b=1 1
ptr=0, a[0]=1
b0=1, 第一次出现且等于1 → used[1]=true, ptr=1
b1=1, 已出现 → 继续
结束，输出 YA

例2

n=3, m=6, a=1 2 3, b=1 1 2 3 3 2
ptr=0, a[0]=1
b0=1 第一次出现 → ok, ptr=1
b1=1 已出现
b2=2 第一次出现, a[1]=2 → ok, ptr=2
b3=3 第一次出现, a[2]=3 → ok, ptr=3
b4=3 已出现
b5=2 已出现
输出 YA

例3

n=4, m=6, a=3 1 4 2, b=3 1 1 2 3 4
ptr=0, a[0]=3
b0=3 第一次出现, a[0]=3 → ok, ptr=1
b1=1 第一次出现, a[1]=1 → ok, ptr=2
b2=1 已出现
b3=2 第一次出现, a[2]=4 → 2≠4 → 失败 TIDAK

与样例输出一致。