C2. 调整演示（困难版本）详细题解

1. 问题理解

我们有 $n$ 个成员，初始队伍顺序由排列 $a_1, a_2, \dots, a_n$ 给出。有 $m$ 张幻灯片，要求第 $i$ 张幻灯片由成员 $b_i$ 讲解。

操作规则：

• 每张幻灯片由当前队伍最前面的成员讲解
• 讲解完毕后，可以将该成员移动到队伍中的任意位置（其余成员相对顺序不变）

需要判断是否存在一种操作方式满足所有要求。

本题中 $q$ 可以很大，我们需要在每次修改 $b$ 中的某个值后快速判断。

---

2. 关键转化：重标号

首先，我们按照初始队伍顺序重新编号成员：

令初始队伍中第 $i$ 个位置的成员编号为 $i$。也就是说：

• 原数组 $a$ 中的 $a_1$ 变成成员 $1$
• 原数组 $a$ 中的 $a_2$ 变成成员 $2$
• ...
• 原数组 $a$ 中的 $a_n$ 变成成员 $n$

同时，将数组 $b$ 中的所有成员编号按照这个映射进行转换。

结果：初始队伍顺序变成了 $[1, 2, 3, \dots, n]$。

这样做的好处是简化了问题：我们不再需要关心 $a$ 的具体值，只需要知道成员编号与初始位置的关系。

---

3. 无更新时的判断算法

让我们先考虑 $q = 0$ 的情况（简单版本）。

按顺序处理 $b_1, b_2, \dots, b_m$，同时维护：

• current：当前队伍最前面的成员（初始为 $1$）
• pending：一个集合，存放已经讲解过但还未确定最终位置的成员

处理规则：

当处理到 $b_i$ 时：

情况1：$b_i = \text{current}$

• 让该成员讲解当前幻灯片
• 讲解完毕后，他成为 pending 成员（因为我们可以稍后把他放回队伍前面）
• 更新 current 为队伍中的下一个成员（即不在 pending 中的最小成员）

情况2：$b_i$ 在 pending 中

• 我们可以通过之前移动该成员时设定合适的目标位置，使得现在他正好在队伍最前面
• 讲解完毕后，他仍然是一个 pending 成员
• current 保持不变

情况3：否则

• 无法让 $b_i$ 讲解当前幻灯片 → 输出 "TIDAK"

算法正确性：

• 情况1：当前成员正好在最前面，直接讲解
• 情况2：该成员之前被移到了后面，但我们可以安排他在此时回到最前面
• 情况3：该成员既不在最前面，也没有被移动过，无法出现

---

4. 重要观察

从上述算法中，我们可以发现几个关键性质：

性质1：一旦一个成员成为 pending，他就永远在 pending 中。

性质2：一个成员 $x$ 第一次出现在 $b$ 中的时候，就是他成为 pending 的时刻。

性质3：成员成为 pending 的顺序必须与初始队伍顺序一致。

为什么性质3成立？

因为初始队伍顺序是 $[1, 2, 3, \dots, n]$。成员 $1$ 在队伍最前面，所以如果他第一次出现时不是第一个，那么他之前一定已经被移到了后面，但那时他还没有出现过，矛盾。因此成员 $1$ 必须是第一个成为 pending 的成员。

当成员 $1$ 成为 pending 后，队伍最前面变成了成员 $2$。类似地，成员 $2$ 必须是下一个成为 pending 的成员，否则成员 $2$ 第一次出现时，成员 $1$ 可能还在前面（如果还没有被移走），或者成员 $3$ 跑到了前面（不可能，因为成员 $3$ 在成员 $2$ 后面）。

因此，成员 $x$ 必须在成员 $x+1$ 第一次出现之前成为 pending。

---

5. 转化为条件判断

基于上述观察，我们定义：

$\text{first}[x] = \begin{cases} \text{最小的 } i \text{ 使得 } b_i = x, & \text{如果 } x \text{ 在 } b \text{ 中出现} \\ m+1, & \text{如果 } x \text{ 在 } b \text{ 中未出现} \end{cases}$

定理：幻灯片演示是“好的” $\iff$ $\text{first}[1] \le \text{first}[2] \le \dots \le \text{first}[n]$

证明：

必要性：

• 成员 $x$ 必须在成员 $x+1$ 第一次出现之前成为 pending
• 成员 $x$ 成为 pending 的时刻就是 $\text{first}[x]$
• 成员 $x+1$ 第一次出现的时刻是 $\text{first}[x+1]$
• 因此必须有 $\text{first}[x] \le \text{first}[x+1]$

充分性：

• 如果 $\text{first}[1] \le \text{first}[2] \le \dots \le \text{first}[n]$，我们可以构造操作：
  • 当遇到成员 $x$ 第一次出现时，如果当前最前面不是 $x$，说明 $x$ 已经在 pending 中
  • 我们可以通过之前移动 $x$ 时的位置选择，让 $x$ 在这个时刻出现在最前面
  • 这样所有要求都可以满足

因此，问题转化为维护 $\text{first}$ 数组的非递减性。

---

6. 处理更新操作

现在考虑有 $q$ 次更新（困难版本）。每次更新将 $b_{s_i}$ 改为 $t_i$。

