#ABC380C. 移动序列

移动序列

AT_abc380_c [ABC380C] Move Segment

题目描述

\hspace{15pt}给定一个长度为 nn、只包含 ‘0’\texttt{`0'} 和 ‘1’\texttt{`1'} 的字符串 ss。请输出将 ss 中从头开始第 kk 个 ‘1’\texttt{`1'} 的连续块移动到第 k−1k-1 个 ‘1’\texttt{`1'} 的连续块的后面所得的字符串。

\hspace{15pt}保证 ss 中包含至少 kk 个 ‘1’\texttt{`1'} 的连续块。

\hspace{15pt}更为准确的说明如下:

∙ \hspace{23pt}\bullet\,用 sl…rs_{l \dots r} 表示 ss 的第 ll 个字符到第 rr 个字符组成的子串;

∙ \hspace{23pt}\bullet\,称 sl…rs_{l \dots r} 为 ‘1’\texttt{`1'} 的连续块,当且仅当以下三个条件全部满足:

∘ \hspace{38pt}\circ\,对任意的 l≦i≦rl \leqq i \leqq r 都有 si=‘1’s_i = \texttt{`1'};

∘ \hspace{38pt}\circ\,满足 l=1l = 1 或 sl−1=‘0’s_{l-1} = \texttt{`0'};

∘ \hspace{38pt}\circ\,满足 r=nr = n 或 sr+1=‘0’s_{r+1} = \texttt{`0'}。

∙ \hspace{23pt}\bullet\,假设 ss 中所有的 ‘1’\texttt{`1'} 的连续块依次为 $s_{l_1 \dots r_1}, s_{l_2 \dots r_2}, \dots, s_{l_p \dots r_p}$,且 l1<l2<⋯<lpl_1 < l_2 < \dots < l_p。这时,定义长度为 nn 的字符串 tt 为「将 ss 中从头开始第 kk 个 ‘1’\texttt{`1'} 的连续块移动到第 k−1k-1 个 ‘1’\texttt{`1'} 的连续块的后面所得的字符串」,具体如下:

∘ \hspace{38pt}\circ\,当 1≦i≦rk−11 \leqq i \leqq r_{k-1} 时,ti=sit_i = s_i;

∘ \hspace{38pt}\circ\,当 $r_{k-1}+1 \leqq i \leqq r_{k-1}+\left(r_k-l_k\right)+1$ 时,ti=‘1’t_i = \texttt{`1'};

∘ \hspace{38pt}\circ\,当 rk−1+(rk−lk)+2≦i≦rkr_{k-1}+\left(r_k-l_k\right)+2 \leqq i \leqq r_k 时,ti=‘0’t_i = \texttt{`0'};

∘ \hspace{38pt}\circ\,当 rk+1≦i≦nr_k+1 \leqq i \leqq n 时,ti=sit_i = s_i。

输入格式

\hspace{15pt}第一行输入两个整数 $n, k \left(1 \leqq n \leqq 5 \times 10^5;\ 2 \leqq k \leqq n\right)$ 代表字符串的长度与需要移动的 ‘1’\texttt{`1'} 的连续块的编号。

\hspace{15pt}第二行输入一个长度为 nn、只包含 ‘0’\texttt{`0'} 和 ‘1’\texttt{`1'} 的字符串 ss。保证 ss 中包含至少 kk 个 ‘1’\texttt{`1'} 的连续块。

输出格式

\hspace{15pt}在一行上输出一个长度为 nn 的字符串,代表操作结束后得到的字符串。

测试样例

15 3
010011100011001
010011111000001
10 2
1011111111
1111111110

样例 1 解释

\hspace{15pt}样例中的字符串 ss 中有 44 个 ‘1’\texttt{`1'} 的连续块,分别为 s2…2s_{2 \dots 2}、s5…7s_{5 \dots 7}、s11…12s_{11 \dots 12} 和 s15…15s_{15 \dots 15}。将第 33 个连续块 s11…12s_{11 \dots 12} 移动到第 22 个连续块 s5…7s_{5 \dots 7} 的后面,得到 "010011111000001"\texttt{"010011111000001"}。