CF1555D Say No to Palindromes

我们称一个字符串是美丽的，如果它不包含长度至少为 $2$ 的回文子串。回文串是指从第一个字符到最后一个字符、以及从最后一个字符到第一个字符读起来都相同的字符串。例如，字符串 a、bab、acca、bcabcbacb 是回文串，但 ab、abbbaa、cccb 不是。 我们定义一个字符串的代价为：将该字符串变为美丽字符串所需的最少操作次数，每次操作可以将字符串中的任意一个字符更改为拉丁字母表中前 $3$ 个小写字母之一。 给定一个长度为 $n$ 的字符串 $s$，其中每个字符都是拉丁字母表中前 $3$ 个小写字母之一。 你需要回答 $m$ 个询问——对于每个询问，计算字符串 $s$ 的第 $l_i$ 到第 $r_i$ 个位置（包含两端）组成的子串的代价。

第一行包含两个整数 $n$ 和 $m$（$1 \le n, m \le 2 \cdot 10^5$），分别表示字符串 $s$ 的长度和询问的数量。 第二行包含字符串 $s$，长度为 $n$，每个字符都是拉丁字母表中前 $3$ 个小写字母之一。 接下来的 $m$ 行，每行包含两个整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$），表示第 $i$ 个询问的参数。

对于每个询问，输出一个整数，表示将字符串 $s$ 的第 $l_i$ 到第 $r_i$ 个位置组成的子串变为美丽字符串所需的最小操作次数。

考虑示例测试中的询问： - 第一个询问，子串为 baa，可以通过一次操作变为 bac； - 第二个询问，子串为 baacb，可以通过两次操作变为 cbacb； - 第三个询问，子串为 cb，可以保持不变； - 第四个询问，子串为 aa，可以通过一次操作变为 ba。 由 ChatGPT 4.1 翻译