【ABC157】E - Simple String Queries

atcoder.jp

解法

クエリの内容的にセグメント木を使いたくなる。
セグ木には、区間の文字がそれぞれ何個ずつあるかという情報を乗せたい。

文字列に関する問題でよくあるのは、英小文字が26文字しかないことを利用するパターンだ。
この問題も利用できる。

具体的には、区間をマージするときに26回ループを回して、それぞれの文字が何個ずつあるかを足し合わせれば良い。
これで更新&探索をそれぞれO(logN)で行うことができる。
全体計算量はO(QlogN)になる。

実装

struct SegTree {
    int n; // 葉の数
    vector<vector<int>> node; // 完全2分木

    // 初期化
    SegTree(string S) {
        int sz = S.size();
        n = 1;
        while (n < sz) n *= 2; // 与えられた数列の項数以上の2^n個、葉を作る
        node.resize(n*2-1, vector<int>(26, 0)); // 0で初期化

        for (int i = 0; i < sz; i++) node[n-1+i][S[i]-'a']++;
        for (int i = n-2; i >= 0; i--) {
            REP (j, 26) node[i][j] = node[i*2+1][j] + node[i*2+2][j];
        }
    }

    // 更新
    void update(int i, int co, int cn) {
        i += n-1; // 葉はn-1から始まる
        node[i][co]--;
        node[i][cn]++;
        while (i > 0) { // 親に更新を伝搬
            i = (i-1)/2; // 親の添字
            node[i][co]--;
            node[i][cn]++;
        }
    }

    // クエリ処理
    // [s, t)を探す
    // 再帰的に探索するために呼び出す側を別の関数に
    void find(int s, int t, set<int> &ans) { find_query(s, t, 0, n, 0, ans); }

    void find_query(int s, int t, int l, int r, int n, set<int> &ans) {
        if (r <= s || t <= l) return; // 範囲外なら終了
        // [s, t)が[l, r)を内包しているとき
        else if (s <= l && t >= r) {
            REP (i, 26) if (node[n][i]) ans.insert(i);
        } else {
            // (r+l)/2は区間の中心, 区間の中心を左端にするか、右端にするかで分岐する
            find_query(s, t, l, (r+l)/2, n*2+1, ans); // 左下の子を探索
            find_query(s, t, (r+l)/2, r, n*2+2, ans);  // 右下の子を探索
        }
    }

};

int main(){
    ll N, Q;
    string S;
    cin >> N >> S >> Q;

     // セグ木
    auto segtree = SegTree(S);
    REP (i, Q) {
        int q;
        cin >> q;
        if (q == 1) {
            int j;
            char c;
            cin >> j >> c;
            // 更新
            segtree.update(j-1, S[j-1] - 'a', c - 'a');
            S[j-1] = c;
        } else {
            int l, r;
            cin >> l >> r;
            set<int> ans;
             // 探索
            segtree.find(l-1, r, ans);

            cout << ans.size() << endl;
        }
    }

    return 0;
}