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: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from bisect import bisect_right

n = int(input())
s = list(input())
q = int(input())

ind_list = [[] for _ in range(26)]

for i, x in enumerate(s):
    ind_list[ord(x)-97].append(i)

for _ in range(q):
    _type, val1, val2 = input().split()
    if _type == '1':
        i = int(val1)-1
        c = val2
        if s[i] == c:
            continue
        ind_list[ord(s[i])-97].remove(i)
        ind_list[ord(c)-97].append(i)
        ind_list[ord(c)-97].sort()
        s[i] = c
    elif _type == '2':
        l = int(val1)-1
        r = int(val2)-1
        ans = 0
        for i in range(26):
            if bisect_right(ind_list[i], r) - bisect_left(ind_list[i], l) > 0:
                ans += 1
        print(ans)
    else:
        print('Exception caught!')
        exit()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
from bisect import bisect_right

n = int(input())
s = list(input())
q = int(input())

ind_list = [[] for _ in range(26)]

for i, x in enumerate(s):
    ind_list[ord(x)-97].append(i)

for _ in range(q):
    _type, val1, val2 = input().split()
    if _type == '1':
        i = int(val1)-1
        c = val2
        ind_list[ord(s[i])-97].remove(i)
        ind_list[ord(c)-97].append(i)
        ind_list[ord(c)-97].sort()
        s[i] = c
    elif _type == '2':
        l = int(val1)-1
        r = int(val2)-1
        ans = 0
        for i in range(26):
            if bisect_right(ind_list[i], r) - bisect_left(ind_list[i], l) > 0:
                ans += 1
        print(ans)
    else:
        print('Exception caught!')
        exit()

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        o=ord(s)-ord("a")
        alphabet[o].pop(bisect.bisect_left(alphabet[o],A-1))
        index=bisect.bisect(alphabet[ord(B)-ord("a")],A-1)
        #alphabet[o]=alphabet[o][:index]+[A-1]+alphabet[o][index:]
        #bisect.insort(alphabet[o],A-1)
        alphabet[ord(B)-ord("a")].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            #indexR=bisect.bisect_right(alphabet[i],B-1)
            #ans+=(indexL!=indexR)
            if indexL==len(alphabet[i]):
                continue
            ans+=(alphabet[i][indexL]<=B-1)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        alphabet[ord(s)-ord("a")].pop(bisect.bisect_left(alphabet[ord(s)-ord("a")],A-1))
        index=bisect.bisect(alphabet[ord(B)-ord('a')],A-1)
        #alphabet[ord(B)-ord('a')]=alphabet[ord(B)-ord('a')][:index]+[A-1]+alphabet[ord(B)-ord('a')][index:]
        #bisect.insort(alphabet[ord(B)-ord('a')],A-1)
        alphabet[ord(B)-ord('a')].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            #indexR=bisect.bisect_right(alphabet[i],B-1)
            #ans+=(indexL!=indexR)
            if indexL==len(alphabet[i]):
                continue
            ans+=(alphabet[i][indexL]<=B-1)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        alphabet[ord(s)-ord("a")].pop(bisect.bisect_left(alphabet[ord(s)-ord("a")],A-1))
        index=bisect.bisect(alphabet[ord(B)-ord('a')],A-1)
        #alphabet[ord(B)-ord('a')]=alphabet[ord(B)-ord('a')][:index]+[A-1]+alphabet[ord(B)-ord('a')][index:]
        #bisect.insort(alphabet[ord(B)-ord('a')],A-1)
        alphabet[ord(B)-ord('a')].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            indexR=bisect.bisect_right(alphabet[i],B-1)
            ans+=(indexL!=indexR)
            #if indexL>len(alphabet[i]):
            #    continue
            #ans+=(alphabet[i][indexL+1]<=B-1)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        alphabet[ord(s)-ord("a")].pop(bisect.bisect_left(alphabet[ord(s)-ord("a")],A-1))
        index=bisect.bisect(alphabet[ord(B)-ord('a')],A-1)
        alphabet[ord(B)-ord('a')]=alphabet[ord(B)-ord('a')][:index]+[A-1]+alphabet[ord(B)-ord('a')][index:]
        #bisect.insort(alphabet[ord(B)-ord('a')],A-1)
        S[A-1]=B
    if Type=="2":
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            indexR=bisect.bisect_right(alphabet[i],B-1)
            ans+=(indexL!=indexR)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        alphabet[ord(s)-ord("a")].pop(bisect.bisect_left(alphabet[ord(s)-ord("a")],A-1))
        #index=bisect.bisect(alphabet[ord(B)-ord('a')],A-1)
        #alphabet[ord(B)-ord('a')]=alphabet[ord(B)-ord('a')][:index]+[A-1]+alphabet[ord(B)-ord('a')][index:]
        bisect.insort(alphabet[ord(B)-ord('a')],A-1)
        S[A-1]=B
    if Type=="2":
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            indexR=bisect.bisect_right(alphabet[i],B-1)
            ans+=(indexL!=indexR)
        print(ans)

