C. 更新查询 – 详细题解

问题重述

给定初始字符串 $s$（长度 $n$），一个索引数组 $\text{ind}$（长度 $m$）和一个字符数组 $c$（长度 $m$）。每次操作选择 $\text{ind}$ 中的一个位置 $p$ 和 $c$ 中的一个字符 $ch$，将 $s_p$ 更新为 $ch$。所有操作按某种顺序依次执行。我们可以任意重排 $\text{ind}$ 和 $c$ 的顺序（即重新排列操作顺序和分配字符）。求经过 $m$ 次操作后能得到的最小字典序的 $s$。

核心观察

• 一个位置可能被多次更新。最终该位置的值由最后一次（即该位置上的最后一次操作）的字符决定。之前的更新会被覆盖，因此不影响结果。
• 对于每个位置 $i$（$1 \le i \le n$），记 $f_i$ 为 $\text{ind}$ 中 $i$ 出现的次数。若 $f_i = 0$，则该位置永远不会被修改，最终字符就是 $s_i$ 本身。
• 若 $f_i > 0$，则我们将会对该位置执行 $f_i$ 次操作，其中最后一次操作决定最终字符。前 $f_i-1$ 次操作可以任意使用 $c$ 中的字符（它们会被覆盖，不影响结果），但会消耗掉 $c$ 中的某些字母。
• 目标：使最终的字符串 $s$ 字典序最小。字典序的比较是从左到右逐字符进行的，因此我们应优先让靠前的位置尽可能小。

贪心策略

从左到右依次处理每个位置 $i$：

• 如果 $f_i = 0$，则 $s_i$ 不变。
• 如果 $f_i > 0$：
  • 我们需要为这个位置选择一个最终字符。为了字典序最小，我们应从 $c$ 中剩余的所有字母里选择最小的那个作为该位置的最终值。
  • 选择后，将该字母从 $c$ 的计数中移除（表示已用于最后一次操作）。
  • 该位置还需要 $f_i - 1$ 个额外的操作（它们会被覆盖）。这些操作可以使用 $c$ 中任意剩余的字母，因为无论用什么都对最终结果没有影响。为了不浪费小字母（后面可能还需要），我们应该用最大的字母来填充这些额外的操作。具体做法是：从 $z$ 向下遍历，尽可能多地取大字母，直到凑够 $f_i - 1$ 个。
• 处理完所有位置后，$c$ 中可能还有剩余字母，但所有操作已经用完？注意 $m$ 等于所有 $f_i$ 之和，因此 $c$ 中的字母总数正好等于 $\sum f_i$，所以最后计数会归零。

正确性说明

• 字典序最小：由于我们是从左到右处理，每个位置都使用了当前可用的最小字母作为最终值，保证了前面位置尽可能小。同时，我们用大字母填充多余的操作，保留了小字母给后面的位置，从而不会破坏后续的字典序优势。
• 可行性：因为总操作数等于 $c$ 中字母总数，且每个位置 $f_i>0$ 时我们分配了 $1$ 个最终字母和 $f_i-1$ 个填充字母，总共 $f_i$ 个。整个过程消耗完所有字母，因此是可行的。

算法步骤

1. 统计 $\text{ind}$ 中每个位置的出现次数 $f_i$（$1 \le i \le n$）。
2. 统计 $c$ 中每个字母的频率 $\text{cnt}[0..25]$。
3. 新建一个空字符串 $\text{ans}$。
4. 对于 $i = 1$ 到 $n$：
   • 如果 $f_i = 0$：将 $s_i$ 追加到 $\text{ans}$。
   • 否则：
     • 找到最小的字母 $ch$（从 'a' 到 'z'）使得 $\text{cnt}[ch] > 0$，将 $ch$ 追加到 $\text{ans}$，并将 $\text{cnt}[ch]$ 减 $1$。
     • 还需要 $f_i - 1$ 个字母来填充。从 $z$ 向下到 $a$，每次尽量取最多，直到取够 $f_i - 1$ 个。（实际上，我们不需要显式记录这些填充操作，只需将 $\text{cnt}$ 中的对应字母减少即可，因为填充字母不参与最终结果。）
5. 输出 $\text{ans}$。

复杂度

• 统计频率：$O(n + m)$。
• 处理每个位置：对于每个 $f_i > 0$ 的位置，寻找最小字母需要 $O(26)$，填充大字母也需要 $O(26)$。由于 $n$ 和 $m$ 的总和不超过 $2\times 10^5$，总复杂度 $O((n+m)\cdot 26)$，完全可以接受。

示例验证

以样例2为例：$s=\text{"meow"}$，$n=4$，$\text{ind}=[1,2,1,4]$，$c=\text{"zcwz"}$。
统计 $f$：位置1出现2次，位置2出现1次，位置3出现0次，位置4出现1次。
$c$ 字母频率：z:2, c:1, w:1。
从左到右：

• $i=1$ ($f=2$)：取最小字母 c → ans="c"，cnt[c]=0。还需1个填充，取最大字母 z，cnt[z]=1。
• $i=2$ ($f=1$)：取最小字母 w → ans="cw"，cnt[w]=0。
• $i=3$ ($f=0$)：原字符 o → ans="cwo"。
• $i=4$ ($f=1$)：取最小字母 z → ans="cw o z" = "cwoz"。结果与输出一致。

总结

本题的核心是理解“最后一次操作决定最终值”以及“多余的更新可以用任意字符填充”。通过贪心地为每个被更新的位置分配当前最小的字母作为最终值，并用最大的字母填充多余操作，即可得到字典序最小的结果。