CF1555D题解

• 分析

  注意到字符集大小很小，那么很容易就会产生回文，那么合法序列的种类就会比较有限。
  思考对于不同长度而言合法序列的种类，显然长度为 \(1\) 时无回文，长度为 \(2\) 只要两个字符不同就无回文。
  尝试扩展到长度为 \(3\) 时的情况，显然 \(s_1 \neq s_2\)，\(s_2 \neq s_3\)。发现 \(s_1 = s_3\) 时会产生形如aba的回文，所以 \(s1 \neq s3\)，那么当长度为 \(3\) 时，需要三个字符互不相同才没有回文。
  继续向下扩展。当长度为 \(4\) 时，有 \(s_4 \neq s_3\)，\(s_4 \neq s_2\)，由于字符集的大小为 \(3\)，那么 \(s_4 = s_1\)，这样一直推到 \(s_6\) 发现 \(s_1 = s_4\)，\(s_2 = s_5\)，\(s_3 = s_6\)，以此类推，对于一个长度为 \(n\) 的合法子串，其一定是由长度为 \(3\) 且 \(3\) 个字符互不相同的循环节循环而成的。

  思考如何求最小修改，对于一个子串，我们要求的就是与之最相似的的合法子串与这个串中不同的字符个数（定义不同的字符个数越小越相似）。
  思考求最相似合法子串的循环节以及循环起点。发现循环起点并不重要，因为错开一位可以看做将第 \(1\) 个字符放到了最后一位。
  思考求循环节，发现循环节一共有 \(3!=6\) 种情况，于是可以枚举循环节，然后求最小的字符个数。

  这样的时间复杂度是 \(\mathcal{O(nm)}\) 的，需要进行优化。
  发现对于同一个循环节，不同的字符个数满足可加性，那么对于每个循环节，预处理出字符串中每个位置的不同字符个数的前缀数组，在每次询问的时候就可以通过减去两个前缀快速求出不同字符个数，将时间复杂度降到 \(\mathcal{O(n + m)}\)，可以通过本题。

• 代码

#include <iostream>
using namespace std;
constexpr int MAXN(1000007);
constexpr int INF(0x3f3f3f3f);
int f[7][MAXN];
string a[7] = {"#", "abc", "acb", "bac", "bca", "cab", "cba"};
string s;
int n, q;
inline void read(int &temp) { cin >> temp; }
inline int calc(int l, int r) {
	read(l), read(r);
	int cnt(INF);
	for (int i(1); i <= 6; ++i)  cnt = min(cnt, f[i][r - 1] - f[i][l - 2]);
	return cnt;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	read(n), read(q);
	cin >> s;
	for (int i(1); i <= 6; ++i)
		for (int j(0); j < (int)s.length(); ++j)  f[i][j] = f[i][j - 1] + (s[j] != a[i][j % 3]);
	for (int i(1), l(0), r(0); i <= q; ++i)  cout << calc(l, r) << endl;
	return 0;
}