Problem p02763 (python)

Fixed submission:
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)

    if i != len(a) and a[i] == x:
        return i
    raise ValueError

# ポイント
# 文字列update
# 文字種の高速取得

# 文字種の高速取得について考えてみる
# 文字のidxを取得しておいて二分探索することで高速に取得することが可能


N = read_a_int()
S = list(read()[:-1])

from collections import defaultdict
from bisect import bisect_left, bisect_right, insort_left
char_idxs = defaultdict(lambda: [])
for i, s in enumerate(S):
    char_idxs[s].append(i)


def get_syurui(char_idxs, l, r):
    ret = 0
    for v in char_idxs.values():
        l_idx = bisect_left(v, l)
        r_idx = bisect_right(v, r)
        # print(v,l_idx,r_idx)
        if r_idx - l_idx > 0:
            ret += 1
    return ret


Q = read_a_int()
for q in range(Q):
    com, a, b = read().split()
    if int(com) == 2:
        a, b = int(a) - 1, int(b) - 1
        print(get_syurui(char_idxs, a, b))
    else:
        i = int(a) - 1
        if S[i] == b:
            continue
        # i文字目を消す
        tmp = char_idxs[S[i]]  # S[i]を更新しなきゃ
        del char_idxs[S[i]][index(tmp, i)]
        # cのidxに挿入し直す
        insort_left(char_idxs[b], i)
        # S[i]を更新しなきゃ
        S[i] = b

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc157/tasks/abc157_e
# セグメント木
# 各文字をビットに対応させる(セグ木を26本持っても良い)
import sys
read = sys.stdin.readline
from functools import reduce


def read_a_int():
    return int(read())


class SqrtDecomposedList:
    def __init__(self, ls, segfunc, identity_element):
        from math import sqrt
        from copy import copy
        self.f = segfunc  # queryのfunction
        self.ide = identity_element
        self.n = len(ls)
        self.ls = ls.copy()
        self.b = int(sqrt(self.n)) + 1
        self.bucket = [self.ide] * (self.b + 1)
        self._build()

    def _build(self):
        for d in range(self.b):
            self.bucket[d] = reduce(
                self.f, self.ls[(d * self.b):((d + 1) * self.b)], self.ide)
        # for i, v in enumerate(self.ls):
        #     self.bucket[i // self.b] = \
        #         self.f(v, self.bucket[i // self.b])

    def __getitem__(self, idx):
        return self.ls[idx]

    def update(self, i, x):
        '''i番目の要素をxに更新する O(√n)'''
        self.ls[i] = x
        s = i // self.b * self.b
        t = s + self.b
        # print(i, self.b, i // self.b, s, t)
        self.bucket[i // self.b] = reduce(self.f,
                                          self.ls[s:t], self.ide)

    def query(self, l, r):
        '''半開区間[l,r)で指定すること O(√n)'''
        if r - l < 2 * self.b:
            return reduce(self.f, self.ls[l:r])
        l_bucket = (l - 1) // self.b + 1
        r_bucket = r // self.b  # 半開区間なのでこれでいい
        ret = reduce(self.f, self.bucket[l_bucket:r_bucket], self.ide)
        ret = self.f(
            reduce(self.f, self.ls[l:(l_bucket * self.b)], self.ide),
            ret)
        ret = self.f(
            reduce(self.f, self.ls[(r_bucket * self.b):r], self.ide),
            ret)
        return ret


def segfunc(x, y):
    # 処理したい内容
    return x | y


def moji_to_bit(a):
    return 1 << (ord(a) - ord('a'))


def bit_to_sum(n):
    return sum([(n >> i) & 1 for i in range(n.bit_length())])


N = read_a_int()
S = read()[:-1]
S_bit = [moji_to_bit(s) for s in S]

# build segment tree
st = SqrtDecomposedList(S_bit, segfunc, 0)

Q = read_a_int()
for q in range(Q):
    com, a, b = read().split()
    if int(com) == 1:
        i, c = int(a) - 1, b
        st.update(i, moji_to_bit(c))
    else:
        l, r = int(a) - 1, int(b)
        print(bit_to_sum(st.query(l, r)))

Buggy submission (verdict: Runtime Error):
# https://atcoder.jp/contests/abc157/tasks/abc157_e
# セグメント木
# 各文字をビットに対応させる(セグ木を26本持っても良い)
import sys
read = sys.stdin.readline
from functools import reduce

def read_a_int():
    return int(read())


class SqrtDecomposedList:
    def __init__(self, ls, segfunc, identity_element):
        from math import sqrt, floor
        from copy import copy
        self.f = segfunc  # queryのfunction
        self.ide = identity_element
        self.n = len(ls)
        self.ls = ls.copy()
        self.b = floor(sqrt(self.n))
        self.bucket = [self.ide] * self.b
        self._build()

    def _build(self):
        for d in range(self.b):
            self.bucket[d] = reduce(
                self.f, self.ls[(d * self.b):((d + 1) * self.b)], initial=self.ide)
        # for i, v in enumerate(self.ls):
        #     self.bucket[i // self.b] = \
        #         self.f(v, self.bucket[i // self.b])

    def __getitem__(self, idx):
        return self.ls[idx]

    def update(self, i, x):
        '''i番目の要素をxに更新する O(√n)'''
        self.ls[i] = x
        s = i // self.b * self.b
        t = s + self.b
        self.bucket[i // self.b] = reduce(self.f,
                                          self.ls[s:t], initial=self.ide)

    def query(self, l, r):
        '''半開区間[l,r)で指定すること O(√n)'''
        if r - l < 2 * self.b:
            return reduce(self.f, self.ls[l:r])
        l_bucket = (l - 1) // self.b + 1
        r_bucket = r // self.b  # 半開区間なのでこれでいい
        ret = reduce(self.f, self.bucket[l_bucket:r_bucket], initial=self.ide)
        ret = self.f(
            reduce(self.f, self.ls[l:(l_bucket * self.b)], initial=self.ide),
            ret)
        ret = self.f(
            reduce(self.f, self.ls[(r_bucket * self.b):r], initial=self.ide),
            ret)
        return ret


