Simple String Queries [AtCoder Beginner Contest 157 E]

https://atcoder.jp/contests/abc157/tasks/abc157_e

前提知識

• セグメントツリー

解説

https://atcoder.jp/contests/abc157/submissions/10472600

何から手を付ければいいか分からなかったかもしれない。
一点更新、区間クエリなので、セグメントツリー的な解法から考えるといいかもしれない。

文字種類の個数を数えるのには、bit演算のorが有用である。
a -> 0, b -> 1, c -> 2, ...のようにマッピングを行い、その文字があれば、対応する下位iビットのフラグを
立てたものを考える。
つまり、aであれば、...0001であるし、bであれば、...0010である。
アルファベットは26文字なので、long longを使えばビット数は足りる。
これのORをとることでビットが立っているものをすべて集めることができるので、
区間の数の種類は、区間のビットのOR和のビットが立っている個数と等しくなっている。

ここまで分かっていれば、後は実装するだけ。
ビットが立っている個数を取得するには__buildin_popcountを使うといい。

int N; string S; int Q;
SegTree<ll, 1 << 19> st;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> S >> Q;
    rep(i, 0, N) st.update(i, 1LL << (S[i] - 'a'));
    rep(_, 0, Q) {
        int t; cin >> t;
        if (t == 1) {
            int i; char c; cin >> i >> c; i--;
            st.update(i, 1LL << (c - 'a'));
        }
        else {
            int l, r; cin >> l >> r; l--;
            ll msk = st.get(l, r);
            int ans = __builtin_popcount(msk);
            printf("%d\n", ans);
        }
    }
}