我们需要在每次更新后快速判断 $\text{first}[1] \le \text{first}[2] \le \dots \le \text{first}[n]$ 是否成立。

6.1 数据结构设计

对于每个成员 $x$（$1 \le x \le n$），我们维护一个有序集合 $S_x$，存储 $x$ 在 $b$ 中的所有出现位置。

那么： $\text{first}[x] = \begin{cases} \min(S_x), & \text{如果 } S_x \text{ 非空} \\ m+1, & \text{如果 } S_x \text{ 为空} \end{cases}$

6.2 维护非递减性

我们维护一个变量 $c$，表示满足 $\text{first}[x] \le \text{first}[x+1]$ 的 $x$ 的数量（$1 \le x \le n-1$）。

初始化：

• 遍历 $b$ 数组，将每个位置 $i$ 插入到 $S_{b_i}$ 中
• 计算每个 $\text{first}[x]$ 的值
• 计算 $c$ 的初始值

更新操作（将 $b_s$ 从 $old$ 改为 $new$）：

1. 从 $S_{old}$ 中删除 $s$：

   • 更新前的 $\text{first}[old]$ 记为 $f_{old}^{old}$
   • 删除后，新的 $\text{first}[old]$ 记为 $f_{old}^{new}$
   • 如果 $f_{old}^{old} \ne f_{old}^{new}$，则需要更新与 $old$ 相邻的比较

2. 向 $S_{new}$ 中插入 $s$：

   • 更新前的 $\text{first}[new]$ 记为 $f_{new}^{old}$
   • 插入后，新的 $\text{first}[new]$ 记为 $f_{new}^{new}$
   • 如果 $f_{new}^{old} \ne f_{new}^{new}$，则需要更新与 $new$ 相邻的比较

3. 更新 $c$：

   • 对于每个受影响的 $x$（$old-1, old, old+1, new-1, new, new+1$ 范围内的 $x$），先减去原来的比较结果（如果成立）
   • 更新 $\text{first}$ 值
   • 再加上新的比较结果（如果成立）

注意需要处理边界情况（$x = 1$ 或 $x = n$ 时只有一个相邻比较）。

6.3 判断结果

每次更新后：

• 如果 $c = n-1$，则 $\text{first}$ 数组非递减 → 输出 "YA"
• 否则输出 "TIDAK"

---

7. 时间复杂度分析

• 预处理：$O(n + m \log m)$（插入所有 $b$ 中的元素到集合）
• 每次更新：$O(\log m)$（删除、插入、更新 $\text{first}$ 和 $c$）
• 总复杂度：$O((n + m + q) \log m)$

由于 $n, m, q$ 的总和不超过 $2 \times 10^5$（所有测试用例），这个复杂度完全可以接受。

---

8. 实现细节

8.1 集合的选择

• 可以使用 C++ 的 std::set 或 std::multiset
• 由于每个值可能出现多次，使用 std::set 存储所有位置

8.2 获取最小值

• 对于 std::set，最小值是 *S[x].begin()
• 空集合时返回 $m+1$

8.3 更新 $c$ 的辅助函数

auto update = [&](int x, int delta) {
    // 更新与 x 和 x+1 的比较
    if (1 <= x && x < n) {
        // 比较 first[x] 和 first[x+1]
        if (first[x] <= first[x+1]) c += delta;
    }
};

---

9. 完整算法流程

1. 读入 t 个测试用例
2. 对每个测试用例：
   a. 读入 n, m, q
   b. 读入数组 a，并建立映射（成员重编号）
   c. 读入数组 b，应用映射转换
   d. 初始化：为每个成员 x 建立空集合 S[x]
   e. 遍历 b，将位置 i 插入 S[b_i]
   f. 计算 first[x]（S[x] 的最小值或 m+1）
   g. 计算初始 c
   h. 输出初始状态的结果
   i. 对于每次更新：
      - 读取 s, t
      - 将 t 映射为新编号
      - old = b[s]
      - 从 S[old] 删除 s，更新 first[old] 和 c
      - 向 S[t] 插入 s，更新 first[t] 和 c
      - b[s] = t
      - 输出当前状态的结果

---

10. 示例验证

以题目中的第二个测试用例为例（经过重标号后）：

• $n = 3, m = 6, b = [1, 1, 2, 3, 3, 2]$
• $\text{first}[1] = 1, \text{first}[2] = 3, \text{first}[3] = 4$
• $1 \le 3 \le 4$ 成立 → "YA"

第三个测试用例：

• $b = [3, 1, 1, 2, 3, 4]$
• $\text{first}[1] = 2, \text{first}[2] = 4, \text{first}[3] = 1, \text{first}[4] = 6$
• $2 \le 4$ 成立，但 $4 \le 1$ 不成立 → "TIDAK"

与题目输出一致。

---

11. 总结

本题的核心思想是：

1. 重标号简化初始顺序
2. 发现等价条件：$\text{first}[1] \le \text{first}[2] \le \dots \le \text{first}[n]$
3. 使用有序集合维护每个值的出现位置
4. 维护相邻比较计数 $c$，实现 $O(\log m)$ 的更新

这样，我们就得到了一个高效的动态维护算法，能够处理困难版本中 $q$ 很大的情况。