前言

唉

思路

题面不太会说人话，先把题面的操作转化成人话。

如果把整个 01 串划分成值相同的连续段，由于经过一次变换后 sis_i 只可能变成自己或 si−1s_{i-1}，所以只有每个连续段的左端点可能发生变化。设 i(i≥3)i(i\geq 3) 为某个连续段的左端点，分类讨论 si−2,si−1,si(si−1≠si)s_{i-2},s_{i-1},s_i(s_{i-1}≠s_i) 的取值，发现只有 101,110101,110 两种情况会导致 sis_i 在一次变换后被翻转。

发现这个规律实际分别等价于，对于每个单个的 00，在一次变换后会变成两个 00；对于每段非单个（≥2\geq 2）的 11，在一次变换后会往右扩展一位。

得到人话后我们考虑整个扩展过程需要的最小时间（即题面里的 kk）怎么求。模拟一下前面的过程，考虑最左边的一段长度 ≥2\geq 2 的 11，它往右扩展一段时间后会覆盖右边那段 00 产生一个单个的 00，剩下的过程就是它推着一个 00 往右走，直到这个 00 被推到 nn，最后后缀全都变成 11 为止。设这一段 11 的右端点为 ii，答案即为 n−in-i。若串中存在位置不为 nn 的单个的 00，则答案为 max⁡(n−i,1)\max(n-i,1)。

线段树维护左右 0/10/1 的个数、所有连续 0/10/1 段中最靠左的右端点的值，并记录一个单个 0/10/1（优先记录非端点的，因为端点处的可能被合并）的位置即可。这个信息是支持标记下传、左右合并的。

复杂度 O(nlog⁡n)\mathcal{O}(n\log n)。