CF1555D 题解

songtaoran · 2025-03-26 16:22:10 · 题解

注意到当且仅当一个字符串为长度为 3 的循环节构成的情况下才能满足条件，例如 abcabcab。
所以考虑维护前缀和，每个前缀和分别代表当循环节为 abc 时需要改多少个字母，当循环节为 acb 时需要改多少个字母，当循环节为 bac 时需要改多少个字母，当循环节为 bca 时需要改多少个字母，当循环节为 cab 时需要改多少个字母，当循环节为 cba 时需要改多少个字母。

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, l, r, sum[200010][10];
string s;
ll query(ll op, ll x, ll y){
    return sum[y][op] - sum[x - 1][op];
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m >> s, s = '_' + s;
    for(ll i = 1; i <= n; i++){
        sum[i][1] = sum[i - 1][1] + ((i % 3 == 1 && s[i] != 'a') || (i % 3 == 2 && s[i] != 'b') || (i % 3 == 0 && s[i] != 'c'));
        sum[i][2] = sum[i - 1][2] + ((i % 3 == 1 && s[i] != 'a') || (i % 3 == 2 && s[i] != 'c') || (i % 3 == 0 && s[i] != 'b'));
        sum[i][3] = sum[i - 1][3] + ((i % 3 == 1 && s[i] != 'b') || (i % 3 == 2 && s[i] != 'a') || (i % 3 == 0 && s[i] != 'c'));
        sum[i][4] = sum[i - 1][4] + ((i % 3 == 1 && s[i] != 'b') || (i % 3 == 2 && s[i] != 'c') || (i % 3 == 0 && s[i] != 'a'));
        sum[i][5] = sum[i - 1][5] + ((i % 3 == 1 && s[i] != 'c') || (i % 3 == 2 && s[i] != 'a') || (i % 3 == 0 && s[i] != 'b'));
        sum[i][6] = sum[i - 1][6] + ((i % 3 == 1 && s[i] != 'c') || (i % 3 == 2 && s[i] != 'b') || (i % 3 == 0 && s[i] != 'a')); 
    }
    while(m--){
        cin >> l >> r;
        cout << min({query(1, l, r), query(2, l, r), query(3, l, r), query(4, l, r), query(5, l, r), query(6, l, r)}) << endl;
    }
    return 0;
}