官方题解｜统计满足条件的子串个数

题目解析

数据结构（树状数组，线段树，平衡树）；

使用「树状数组」等数据结构，ft[i][j] 维护字符串 $S$ 中字符 $i$ 在前 $j$ 个字符中出现的次数。

使用树状数组，预处理 cnt[i][j] 数组，表示字符串 S 中，以 $i$ 开头，以 $j$ 结尾的子串的个数。

对于每次修改操作，我们考虑删除字符 $S_X$ 对以 $i$ 开头以 $S_X$ 结尾和以 $S_X$ 开头以 $i$ 结尾的子串数量，即 $cnt_{i, S_X}$ 和 $cnt_{S_X, i}$ 的影响。

那么我们直接枚举 $i$：

1. 对于 $cnt_{i, S_X}$，查询前 $X - 1$ 个字符中，字符 $i$ 出现的次数，并将其从 $cnt_{i, S_X}$ 减去。
2. 对于 $cnt_{S_X, i}$，查询第 $X$ 个及以后的字符中，字符 $i$ 出现的次数，并将其从 $cnt_{S_X, i}$ 减去。

同时修改树状数组。

然后将 $S_X$ 修改为字符 $C$，使用与计算删除的影响相同的做法，即可得到修改后对 cnt 数组的影响。

对于每个查询，我们可以以 $\mathrm{O}(1)$ 的时间从 cnt 数组中得到答案。

令 $N$ 为字符串 $S$ 的长度，$M$ 为字符集的大小，整个算法，预处理 cnt 数组的时间复杂度为 $\mathrm{O}(NM\log_2{N})$。处理每个查询的时间复杂度为 $\mathrm{O}(M\log_2{N})$，整个算法时间复杂度为 $\mathrm{O}((N + Q) \times (M\log_2{N})$。

AC代码

#include <bits/stdc++.h>

using i64 = long long;

template<class T>
class FenwickTree {
private: // fenwickTree for interval [0, n)
    int n;
    std::vector<T> data;
public:
    FenwickTree() : FenwickTree(0) {}
    explicit FenwickTree(int n) : n(n), data(n) {}

    void add(int p, T x) {
        assert(0 <= p and p < n);
        p += 1;
        while (p <= n) {
            data[p - 1] += x;
            p += p & -p;
        }
    }

    T sum(int l, int r) {// return sum of [l, r)
        assert(0 <= l and l <= r and r <= n);
        return sum(r) - sum(l);
    }

    T sum(int r) {// return sum of [0, r)
        assert(0 <= r and r <= n);
        T s = 0;
        while (r > 0) {
            s += data[r - 1];
            r -= r & -r;
        }
        return s;
    }
};

int main() {
    std::cin.tie(nullptr)->sync_with_stdio(false);
    int n, q;
    std::cin >> n >> q;
    std::string s; std::cin >> s;
    std::vector<FenwickTree<int>> ft(26, FenwickTree<int>(n));
    for (int i = 0; i < n; ++i)
        ft[s[i] - 'a'].add(i, 1);
    i64 cnt[26][26]{};
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < 26; ++j)
            cnt[s[i] - 'a'][j] += ft[j].sum(i, n);
    while (q--) {
        int t; std::cin >> t;
        if (t == 1) {
            int x; std::cin >> x, --x;
            char c; std::cin >> c;
            for (int i = 0; i < 26; ++i) {
                cnt[i][s[x] - 'a'] -= ft[i].sum(0, x);
                cnt[s[x] - 'a'][i] -= ft[i].sum(x, n);
            }
            ft[s[x] - 'a'].add(x, -1);
            s[x] = c;
            ft[s[x] - 'a'].add(x, +1);
            for (int i = 0; i < 26; ++i) {
                cnt[i][s[x] - 'a'] += ft[i].sum(0, x);
                cnt[s[x] - 'a'][i] += ft[i].sum(x, n);
            }
        }
        else {
            char a, b;
            std::cin >> a >> b;
            std::cout << cnt[a - 'a'][b - 'a'] << '\n';
        }
    }
    return 0;
}