题解

思路

美丽字符串不能出现长度为 $2$ 的回文，所以相邻字符必须不同；也不能出现长度为 $3$ 的回文， 所以相距两个位置的字符也必须不同。字母表只有三个字符，因此任意连续三个位置必须恰好是 a、b、c 的一个排列，之后的字符也被唯一确定。

所以所有美丽字符串都是 abc 的六种排列之一无限周期串的子串。一个询问的答案，就是原子串 与这六种周期串在对应位置上的失配数最小值。

做法

枚举 abc 的六种排列。对每种排列预处理前缀失配数：第 $i$ 个字符与该排列的第 $i\bmod3$ 个字符不同时加一。询问 $[l,r]$ 对某个排列的修改次数可由两次前缀相减得到， 对六个结果取最小值。

正确性证明

任何美丽字符串都必须同时满足相邻字符不同和相距两位的字符不同。因此给定前两个不同字符后， 第三个位置只能选择剩余字符，后续每个位置也都被前两位唯一决定，故它必为某个三字符排列的周期串。 反之，六种排列的周期串中相邻和相距两位的字符均不同；更长回文必包含中心处长度为 $2$ 或 $3$ 的回文，所以这些周期串确实美丽。

对固定周期串，失配位置必须修改且修改后即可匹配，故失配数就是变成该周期串的最少操作数。 所有美丽目标都属于六种周期串，取六者最小值即为询问最优代价。

复杂度

预处理时间复杂度为 $O(6n)$，每个询问耗时 $O(6)$，总时间复杂度为 $O(n+m)$， 空间复杂度为 $O(6n)$。