AT_abc314_c [ABC314C] Rotate Colored Subsequence

题目描述

给定一个由小写英文字母组成、长度为 $N$ 的字符串 $S$。$S$ 的每个字符都被涂上了 $M$ 种颜色中的一种，分别为颜色 $1$、颜色 $2$、$\ldots$、颜色 $M$。对于 $i = 1, 2, \ldots, N$，$S$ 的第 $i$ 个字符被涂上了颜色 $C_i$。

对于每个 $i = 1, 2, \ldots, M$，按此顺序进行如下操作：

• 将 $S$ 中所有被颜色 $i$ 涂色的字符部分，向右循环平移 $1$ 位。也就是说，假设 $S$ 中被颜色 $i$ 涂色的字符的位置依次为 $p_1, p_2, p_3, \ldots, p_k$，则将 $S$ 的第 $p_1, p_2, p_3, \ldots, p_k$ 个字符，分别同时替换为 $S$ 的第 $p_k, p_1, p_2, \ldots, p_{k-1}$ 个字符。

请输出经过上述所有操作后的最终字符串 $S$。

保证对于所有颜色 $1 \leq i \leq M$，都至少有一个字符被该颜色涂色。

输入格式

输入按以下格式从标准输入读入。

$N$ $M$ $S$ $C_1$ $C_2$ $\ldots$ $C_N$

输出格式

请输出答案。

输入输出样例 #1

输入 #1

8 3
apzbqrcs
1 2 3 1 2 2 1 2

输出 #1

cszapqbr

输入输出样例 #2

输入 #2

2 1
aa
1 1

输出 #2

aa

说明/提示

限制条件

• $1 \leq M \leq N \leq 2 \times 10^5$
• $1 \leq C_i \leq M$
• $N, M, C_i$ 均为整数
• $S$ 是由小写英文字母组成的长度为 $N$ 的字符串
• 对于任意整数 $1 \leq i \leq M$，都存在某个整数 $1 \leq j \leq N$ 使得 $C_j = i$

样例解释 1

初始时，$S =$ apzbqrcs。

• 对于 $i = 1$ 的操作，将 $S$ 的第 $1, 4, 7$ 个字符组成的部分向右循环平移 $1$ 位。结果为 $S =$ cpzaqrbs。
• 对于 $i = 2$ 的操作，将 $S$ 的第 $2, 5, 6, 8$ 个字符组成的部分向右循环平移 $1$ 位。结果为 $S =$ cszapqbr。
• 对于 $i = 3$ 的操作，将 $S$ 的第 $3$ 个字符组成的部分向右循环平移 $1$ 位。操作前后 $S$ 不变，仍为 cszapqbr。

因此，最终的 $S$ 为 cszapqbr，输出该字符串。

由 ChatGPT 4.1 翻译