[AtCoder] ABC 157 E – Simple String Queries

2020年3月5日2020年12月15日

問題

方針

区間和のような情報が必要なので、セグメント木を使います。\( 1 \) 文字目から \( i \) 文字目までの文字の種類を \( 2 \) 進数を用いて表現します。これは、\( 26 \) ビットで表現できます。これをセグメント木を使って管理します。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int bit_count(int n) {
    int ret = 0;
    for (int i = 0; i < 26; i++) {
        if (n & (1<<i)) ret++;
    }
    return ret;
}

class SegmentTree {
private:
    int n;
    vector<ll> node, v;
    ll INF = (1ll << 31) - 1;
public:
    SegmentTree(int N, string S) {
        n = 1;
        while (n < N) n *= 2;
        node.resize(2 * n - 1, 0);
        v.resize(N);
        for (int i = 0; i < N; i++) v[i] = S[i] - 'a';
        for (int i = 0; i < N; i++) node[i + n - 1] = 1<<v[i];
        for (int i = n - 2; i >= 0; i--) {
            node[i] = node[2 * i + 1] | node[2 * i + 2];
        }
    }

    void update(int i, int x) {
        node[i + n - 1] -= (1<<v[i]);
        v[i] = x;
        node[i + n - 1] += (1<<x);
        i += (n - 1);
        while (i > 0) {
            i = (i - 1) / 2;
            node[i] = node[2 * i + 1] | node[2 * i + 2];
        }
    }

    int query(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0) r = n;
        if (b <= l || r <= a) return 0;
        if (a <= l && r <= b) return node[k];
        int sum_l = query(a, b, 2 * k + 1, l, (l + r) / 2);
        int sum_r = query(a, b, 2 * k + 2, (l + r) / 2, r);
        return sum_l | sum_r;
    }
};

int main() {
    int N, Q;
    string S;
    cin >> N >> S >> Q;
    vector<int> ans;
    int q, x, y;
    char c;
    SegmentTree st(N, S);
    for (int i = 0; i < Q; i++) {
        cin >> q;
        if (q == 1) {
            cin >> x >> c;
            st.update(x - 1, c - 'a');
        } else {
            cin >> x >> y;
            ans.push_back(st.query(x - 1, y));
        }
    }
    for (int i : ans) {
        cout << bit_count(i) << "\n";
    }
    return 0;
}