Problem:


Score : 500 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Process Q queries of the following two types:

Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)

Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Constraints

N, Q, i_q, l_q, and r_q are integers.

S is a string consisting of lowercase English letters.

c_q is a lowercase English letter.

1 \leq N \leq 500000

1 \leq Q \leq 20000

|S| = N

1 \leq i_q \leq N

1 \leq l_q \leq r_q \leq N

There is at least one query of type 2 in each testcase.

Input

Input is given from Standard Input in the following format:

N
S
Q
Query_1
\vdots
Query_Q

Here, Query_i in the 4-th through (Q+3)-th lines is one of the following:

1 i_q c_q

2 l_q r_q

Output

For each query of type 2, print a line containing the answer.

Sample Input 1

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

Sample Output 1

3
1
5

In the first query, cdbb contains three kinds of letters: b , c , and d, so we print 3.

In the second query, S is modified to abcdzbd.

In the third query, a contains one kind of letter: a, so we print 1.

In the fourth query, S is modified to abcazbd.

In the fifth query, S does not change and is still abcazbd.

In the sixth query, abcazbd contains five kinds of letters: a, b, c, d, and z, so we print 5.



Sample input:
7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7


Sample output:
3
1
5

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
import heapq, bisect
n = int(input())
s = list(input())
alp = 'abcdefghijklmnopqrstuvwxyz'
cnt = {c: set() for c in alp}

for i in range(n):
    cnt[s[i]].add(i)

q = int(input())
for _ in range(q):
    t, x, y = input().split()
    ans = 0
    if t == '1':
        i, c = int(x) - 1, y
        cnt[s[i]].remove(i)
        cnt[c].add(i)
    else:
        l, r = int(x) - 1, int(y) - 1
        for c in alp:
            sort_cnt = sorted(cnt[c])
            a = bisect.bisect_left(sort_cnt, l)
            if a < len(cnt[c]) and sort_cnt[a] <= r:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
import heapq, bisect
n = int(input())
s = list(input())
alp = 'abcdefghijklmnopqrstuvwxyz'
cnt = {c: [] for c in alp}

for i in range(n):
    heapq.heappush(cnt[s[i]], i)

q = int(input())
for _ in range(q):
    t, x, y = input().split()
    ans = 0
    if t == '1':
        i, c = int(x) - 1, y
        cnt[s[i]].remove(i)
        heapq.heappush(cnt[c], i)
    else:
        l, r = int(x) - 1, int(y) - 1
        for c in alp:
            a = bisect.bisect_left(cnt[c], l)
            if a < len(cnt[c]) and cnt[c][a] <= r:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
class SegmentTree:
    def __init__(self,l):
        nb = bin(len(l))[2:]
        b = sum([int(d) for d in nb])
        if b == 1:
            self.end_leaves = pow(2,len(nb)-1)
        else:
            self.end_leaves = pow(2,len(nb))
        self.tree = [set() for _ in range(self.end_leaves*2)]
        
        for i in range(len(l)):
            self.tree[self.end_leaves+i].add(l[i])
            
    def union(self,a):
        if a >= self.end_leaves // 2:
            self.tree[a] = self.tree[a*2] | self.tree[a*2+1]
            return self.tree[a]
        else:
            self.tree[a] = self.union(a*2) | self.union(a*2+1)
            return self.tree[a]
    def update(self,a,s):
        x = a + self.end_leaves
        self.tree[x] = set(s)
        while x > 1:
            x //= 2
            self.tree[x] = self.tree[x*2] | self.tree[x*2+1]
    def query(self,l,r):
        x = l + self.end_leaves
        y = r + self.end_leaves
        tl = set()
        tr = set()
        while y - x > 1:
            if x & 1:
                tl = tl | self.tree[x]
                x += 1
            if y & 0:
                tr = self.tree[y] | tr
                y -= 1
            x >>= 1
            y >>= 1
        if y - x == 0:
            print(len(tl|tr|self.tree[x]))
        else:
            print(len(tl|tr|self.tree[x]|self.tree[y]))
            
            

