Problem p02763 (python)

Fixed submission:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().rstrip().split()
def LST2(N): return [sys.stdin.readline().rstrip().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

N = I()
S = list(ST())
Q = I()
bits=[[0]*(N+1) for _ in range(26)]

def ctoi(c): #アルファベットを0-25の数字に変換
    return ord(c)-97

def query(pos): #各文字について1-pos番目までの文字数をカウント
    ret = [0]*26
    for i in range(26):
        tmp = 0
        p = pos
        while p>0:
            tmp += bits[i][p]
            bit_len = p&(-p) #p&(-p)は1のたつ最小桁であり、今の区間の長さをあらわす
            p -= bit_len #つぎに足すべき塊の番号は、今の値から区間の長さを引くとでる
        ret[i] = tmp #アルファベットiの1-posまでの出現回数
    return ret

def update(pos, a, x): #a番目のアルファベットについてpos番目の要素の値を更新
    while pos <= N:
        bits[a][pos] += x
        pos += pos&(-pos)

for i in range(N):
    update(i+1, ctoi(S[i]),1)
for _ in range(Q):
    q = LST()
    if q[0]=='1':
        i = int(q[1])
        c = q[2]
        if S[i-1]==c:
            continue
        update(i, ctoi(S[i-1]), -1) #S[i-1]のi番目に1が立っているが、これを下ろして削除を表現
        #O(logN)で削除が完了
        update(i, ctoi(c), 1)
        S[i-1] = c
    else:
        ans = 0
        l = int(q[1])
        r = int(q[2])
        r_sum = query(r)
        l_sum = query(l-1)
        for i in range(26):
            if r_sum[i]-l_sum[i] > 0:
                ans += 1
        print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().split()
def LST2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 0 #ノードの高さ


class AVL:
    def __init__(self):
        self.root = None


    def get_height(self, node):
        if not node:
            return -1
        return node.height

    def overwrite_height(self, node):
        return max(self.get_height(node.left),self.get_height(node.right))+1

    def get_balance(self, node):
        '''
        返り値が1以上の時、左がより高いので右回転
        -1以下の時左回転
        '''
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    def rotate_right(self, node): #nodeが回転の頂点、node.leftが頂点にくる。頂点を返す
        temp_left = node.left
        temp_left_right = temp_left.right
        temp_left.right = node
        node.left = temp_left_right

        node.height = self.overwrite_height(node)
        temp_left.height = self.overwrite_height(temp_left)

        return temp_left

    def rotate_left(self, node): #nodeが回転の頂点、node.leftが頂点にくる
        temp_right = node.right
        temp_right_left = temp_right.left
        temp_right.left = node
        node.right = temp_right_left

        node.height = self.overwrite_height(node)
        temp_right.height = self.overwrite_height(temp_right)

        return temp_right

    def insert(self, data):
        #print('--------------')
        #print('start inserting {}'.format(data))
        self.root = self._insert(data, self.root)
        #print('finish inserting')
        #print('--------------')

    def _insert(self, data, node): #dataをnodeに挿入、回転した上でrootを返す
        if not node:
            return Node(data)

        if data < node.data:
            node.left = self._insert(data,node.left)
        else:
            node.right = self._insert(data, node.right)
        node.height = self.overwrite_height(node)

        return self.settle_unbalance(data, node)

    def settle_unbalance(self, data, node): #回転を行なった上でrootを返す
        balance = self.get_balance(node)
        if balance > 1 and data < node.left.data:
            #print('right')
            return self.rotate_right(node)
        if balance < -1 and data > node.right.data:
            #print('left')
            return self.rotate_left(node)
        if balance > 1 and data > node.left.data:
            #print('left,right')
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        if balance < -1 and data < node.right.data:
            #print('right,left')
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        return node

    def remove(self, data):
        if self.root:
                self.root = self._remove(data, self.root)

    def _remove(self, data, node):
        if not node:
            return None
        if data < node.data:
            node.left = self._remove(data, node.left)
        elif data > node.data:
            node.right = self._remove(data, node.right)
        else:
            if not node.right and not node.left:
                del node
                return None
            if not node.right:
                temp = node.left
                del node
                return temp
            if not node.left:
                temp = node.right
                del node
                return temp

            def _get_max_node(node): #左側のsubtreeの最大ノードを代わりのノードとする
                if node.right:
                    return _get_max_node(node.right)
                return node
            temp = _get_max_node(node.left)
            node.data = temp.data
            node.left = self._remove(temp.data, node.left) #この場合もとのノード削除は不要。削除ノードを、新規ノードにおきかえればよい

        if not node:
            return node

        node.height = self.overwrite_height(node)
        balance = self.get_balance(node)
        if balance > 1 and self.get_balance(node.left) >= 0:
            return self.rotate_right(node)
        if balance < -1 and self.get_balance(node.right) <= 0:
            return self.rotate_left(node)
        if balance > 1 and self.get_balance(node.left) < 0:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        if balance < -1 and self.get_balance(node.right) > 0:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)

        return node


    def search(self, search): #インターフェース
        searcher = self._search(search)
        if searcher is None:
            pass
            #print('Search target is not found.')
        elif searcher == True:
            pass
            #print(str(search)+' is found.')
        elif searcher == False:
            pass
            #print(str(search)+' is not found.')

    def _search(self,search):
            n = self.root
            if n is None:
                return None
            else:
                lst = []
                lst.append(n)
                while len(lst) > 0:
                    node = lst.pop()
                    if node.data == search:
                        return True
                    if node.right is not None:
                        lst.append(node.right)
                    if node.left is not None:
                        lst.append(node.left)
                return False

    def search_higher(self, search):
        if self.root:
            return self._search_higher(search, self.root, None)
        else:
            print('木構造がありません')

    def _search_higher(self, search, node, temp_high):
        '''
        nodeを頂点とする部分木から、searchより大きい中でもっとも小さいnodeのデータを返す
        '''
        if node is None:
            return temp_high
        if node.data > search:
            temp_high = node.data
            if node.left is None:
                return temp_high
            else:
                return self._search_higher(search, node.left, temp_high)
        elif node.data < search:
            if node.right is None:
                return temp_high
            else:
                return self._search_higher(search, node.right, temp_high)
        else:  #nodeの値が探索値と一致する時
            if node.right is None:
                return temp_high
            else:
                if temp_high is None:
                    return self.end_lower(node.right)
                else:
                    return min(temp_high, node.right.end_lower(node.right.data))

    def end_lower(self, node):
        #あるnodeの下の部分木のうち最小値 nodeにdataあることが前提
        if node.left is None:
            return node.data
        else:
            return end_lower(node.left)

    def traverse_inorder(self):
        if self.root:
            self._traverse_inorder(self.root)
            # 改行対策
            print()
        else:
            print('木は空です。')

    def _traverse_inorder(self, node):
        if node.left:
            self._traverse_inorder(node.left)
        sep = '|'*node.height
        print(sep+str(node.data)+sep, end=' ')
        if node.right:
            self._traverse_inorder(node.right)