def segfunc(x, y):
    # 処理したい内容
    return x | y


def moji_to_bit(a):
    return 1 << (ord(a) - ord('a'))


def bit_to_sum(n):
    return sum([(n >> i) & 1 for i in range(n.bit_length())])


N = read_a_int()
S = read()[:-1]
S_bit = [moji_to_bit(s) for s in S]

# build segment tree
st = SqrtDecomposedList(S_bit, segfunc, 0)

Q = read_a_int()
for q in range(Q):
    com, a, b = read().split()
    if int(com) == 1:
        i, c = int(a) - 1, b
        st.update(i, moji_to_bit(c))
    else:
        l, r = int(a) - 1, int(b)
        print(bit_to_sum(st.query(l, r)))

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)

    if i != len(a) and a[i] == x:
        return i
    raise ValueError

# ポイント
# 文字列update
# 文字種の高速取得

# 文字種の高速取得について考えてみる
# 文字のidxを取得しておいて二分探索することで高速に取得することが可能


N = read_a_int()
S = read()[:-1]

from collections import defaultdict
from bisect import bisect_left, bisect_right, insort_left
char_idxs = defaultdict(lambda: [])
for i, s in enumerate(S):
    char_idxs[s].append(i)


def get_syurui(char_idxs, l, r):
    ret = 0
    for v in char_idxs.values():
        l_idx = bisect_left(v, l)
        r_idx = bisect_right(v, r)
        # print(v,l_idx,r_idx)
        if r_idx - l_idx > 0:
            ret += 1
    return ret


Q = read_a_int()
for q in range(Q):
    com, a, b = read().split()
    if int(com) == 2:
        a, b = int(a) - 1, int(b) - 1
        print(get_syurui(char_idxs, a, b))
    else:
        i = int(a) - 1
        if S[i] == b:
            continue
        # i文字目を消す
        tmp = char_idxs[S[i]]  # S[i]を更新しなきゃ
        del char_idxs[S[i]][index(tmp, i)]
        # cのidxに挿入し直す
        insort_left(char_idxs[b], i)
        # S[i]を更新しなきゃ
        S[i] = b

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

# ポイント
# 文字列update
# 文字種の高速取得

# 文字種の高速取得について考えてみる
# 文字のidxを取得しておいて二分探索することで高速に取得することが可能


N = read_a_int()
S = read()[:-1]

from collections import defaultdict
from bisect import bisect_left, bisect_right, insort_left
char_idxs = defaultdict(lambda: [])
for i, s in enumerate(S):
    char_idxs[s].append(i)


def get_syurui(char_idxs, l, r):
    ret = 0
    for v in char_idxs.values():
        l_idx = bisect_left(v, l)
        r_idx = bisect_right(v, r)
        # print(v,l_idx,r_idx)
        if r_idx - l_idx > 0:
            ret += 1
    return ret


Q = read_a_int()
for q in range(Q):
    com, a, b = read().split()
    if int(com) == 2:
        a, b = int(a) - 1, int(b) - 1
        print(get_syurui(char_idxs, a, b))
    else:
        i = int(a) - 1
        if S[i] == b:
            continue
        # i文字目を消す
        tmp = char_idxs[S[i]]
        del char_idxs[S[i]][index(tmp, i)]
        # cのidxに挿入し直す
        insort_left(char_idxs[b], i)

Buggy submission (verdict: Runtime Error):
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_a_int():
    return int(read())


def read_matrix(H):
    '''
    H is number of rows
    '''
    return [list(map(int, read().split())) for _ in range(H)]


def read_map(H):
    '''
    H is number of rows
    文字列で与えられた盤面を読み取る用
    '''
    return [read()[:-1] for _ in range(H)]


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


def read_col(H, n_cols):
    '''
    H is number of rows
    n_cols is number of cols

    A列、B列が与えられるようなとき
    '''
    ret = [[] for _ in range(n_cols)]
    for _ in range(H):
        tmp = list(map(int, read().split()))
        for col in range(n_cols):
            ret[col].append(tmp[col])

    return ret


def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

# ポイント
# 文字列update
# 文字種の高速取得

# 文字種の高速取得について考えてみる
# 文字のidxを取得しておいて二分探索することで高速に取得することが可能


N = read_a_int()
S = read()[:-1]

from collections import defaultdict
from bisect import bisect_left, bisect_right, insort_left
char_idxs = defaultdict(lambda: [])
for i, s in enumerate(S):
    char_idxs[s].append(i)


def get_syurui(char_idxs, l, r):
    ret = 0
    for v in char_idxs.values():
        l_idx = bisect_left(v, l)
        r_idx = bisect_right(v, r)
        # print(v,l_idx,r_idx)
        if r_idx - l_idx > 0:
            ret += 1
    return ret


Q = read_a_int()
for q in range(Q):
    com, a, b = read().split()
    if int(com) == 2:
        a, b = int(a) - 1, int(b) - 1
        print(get_syurui(char_idxs, a, b))
    else:
        i = int(a) - 1
        if S[i] == b:
            continue
        # i文字目を消す
        tmp = char_idxs[S[i]]
        del tmp[index(tmp, i)]
        char_idxs[S[i]] = tmp
        # cのidxに挿入し直す
        insort_left(char_idxs[b], i)