N = int(input())
S = list(input())
st = SegmentTree(S)
st.union(1)
Q = int(input())
for i in range(Q):
    q = input().split()
    if q[0] == '1':
        st.update(int(q[1])-1,q[2])
    else:
        st.query(int(q[1])-1,int(q[2])-1)

Submission status: Runtime Error

Solution code:
n = int(input())
s = [i for i in input()]
q = int(input())
for _ in range(n):
    num, a, b = input().split()
    if num == "1": s[int(a)-1] = b
    else: print(len(set(s[int(a)-1:int(b)])))

Submission status: Runtime Error

Solution code:
import bisect

N=int(input())
S=list(input())
Q=int(input())

alphabet="abcdefghijklmnopqrstuvwxyz"
bag={l:[] for l in alphabet}
for i in range(N):
    bag[S[i]].append(i+1)
#print(bag)

for i in range(Q):
    Type,a,b=input().split()
    if Type=='1':
        if S[a-1]!=b:
            a=int(a)
            bag[S[a-1]].remove(a)
            S[a-1]=b
            bisect.insort(bag[b],a)
    else:
        cnt=0
        a,b=int(a),int(b)
        for l in alphabet:
            bl=len(bag[l])
            if bl>0:
                left=bisect.bisect_left(bag[l],a)
                if left!=bl and bag[l][left]<=b:
                        cnt+=1
        print(cnt)

Submission status: Runtime Error

Solution code:
import bisect

N=int(input())
S=list(input())
Q=int(input())
L=[[] for i in range(150)]

for i in range(N):
    L[ord(S[i])].append(i)

#print(L)

for i in range(Q):
    
    Type,q1,q2=map(str,input().split())
    if Type=='1':
        q1=int(q1)-1
        L[ord(S[q1])].remove(q1)
        L[ord(q2)].append(q1)
        L[ord(q2)]=sorted(L[ord(q2)])
    else:
        q1,q2=int(q1)-1,int(q2)-1
        cnt=0
        for j in range(97,123):
            if len(L[j])!=0:
                L[j]=sorted(L[j])
                n=bisect.bisect_left(L[j],q1)
                #print(j,n)
                if n<len(L[j]) and L[j][n]<=q2:
                    cnt+=1
                    #print(str(j),'<')
        print(cnt)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import bisect

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    N = int(input())
    S = list(input())
    Q = int(input())

    L = [[] for x in range(26)] # i番目のリストは、アルファベットが現れるインデックスのリストを持つ。

    for idx, s in enumerate(S):
        L[ord(s)-ord("a")].append(idx)

    for _ in range(Q):
        row = input().split()
        if row[0] == '1':
            y, z = int(row[1])-1, row[2]
            idx_target = ord(S[y]) - ord("a")
            idx_del = bisect.bisect_left(L[idx_target], y)
            if idx_del < len(L[idx_target]):
                L[idx_target].pop(idx_del)
            bisect.insort(L[ord(z) - ord("a")], y)
            S[y] = z

        elif row[0] == '2':
            y, z = int(row[1]) - 1, int(row[2]) - 1
            answer = 0
            for idx_alphabet in range(ord("a"), ord("z")+1):
                left = bisect.bisect_left(L[idx_alphabet], y)
                if left < len(L[idx_alphabet]) and y <= L[idx_alphabet][left] <= z:
                    answer += 1
            print(answer)

    # Failed to predict input format
    pass

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#query=10**4*2
#alph=26
#insert=500000
#O(|insert*query*alph|)?
def main():
	import bisect,sys
	input=sys.stdin.readline
	n=int(input())
	s=list(input().rstrip())
	q=int(input())
	word=[[]for _ in range(26)]
	for i,j in enumerate(s):
		ch=ord(j)-ord("a")
		word[ch].append(i)
	for _ in range(q):
		query=input().split()
		if query[0]=="1":
			i,x=int(query[1])-1,ord(query[2])-ord("a")
			old=ord(s[i])-ord("a")
			word[old].remove(i)
			new=bisect.bisect_left(word[x],i)
			word[x].insert(new,i)
			s[i]=x
		# else:
		# 	l,r=int(query[1])-1,int(query[2])-1
		# 	kind=0
		# 	for i in range(26):
		# 		l=bisect.bisect_left(word[i],l)
		# 		if l==len(word[i]):
		# 			continue
		# 		if word[i][l]<=r:
		# 			kind+=1
		# 	print(kind)
