agc059 A – My Last ABC Problem

题意：

排列可视为映射

给定一个 A,B,C 字符串 str。每次操作选择一个子串并对其应用一个 ABC 的排列对应的映射。每次询问至少要多少次操作才能让子串 str[l..r] 中的全部字符相同

\(|S|\le 1e5, q\le 1e5\)

思路：

放一份完美题解

https://www.cnblogs.com/Appleblue17/p/17019258.html

const int N = 1e5 + 5;
char str[N];
int n, q, s[N];
void sol() {
    cin >> n >> q >> (str + 1);
    for(int i = 1; i <= n; i++)
        s[i] = s[i - 1] + (str[i] != str[i - 1]);
    while(q--) {
        int l, r; cin >> l >> r;
        cout << (s[r] - s[l - 1] + (str[l] == str[l - 1]) //这里不考虑会少算
            + (str[l] != str[r])) / 2 << '\n';
    }
}