CF1555D Say No to Palindromes

CF1555D
https://codeforces.com/problemset/problem/1555/D
阿里巴巴控股集团笔试第三题改了下修改区间在线查询，原题是个比较简单的贪心，想清楚只有六种情况就可以了。

Let’s call the string beautiful if it does not contain a substring of length at least 2, which is a palindrome. Recall that a palindrome is a string that reads the same way from the first character to the last and from the last character to the first. For example, the strings a, bab, acca, bcabcbacb are palindromes, but the strings ab, abbbaa, cccb are not.

Let’s define cost of a string as the minimum number of operations so that the string becomes beautiful, if in one operation it is allowed to change any character of the string to one of the first 3 letters of the Latin alphabet (in lowercase).

You are given a string s of length n, each character of the string is one of the first 3 letters of the Latin alphabet (in lowercase).

You have to answer m queries — calculate the cost of the substring of the string s from li-th to ri-th position, inclusive.

Input

The first line contains two integers n and m (1≤n,m≤2⋅105) — the length of the string s and the number of queries.

The second line contains the string s, it consists of n characters, each character one of the first 3 Latin letters.

The following m lines contain two integers li and ri (1≤li≤ri≤n) — parameters of the i-th query.

Output

For each query, print a single integer — the cost of the substring of the string s from li-th to ri-th position, inclusive.

条件是不能出现长度大于等于2的回文串，且只有abc三个字母。
beautiful串其实是固定的，aa bb cc这种组合肯定不能出现，如果两位为ab那第三位只能为c，后续的字母都递推为唯一的结果，字符串开头两位ab ba ac ca bc cb六种情况，符合条件的只有六个串而已，直接枚举。

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int pre[7][N];
void solve(string s, string t, int num, int n)
{
	for (int i = 0; i < n; i++) {
		pre[num][i + 1] += pre[num][i];
		if (i % 3 == 0 && s[i] != t[0]) {
			pre[num][i + 1]++;
		}
		if (i % 3 == 1 && s[i] != t[1]) {
			pre[num][i + 1]++;
		}
		if (i % 3 == 2 && s[i] != t[2]) {
			pre[num][i + 1]++;
		}
	}
}

int main()
{
	int n, m;
	cin >> n >> m;
	string s;
	cin >> s;
	solve(s, "abc", 1, n);
	solve(s, "acb", 2, n);
	solve(s, "bac", 3, n);
	solve(s, "bca", 4, n);
	solve(s, "cab", 5, n);
	solve(s, "cba", 6, n);
	while (m--) {
		int l, r;
		cin >> l >> r;
		int ans = 1e9 + 10;
		for (int j = 1; j <= 6; j++) {
			ans = min(ans, pre[j][r] - pre[j][l - 1]);
		}
		cout << ans << endl;
	}
	
	return 0;
}