if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
#query=10**4*2
#alph=26
#insert=500000
#O(|insert*query*alph|)?
def main():
	import bisect,sys
	input=sys.stdin.readline
	n=int(input())
	s=list(input().rstrip())
	q=int(input())
	word=[[]for _ in range(26)]
	for i,j in enumerate(s):
		ch=ord(j)-ord("a")
		word[ch].append(i)
	for _ in range(q):
		query=input().split()
		if query[0]=="1":
			i,x=int(query[1])-1,ord(query[2])-ord("a")
			old=ord(s[i])-ord("a")
			word[old].remove(i)
			new=bisect.bisect_left(word[x],i)
			word[x].insert(new,i)
			s[i]=x
		else:
			l,r=int(query[1])-1,int(query[2])-1
			kind=0
			for i in range(26):
				l=bisect.bisect_left(word[i],l)
				if l==len(word[i]):
					continue
				if word[i][l]<=r:
					kind+=1
			print(kind)
if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
#query=10**4*2
#alph=26
#insert=500000
#O(|insert*query*alph|)?
def main():
	import bisect
	input=sys.stdin.readline
	n=int(input())
	s=list(input().rstrip())
	q=int(input())
	word=[[]for _ in range(26)]
	for i,j in enumerate(s):
		ch=ord(j)-ord("a")
		word[ch].append(i)
	for _ in range(q):
		query=input().split()
		if query[0]=="1":
			i,x=int(query[1])-1,ord(query[2])-ord("a")
			old=ord(s[i])-ord("a")
			word[old].remove(i)
			new=bisect.bisect_left(word[x],i)
			word[x].insert(new,i)
			s[i]=x
		else:
			l,r=int(query[1])-1,int(query[2])-1
			kind=0
			for i in range(26):
				l=bisect.bisect_left(word[i],l)
				if l==len(word[i]):
					continue
				if word[i][l]<=r:
					kind+=1
			print(kind)
if __name__ == '__main__':
	main()

Submission status: Runtime Error

Solution code:
import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
from bisect import bisect_left, bisect_right, insort
def S(): return sys.stdin.readline().rstrip()
def I(): return int(sys.stdin.readline().rstrip())
def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def LS(): return list(sys.stdin.readline().rstrip().split())
#N = I()
#A = [LI() for _ in range(N)]

n = I()
s = S()
q = I()
box =[[] for _ in range(26)]
for i in range(n):
    o = ord(s[i]) - ord ('a')
    box[o].append(i)
for i in range(q):
    qe,a,b = map(str,input().split())
    if qe == '1':
        a = int(a) - 1
        if s[a] == b:
            continue
        else:
            o = ord(s[a]) - ord('a')
            box[o].pop(bisect_left(box[o], a))
            oo = ord(b) - ord('a')
            insort(box[oo],a)
    else:
        ans = 0
        l = int(a)
        r = int(b)
        for i in range(26):
            ind = bisect_left(box[i], l-1)
            if ind < len(box[i]) and box[i][ind] <= r - 1:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort_left
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 各アルファベットのindexのリストを作り,bisect_left()
N = ir()
S = sr()
dic = defaultdict(list)
for i, s in enumerate(S):
    dic[s].append(i)

Q = ir()
for _ in range(Q):
    a, b, c = sr().split()
    if a == '1':
        b = int(b) - 1
        if S[b] == c:
            continue
        dic[S[b]].remove(b)
        insort_left(dic[c], b)
    else:
        b = int(b) - 1; c = int(c) - 1
        kind = 0
        for x in range(26):
            word = chr(ord('a')+x)
            if len(dic[word]) == 0:
                continue
            i = bisect_left(dic[word], b)
            j = bisect_right(dic[word], c)
            if i != j:
                kind += 1
        print(kind)

