P12898 [POI 2019/2020 R2] 牢骚 Marudny Bajtazar

翻译来自于 [LibreOJ](https://loj.ac/p/4847)。

**题目译自 [XXVII Olimpiada Informatyczna – II etap](https://sio2.mimuw.edu.pl/c/oi27-2/dashboard/) [Marudny Bajtazar](https://szkopul.edu.pl/problemset/problem/kvwWom2nxVBqipEfeiMtidn5/statement/)** 圣诞节即将来临，Bajtazar 决定购买新的装饰品来装点自己的家。今年，他想尝试极简风格，计划买一条只有绿色和红色两种颜色的灯链。于是，他前往附近的灯饰店，请店主展示双色灯链。 然而，多年在字节王国从事各种工作的经历，让 Bajtazar 养成了对任何事物（哪怕是最琐碎的）都有自己看法的习惯，而且他从不吝于表达意见（即便没人愿意听）。特别是在时尚和美学方面，他的观念尤为固执，这对那些接待过他的店主来说尤为头疼，因为他们总是要听他抱怨商品哪里不尽如人意。 这次也不例外：Bajtazar 盯着店主展示的灯链看了半天，终于开口说：「总体来说，这条灯链还不错，但整体美感被一个问题破坏了——链条里没有一段连续四个灯泡的片段，颜色依次是红-绿-绿-红。」由于店主没有其他灯链可供选择，他决定更换其中一个灯泡的颜色，以满足这个要求。 Bajtazar 满意地点了点头，但没过多久又说：「现在还差一段颜色为绿-红-绿-绿-红的片段。」店主又换了一个灯泡的颜色。Bajtazar 接着说：「现在看起来很美，但还缺少另一个对颜色搭配很重要的片段。」 虽然 Bajtazar 非常耐心地解释为什么灯链还不完美，但他担心店主更换灯泡颜色的方式过于随意，可能无法快速达到目标。为了更高效地解决问题，他请你帮忙编写一个程序，帮助他快速找到灯链中缺失的、影响他美感的片段。作为第一步，请你为他编写一个程序，计算给定灯链中未出现的最短颜色片段的长度。

输入的第一行包含两个整数 $n$ 和 $m$ $(1 \leq n \leq 100000, 0 \leq m \leq 10000)$，用单个空格分隔，分别表示灯链中灯泡的数量和店主更换颜色的次数。第二行包含一个长度为 $n$ 的字符串，由字符 `0` 和 `1` 组成，表示灯链中各灯泡的颜色（例如 `0` 表示红色，`1` 表示绿色）。 接下来的 $m$ 行描述颜色更换操作，每行包含一个整数 $a_{i}$ $(1 \leq a_{i} \leq n)$，表示店主更换了第 $a_{i}$ 个灯泡的颜色。

输出应包含正好 $m+1$ 行，每行包含一个整数。第 $i$ 行表示在店主完成前 $i-1$ 次更换后，灯链颜色编码字符串中未出现的最短子字符串（由 `0` 和 `1` 组成）的长度。

**样例 1 解释** 在字符串 `001010` 中，未出现的最短子字符串是 `11`，长度为 $2$。更换第六个字符后得到 `001011`，此时长度为 $1$ 和 $2$ 的所有子字符串都已出现，但长度为 $3$ 的子字符串 `110` 未出现。更换第二个字符后得到 `011011`，此时未出现的最短子字符串是 `00`，长度为 $2$。 **附加样例** 1. 该样例满足 $n=5, m=0$，灯链为 `10000`； 2. 该样例满足 $n=500, m=2$，初始灯链为 `000...0`（全为 `0`），更换第一个和最后一个灯泡； 3. 该样例满足 $n=m=10000$，初始灯链为 `1000...0`（开头为 `1`，后面全为 `0`），依次更换所有灯泡。 详细子任务附加限制及分值如下表所示。 | 子任务 | 附加限制 | 分值 | | :---: | :--: | :---: | | $1$ | $n, m \leq 1000$ | $46$ | | $2$ | 无附加限制 | $54$ |