ABC157-E 解説

E - Simple String Queries

Fenwick Treeを使います。Point AddとRange Sumを高速にできます。 Fenwick Treeを $26$ 本持つと $1$ 文字を変更したり、各文字について、区間にその文字が現れる個数を高速に求めることができたりします。

• type1のクエリについて

Fenwick Treeの更新前の文字の $i$ 番目に $-1$ を足して更新後の文字の $i$ 番目に $1$ を足すとうまく変更できます。

• type2のクエリについて

Fenwick Treeの各文字に対し、$l$ 文字目から $r$ 文字目までの和を求めて、それが正である個数を求めます。

from atcoder.fenwicktree import FenwickTree
N = int(input())
S = list(input())
fw = [FenwickTree(N) for _ in range(26)]
for i in range(N):
    fw[ord(S[i]) - ord('a')].add(i, 1)
for _ in range(int(input())):
    q = input().split()
    if q[0] == '1':
        i = int(q[1]) - 1
        c = q[2]
        fw[ord(S[i]) - ord('a')].add(i, -1)
        fw[ord(c) - ord('a')].add(i, 1)
        S[i] = c
    else:
        l = int(q[1]) - 1
        r = int(q[2]) - 1
        print(sum(fw[i].sum(l, r + 1) > 0 for i in range(26)))

#include <bits/stdc++.h>
#include <atcoder/fenwicktree>
using namespace std;
using namespace atcoder;

int main() {
    int N, Q;
    string S;
    cin >> N >> S >> Q;
    vector<fenwick_tree<int>> fw(26, fenwick_tree<int>(N));
    for (int i = 0; i < N; i++) {
        fw[S[i] - 'a'].add(i, 1);
    }
    while (Q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i;
            char c;
            cin >> i >> c;
            i--;
            fw[S[i] - 'a'].add(i, -1);
            fw[c - 'a'].add(i, 1);
            S[i] = c;
        } else {
            int l, r;
            cin >> l >> r;
            l--; r--;
            int ans = 0;
            for (int i = 0; i < 26; i++) {
                if (fw[i].sum(l, r + 1)) {
                    ans++;
                }
            }
            cout << ans << '\n';
        }
    }
}