# 07

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
from bisect import bisect_left, bisect_right, insort_left
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 各アルファベットのindexのリストを作り,bisect_left()
N = ir()
S = sr()
dic = defaultdict(list)
for i, s in enumerate(S):
    dic[s].append(i)

Q = ir()
for _ in range(Q):
    a, b, c = sr().split()
    if a == '1':
        b = int(b) - 1
        if S[b] == c:
            continue
        dic[S[b]].remove(b)
        insort_left(dic[c], b)
    else:
        b = int(b) - 1; c = int(c) - 1
        kind = 0
        for x in range(26):
            word = chr(ord('a')+x)
            i = bisect_left(dic[word], b)
            j = bisect_right(dic[word], c)
            if i != j:
                kind += 1
        print(kind)

# 07

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    def segfunc(x, y):
        return x | y

    def init(arr):
        for i in range(n):
            seg[i+num-1] = {arr[i]}
        for i in range(num-2,-1,-1) :
            seg[i] = segfunc(seg[2*i+1],seg[2*i+2]) 
        
    def update(k,x):
        k += num-1
        seg[k].clear()
        seg[k] = {x}
        while k:
            k = (k-1)//2
            seg[k].clear()
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
        
    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

    n = int(input())
    s = list(input().rstrip())
    for i in range(n):
        s[i] = ord(s[i]) - 97

    ide_ele = set()

    num =2**((n-1).bit_length())

    # セグ木初期化
    seg=[ide_ele]*2*num
    init(s)

    q = int(input())
    for _ in range(q):
        a,b,c = input().rstrip().split()
        if a == '1':
            b = int(b)
            c = ord(c) - 97
            update(b-1, c)
        else:
            b = int(b)
            c = int(c)
            print(len(query(b-1, c)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10**7)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate, groupby, product
    from bisect import bisect_left,bisect_right
    from heapq import heapify, heappop, heappush
    import math
    from math import gcd

    #inf = 10**17
    #mod = 10**9 + 7

    def segfunc(x, y):
        return x | y

    def init(arr):
        for i in range(n):
            seg[i+num-1] = set(arr[i])
        for i in range(num-2,-1,-1) :
            seg[i] = segfunc(seg[2*i+1],seg[2*i+2]) 
        
    def update(k,x):
        k += num-1
        seg[k].clear()
        seg[k] = set(x)
        while k:
            k = (k-1)//2
            seg[k].clear()
            seg[k] = segfunc(seg[k*2+1],seg[k*2+2])
        
    def query(p,q):
        if q<=p:
            return ide_ele
        p += num-1
        q += num-2
        res=ide_ele
        while q-p>1:
            if p&1 == 0:
                res = segfunc(res,seg[p])
            if q&1 == 1:
                res = segfunc(res,seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = segfunc(res,seg[p])
        else:
            res = segfunc(segfunc(res,seg[p]),seg[q])
        return res

    n = int(input())
    s = list(input().rstrip())

    ide_ele = set()

    num =2**((n-1).bit_length())

    # セグ木初期化
    seg=[ide_ele]*2*num
    init(s)

    q = int(input())
    for _ in range(q):
        a,b,c = input().rstrip().split()
        if a == '1':
            b = int(b)
            update(b-1, c)
        else:
            b = int(b)
            c = int(c)
            print(len(query(b-1, c)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
from collections import defaultdict
#from itertools import combinations
sys.setrecursionlimit(10**7)

def run():

    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    #N, *A = map(int, open(0))
    #N = int(input())
    ###
    def bin_search(A,low_val):
        high = len(A) -1
        low = 0
        current = high // 2

        if A[-1] < low_val:
            return None, None
        if A[0] > low_val:
            return 0, A[0]
        while high-low >1:
            if A[current] == low_val:return current, A[current]
            if A[current] > low_val:
                high = current
                current += low
                current //= 2
            else:
                low = current
                current += high
                current //= 2
        return high, A[high]

    N = int(sysread())
    S = list('0'+input())
    dic = defaultdict(lambda:[])
    for idx, s in enumerate(S[1:],1):
        dic[s].append(idx)

    Q = int(sysread())
    queries = []
    for _ in range(Q):
        queries.append(sysread().split())

    for q,i,c in queries:
        if q == '1':
            i = int(i)
            old = S[i]
            dic[old].remove(i)
            if dic[c] == []:
                dic[c].append(i)
            else:
                h, _ = bin_search(dic[c], i)
                if h is None:
                    dic[c].append(i)
                else:dic[c].insert(h,i)
            S[i] = c
        else:
            count = 0
            i,c = int(i), int(c)
            for key in dic.keys():
                tmp = dic[key]
                _,v = bin_search(tmp, i)
                if v is None:continue
                if v <= c:
                    count += 1
            print(count)

if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
from collections import defaultdict
#from itertools import combinations
sys.setrecursionlimit(10**7)

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    #N, *A = map(int, open(0))
    #N = int(input())
    ###
    def  bin_search(A,low_val):
        high = len(A) -1
        low = 0
        current = high // 2

        if A[-1] < low_val:
            return high, None, None
        if A[0] > low_val:
            return None, low , A[0]
        while high-low >1:
            if A[current] >= low_val:
                high = current
                current += low
                current //= 2
            else:
                low = current
                current += high
                current //= 2
        return low, high, A[high]

    N = int(sysread())
    S = list('0'+input())
    dic = defaultdict(lambda:[])
    for idx, s in enumerate(S[1:],1):
        dic[s].append(idx)

    Q = int(sysread())
    queries = []
    for _ in range(Q):
        queries.append(sysread().split())

    for q,i,c in queries:
        if q == '1':
            i = int(i)
            old = S[i]
            dic[old].remove(i)
            if dic[c] == []:
                dic[c].append(i)
            else:
                l,h,_ = bin_search(dic[c], i)
                if h is None:
                    dic[c].append(i)
                else:dic[c].insert(h,i)
            S[i] = c
        else:
            count = 0
            i,c = int(i), int(c)
            for key in dic.keys():
                tmp = dic[key]
                _,_,v = bin_search(tmp, i)
                if v is None:continue
                if v <= c:
                    count += 1
            print(count)

if __name__ == "__main__":
    run()

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
#from operator import itemgetter
sysread = sys.stdin.readline
#from heapq import heappop, heappush
from collections import defaultdict
#from itertools import combinations
sys.setrecursionlimit(10**7)

def run():
    # import sys
    # A = list(map(int, sys.stdin.readline().split()))
    # all = sys.stdin.readlines()
    #N, *A = map(int, open(0))
    #N = int(input())
    ###
    def  bin_search(A,low_val):
        if A[-1] < low_val:
            return 0, 0, None
        if A[0] > low_val:
            return 0, 0 , A[0]
        high = len(A) -1
        low = 0
        current = high // 2
        while high-low >1:
            if A[current] >= low_val:
                high = current
                current = (low + current) //2
            else:
                low = current
                current = (current + high) // 2
        return low, high, A[high]

    N = int(sysread())
    S = list('0'+input())
    dic = defaultdict(lambda:[])
    for idx, s in enumerate(S[1:],1):
        dic[s].append(idx)

    Q = int(sysread())
    queries = []
    for _ in range(Q):
        queries.append(sysread().split())

    for q,i,c in queries:
        if q == '1':
            i = int(i)
            old = S[i]
            dic[old].remove(i)
            if dic[c] == []:
                dic[c].append(i)
            else:
                l,h,_ = bin_search(dic[c], i)
                dic[c].insert(h,i)
            S[i] = c
        else:
            count = 0
            i,c = int(i), int(c)
            for key in dic.keys():
                tmp = dic[key]
                _,_,v = bin_search(tmp, i)
                if v is None:continue
                if v <= c:
                    count += 1
            print(count)

if __name__ == "__main__":
    run()