Submission status: Time Limit Exceeded

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, self.end_lower(node.right))

    def end_lower(self, node):
        #あるnodeの下の部分木のうち最小値 nodeにdataあることが前提
        if node.left is None:
            return node.data
        else:
            return self.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)
        sepp = '|'*node.height
        print_str = sepp+str(node.data)+sepp
        print(print_str, 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: Time Limit Exceeded

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

for i, c in enumerate(s):
    cnt[c].append(i)

q = int(input())
for _ in range(q):
    t, x, y = input().split()
    ans = 0
    if t == '1':
        i, c = int(x) - 1, y
        a = bisect.bisect_left(cnt[s[i]], i)
        cnt[s[i]].pop(a)
        s[i] = c
        b = bisect.bisect_left(cnt[c], i)
        cnt[c].insert(b, 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: Time Limit Exceeded

Solution code:
n = int(input())
s = [i for i in input()]
q = int(input())
for _ in range(q):
    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: Time Limit Exceeded

Solution code:
import bisect

import sys
input = sys.stdin.readline

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':
        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: Time Limit Exceeded

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':
        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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

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)


import bisect

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

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)


import bisect

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

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


alphabet = "abcdefghijklmnopqrstuvwxyz"

bag = { l:[0 for i in range(N)] for l in alphabet}

for i in range(N):
  bag[S[i]][i] = 1

for _ in range(Q):
  t,a,b = input().split()
  a = int(a)
  if int(t) == 1:
    bag[S[a-1]][a-1] = 0
    S[a-1] = b
    bag[b][a-1] = 1
  else:
    count = 0
    b = int(b)
    for l in alphabet:
      if sum(bag[l][a-1:b]) > 0:
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

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)


import bisect

for _ in range(Q):
  t,a,b = input().split()
  a = int(a)
  if int(t) == 1:
    bag[S[a-1]].remove(a)
    S[a-1] = b
    bisect.insort(bag[b],a)
  else:
    count = 0
    b = int(b)
    for l in alphabet:
      left = bisect.bisect_left(bag[l],a)
      right = bisect.bisect_right(bag[l],b)
      if left !=  right:
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()
S = list(inputS())
Q = inputI()
Qs = inputSLL(Q)

alphabet = "abcdefghijklmnopqrstuvwxyz"

bag = { l:[] for l in alphabet}

for i in range(N):
  bag[S[i]].append(i+1)


import bisect

for t,a,b in Qs:
  a = int(a)
  if int(t) == 1:
    bag[S[a-1]].remove(a)
    S[a-1] = b
    bisect.insort(bag[b],a)
  else:
    count = 0
    b = int(b)
    for l in alphabet:
      left = bisect.bisect_left(bag[l],a)
      right = bisect.bisect_right(bag[l],b)
      if left !=  right:
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
from collections import deque
from fractions import gcd
from functools import lru_cache


#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')

#############
# Functions #
#############

######INPUT######
def inputI(): return int(input().strip())
def inputS(): return input().strip()
def inputIL(): return list(map(int,input().split()))
def inputSL(): return list(map(str,input().split()))
def inputILs(n): return list(int(input()) for _ in range(n))
def inputSLs(n): return list(input().strip() for _ in range(n))
def inputILL(n): return [list(map(int, input().split())) for _ in range(n)]
def inputSLL(n): return [list(map(str, input().split())) for _ in range(n)]

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])
    return arr

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#############
# Main Code #
#############

N = inputI()
S = list(inputS())
Q = inputI()
Qs = inputSLL(Q)

alphabet = "abcdefghijklmnopqrstuvwxyz"

bag = { l:[] for l in alphabet}

for i in range(N):
  bag[S[i]].append(i+1)


import bisect

for t,a,b in Qs:
  a = int(a)
  if int(t) == 1:
    bag[S[a-1]].remove(a)
    S[a-1] = b
    bag[b].append(a)
  else:
    count = 0
    b = int(b)
    for l in alphabet:
      bag[l].sort()
      left = bisect.bisect_left(bag[l],a)
      right = bisect.bisect_right(bag[l],b)
      if left !=  right:
        count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val=init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length() #Nを超える最小の2のべき乗
        # 0-indexedで管理(N0-1からはじまる)
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res= left | right
        return res

    def update(self,k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])
    
            if L & 1:
                s = self._segfunc(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s
def main():
    n=inp()
    s=[set(i) for i in list(input()) if i!="\n"]
    st = SegmentTree(set(), n)
    for i in range(n):
        st.update(i,s[i])
    q = inp()
    ans = []
    for i in range(q):
        mode, first, second = input().split()
        if mode == "1":
            if second in st.data[int(first) - 1 + st.N0 - 1]:
                continue
            st.update(int(first) - 1, set(second))
        else:
            ans.append(len(st.query(int(first) - 1, int(second))))
    for i in ans:
        print(i)

if __name__ == "__main__":
    main()