VP*20；
感觉之前有过类似思路的题，，，再记录一下
给出一个仅含有a和b的字符串，问给出任意一个区间，问最少修改几个字母，使得该区间内不存在任何一个子串是回文串。
思路： 因为只是a，b，c三个字母的组合，那么不存在回文的情况也就很少了，仅有abc，acb，cab，cba，bca，bac六中情况，那么直接预处理字符串中的子串是否都是这六个中的即可，每次询问就只需要遍历六个可能情况，找到改变最少的情况即可，注意处理字母的数量是使用前缀和处理的，且若不想出现回文串，那一个字符串内都应该是六种组合中的同一种！
#include <bits/stdc++.h>
#pragma GCC optimize(2)
template <typename T>
inline void read(T &x) {
x = 0;
int f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
while (isdigit(ch)) {
x = x * 10 + ch - '0', ch = getchar();
}
x *= f;
}
template <typename T>
void write(T x) {
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
write(x / 10);
putchar(x % 10 + '0');
}
#define INF 0x3f3f3f3f
typedef long long ll;
const double PI = acos(-1);
const double eps = 1e-6;
const int mod = 1e9 + 7;
const int N = 2e5 + 5;
int t, n, m;
int f[10][N];
std::string s;
std::vector<std::string>vec = {"abc", "acb", "bac", "bca", "cab", "cba"};
int main() {
// freopen("test.in","r",stdin);
// freopen("output.in", "w", stdout);
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> n >> m;
std::cin >> s;
for (int i = 0; i < 6; i++) {
if (s[0] == vec[i][0])
f[i][0] = 0;
else
f[i][0] = 1;
for (int j = 1; j < n; j++) {
if (s[j] == vec[i][j % 3])
f[i][j] = f[i][j - 1];
else
f[i][j] = f[i][j - 1] + 1;
}
}
while (m--) {
int l, r;
std::cin >> l >> r;
l--, r--;
int min = INF;
for (int i = 0; i < 6; i++) {
min = std::min(f[i][r] - f[i][l - 1], min);
}
std::cout << min << '\n';
}
return 0;
}
若有错误请指教，谢谢！
sroorz