N = I()
S = ST()
Q = I()
D = {}
for i in range(N):
    letter = S[i]
    D[letter] = D.get(letter,AVL())
    D[letter].insert(i)

for _ in range(Q):
    q = LST()
    if q[0]=='1':
        i = int(q[1])
        c = q[2]
        for letter in D:
            D[letter].remove(i-1)
        D[c] = D.get(c,AVL())
        D[c].insert(i-1)
    else:
        ans = 0
        l = int(q[1])
        r = int(q[2])
        for letter in D:
            next_idx = D[letter].search_higher(l-2)
            if next_idx is not None:
                if r-1 >= next_idx:
                    ans += 1

        print(ans)

Buggy submission (verdict: Runtime Error):
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().split()
def LST2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 0 #ノードの高さ


class AVL:
    def __init__(self):
        self.root = None


    def get_height(self, node):
        if not node:
            return -1
        return node.height

    def overwrite_height(self, node):
        return max(self.get_height(node.left),self.get_height(node.right))+1

    def get_balance(self, node):
        '''
        返り値が1以上の時、左がより高いので右回転
        -1以下の時左回転
        '''
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    def rotate_right(self, node): #nodeが回転の頂点、node.leftが頂点にくる。頂点を返す
        temp_left = node.left
        temp_left_right = temp_left.right
        temp_left.right = node
        node.left = temp_left_right

        node.height = self.overwrite_height(node)
        temp_left.height = self.overwrite_height(temp_left)

        return temp_left

    def rotate_left(self, node): #nodeが回転の頂点、node.leftが頂点にくる
        temp_right = node.right
        temp_right_left = temp_right.left
        temp_right.left = node
        node.right = temp_right_left

        node.height = self.overwrite_height(node)
        temp_right.height = self.overwrite_height(temp_right)

        return temp_right

    def insert(self, data):
        #print('--------------')
        #print('start inserting {}'.format(data))
        self.root = self._insert(data, self.root)
        #print('finish inserting')
        #print('--------------')

    def _insert(self, data, node): #dataをnodeに挿入、回転した上でrootを返す
        if not node:
            return Node(data)

        if data < node.data:
            node.left = self._insert(data,node.left)
        else:
            node.right = self._insert(data, node.right)
        node.height = self.overwrite_height(node)

        return self.settle_unbalance(data, node)

    def settle_unbalance(self, data, node): #回転を行なった上でrootを返す
        balance = self.get_balance(node)
        if balance > 1 and data < node.left.data:
            #print('right')
            return self.rotate_right(node)
        if balance < -1 and data > node.right.data:
            #print('left')
            return self.rotate_left(node)
        if balance > 1 and data > node.left.data:
            #print('left,right')
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        if balance < -1 and data < node.right.data:
            #print('right,left')
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        return node

    def remove(self, data):
        if self.root:
                self.root = self._remove(data, self.root)

    def _remove(self, data, node):
        if not node:
            return None
        if data < node.data:
            node.left = self._remove(data, node.left)
        elif data > node.data:
            node.right = self._remove(data, node.right)
        else:
            if not node.right and not node.left:
                del node
                return None
            if not node.right:
                temp = node.left
                del node
                return temp
            if not node.left:
                temp = node.right
                del node
                return temp

            def _get_max_node(node): #左側のsubtreeの最大ノードを代わりのノードとする
                if node.right:
                    return _get_max_node(node.right)
                return node
            temp = _get_max_node(node.left)
            node.data = temp.data
            node.left = self._remove(temp.data, node.left) #この場合もとのノード削除は不要。削除ノードを、新規ノードにおきかえればよい

        if not node:
            return node

        node.height = self.overwrite_height(node)
        balance = self.get_balance(node)
        if balance > 1 and self.get_balance(node.left) >= 0:
            return self.rotate_right(node)
        if balance < -1 and self.get_balance(node.right) <= 0:
            return self.rotate_left(node)
        if balance > 1 and self.get_balance(node.left) < 0:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        if balance < -1 and self.get_balance(node.right) > 0:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)

        return node


    def search(self, search): #インターフェース
        searcher = self._search(search)
        if searcher is None:
            pass
            #print('Search target is not found.')
        elif searcher == True:
            pass
            #print(str(search)+' is found.')
        elif searcher == False:
            pass
            #print(str(search)+' is not found.')

    def _search(self,search):
            n = self.root
            if n is None:
                return None
            else:
                lst = []
                lst.append(n)
                while len(lst) > 0:
                    node = lst.pop()
                    if node.data == search:
                        return True
                    if node.right is not None:
                        lst.append(node.right)
                    if node.left is not None:
                        lst.append(node.left)
                return False

    def search_higher(self, search):
        if self.root:
            return self._search_higher(search, self.root, None)
        else:
            print('木構造がありません')

    def _search_higher(self, search, node, temp_high):
        '''
        nodeを頂点とする部分木から、searchより大きい中でもっとも小さいnodeのデータを返す
        '''
        if node is None:
            return temp_high
        if node.data > search:
            temp_high = node.data
            if node.left is None:
                return temp_high
            else:
                return self._search_higher(search, node.left, temp_high)
        elif node.data < search:
            if node.right is None:
                return temp_high
            else:
                return self._search_higher(search, node.right, temp_high)
        else:  #nodeの値が探索値と一致する時
            if node.right is None:
                return temp_high
            else:
                if temp_high is None:
                    return self.end_lower(node.right)
                else:
                    return min(temp_high, node.right.end_lower(node.right.data))

    def end_lower(self, node):
        #あるnodeの下の部分木のうち最小値 nodeにdataあることが前提
        if node.left is None:
            return node.data
        else:
            return end_lower(node.left)

    def traverse_inorder(self):
        if self.root:
            self._traverse_inorder(self.root)
            # 改行対策
            print()
        else:
            print('木は空です。')

    def _traverse_inorder(self, node):
        if node.left:
            self._traverse_inorder(node.left)
        sep = '|'*node.height
        print(sep+str(node.data)+sep, end=' ')
        if node.right:
            self._traverse_inorder(node.right)

N = I()
S = ST()
Q = I()
D = {}
for i in range(N):
    letter = S[i]
    D[letter] = D.get(letter,AVL())
    D[letter].insert(i)

for _ in range(Q):
    q = LST()
    if q[0]=='1':
        i = int(q[1])
        c = q[2]
        for letter in D:
            D[letter].remove(i-1)
        D[c] = D.get(c,AVL())
        D[c].insert(i-1)
    else:
        ans = 0
        l = int(q[1])
        r = int(q[2])
        for letter in D:
            next_idx = D[letter].search_higher(l-2)
            if next_idx is not None:
                if r-1 >= next_idx:
                    ans += 1

        print(ans)