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:
class SegmentTree:
  """Segmant Tree for query process.

  Args:
    a (List[int]): array.
    identity (int): identity element with f.
  """
  def __init__(self, a, identity=0):
    self.a = a
    self.n = len(a)
    self.identity = identity
    self.depth = (self.n - 1).bit_length()
    self.segment = (1 << self.depth) - 1
    self.tree = [identity] * (self.segment * 2 + 1)
    self.tree[self.segment : self.n + self.segment] = a
    for i in range(self.segment - 1, -1, -1):
      self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

  def update(self, i: int, x: int):
    i += self.segment
    self.tree[i] = x
    while i:
      i = (i - 1) // 2
      self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

  def query(self, l: int, r: int) -> int:
    """Query at [l, r]

    Args:
      l (int): left
      r (int): right

    Returns:
      int: result
    """
    if l > r:
      return self.identity
    l += self.segment
    r += self.segment
    res = self.identity
    while l <= r:
      if not l & 1:
        res = self.f(self.tree[l], res)
      if r & 1:
        res = self.f(res, self.tree[r])
      l = l // 2
      r = (r - 2) // 2
    return res

  def f(self, x: int, y: int) -> int:
    return x | y

n = int(input())
s = input()
q = int(input())
a = ord('a')
segment_tree = [SegmentTree([0] * n) for _ in range(26)]
for i in range(n):
  segment_tree[ord(s[i]) - a].update(i, 1)
for _ in range(q):
  query = input().split()
  if query[0] == '1':
    i = int(query[1])
    c = query[2]
    num_c = ord(c) - a
    for alph in range(26):
      segment_tree[alph].update(i, int(alph == num_c))
  else:
    l = int(query[1])
    r = int(query[2])
    kind = 0
    for alph in range(26):
      kind += segment_tree[alph].query(l, r)
    print(kind)

Submission status: Runtime Error

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from operator import or_

def popcount(x):
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f

class SegmentTree():
    def __init__(self, n, unit, f, initial = []):
        self.f = f
        self.unit = unit
        k = (n-1).bit_length()
        nn = 1 << k + 1
        self.leaf = 1 << k
        if not len(initial):
            self.X = [unit] * nn
        else:
            self.X = [unit] * self.leaf + initial + [unit] * (self.leaf - len(initial))
            for i in range(self.leaf)[::-1]:
                self.X[i] = self.f(self.X[2*i], self.X[2*i+1])
    
    def update(self, i, x):
        i += self.leaf
        self.X[i] = x
        i //= 2
        while i:
            self.X[i] = self.f(self.X[2*i], self.X[2*i+1])
            i //= 2
    
    def query(self, l, r):
        l += self.leaf
        r += self.leaf
        s = self.unit
        while l < r:
            if l & 1:
                s = self.f(self.X[l], s)
                l += 1
            if r & 1:
                r -= 1
                s = self.f(s, self.X[r])
            l >>= 1
            r >>= 1
        return s
    
    def debug(self):
        i = 1
        while i <= self.leaf:
            print(self.X[i:i*2])
            i *= 2
    def debug(self):
        i = 1
        while i <= self.leaf:
            print([bin(a) for a in self.X[i:i*2]])
            i *= 2

N = int(input())
S = [1 << ord(a) - 97 for a in input()]
st = SegmentTree(26, 0, or_, S)

M = int(input())
for _ in range(M):
    a, b, c = input().split()
    if a == "1":
        b = int(b)
        st.update(b-1, 1 << ord(c) - 97)
    else:
        b, c = int(b)-1, int(c)-1
        print(popcount(st.query(b, c + 1)))

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
from collections import Counter
l=Counter()
for i,c in enumerate(list(s)):
    if not l[c]:
        l[c]=[]
    l[c].append(i)

for j in l:
    l[j].append(10**18)
q=int(input())
import bisect
for i in range(q):
    a,b,c=input().split()
    if a=="1":
        b=int(b)-1
        idx=bisect.bisect_left(l[s[b]],b)
        del l[s[b]][idx]
        if not l[c]:
            l[c]=[]
        idx=bisect.bisect_left(l[c],b)
        l[c].insert(idx,b)
        l[c].append(10**18)
    else:
        ans=0
        left,right=int(b)-1,int(c)-1
        for j in l:
            p=bisect.bisect_left(l[j],left)
            q=bisect.bisect_left(l[j],right)
            if p!=q:
                ans+=1
            else:
                if l[j]!=[]:
                    if left<=l[j][p]<=right:
                        ans+=1
        print(ans)

Submission status: Runtime Error

Solution code:
class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    # 1-indexled なので注意
    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    # 1-indexled なので注意
    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

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

def a2n(a):
    return ord(a)-ord("a")

def createInp(a):
    return 1 << a2n(a)

def main():
    N = int(input())
    S = input()
    Q = int(input())
    ST = SegmentTree(N, f=f, default=0)

    for i, s in enumerate(S):
        ST.update(i+1, createInp(s))

    for _ in range(Q):
        t, l, r = input().split()
        if int(t) == 1:
            ST.update(int(l), createInp(r))
        else:
            print(bin(ST.query(int(l), int(r)+1)).count('1'))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    # 1-indexled なので注意
    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    # 1-indexled なので注意
    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

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

def a2n(a):
    return ord(a)-ord("a")

def createInp(a):
    return 1 << a2n(a)

def main():
    N = int(input())
    S = input()
    Q = int(input())
    ST = SegmentTree(N, f=f, default=0)

    for i, s in enumerate(S):
        ST.update(i+1, createInp(s))

    for _ in range(Q):
        t, l, r = input().split()
        if int(t) == 1:
            ST.update(int(l), createInp(s))
        else:
            print(len(ST.query(int(l), int(r)+1)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    # 1-indexled なので注意
    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    # 1-indexled なので注意
    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

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

def main():
    N = int(input())
    S = input()
    Q = int(input())
    ST = SegmentTree(N, f=f, default=set([]))

    for i, s in enumerate(S):
        ST.update(i+1, set([s]))

    for _ in range(Q):
        t, l, r = input().split()
        if int(t) == 1:
            ST.update(int(l), set([r]))
        else:
            print(len(ST.query(int(l), int(r)+1)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    # 1-indexled なので注意
    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    # 1-indexled なので注意
    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res

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

import pysnooper

#@pysnooper.snoop()
def main():
    N = int(input())
    S = input()
    Q = int(input())
    ST = SegmentTree(N, f=f, default=set([]))

    for i, s in enumerate(S):
        ST.update(i+1, set([s]))

    for _ in range(Q):
        t, l, r = input().split()
        if int(t) == 1:
            ST.update(int(l), set([r]))
        else:
            print(len(ST.query(int(l), int(r)+1)))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
q = int(input())
query_list = []
for i in range(q):
    query_list.append(list(input().split()))
for query in query_list:
    if query[0] == '1':
        s = s[:int(query[1])-1] + query[2] + s[int(query[1]):]
    elif query[0] == '2':
        print(s)
        print(len(''.join(set(s[int(query[1])-1:int(query[2])]))))

Submission status: Runtime Error

Solution code:
mod = 10 ** 9 + 7
mod2 = 2**61+1
from collections import deque
import heapq
from bisect import bisect_left, insort_left

def iip(listed):
    ret = [int(i) for i in input().split()]
    if len(ret) == 1 and not listed:
        return ret[0]
    return ret


def main():
    r = solve()
    #print(r)

def solve():
    K = iip(False)
    S = input()
    S = [ord(i) for i in S]
    Q = iip(False)

    posit = {}
    for i in range(ord("a"), ord("z")+1):
        posit[i] = []

    query = []
    for i in range(Q):
        query.append(input().split())

    for i, j in enumerate(S, 1):
        posit[j].append(i)

    result = []
    for q in query:
        if q[0] == "1":
            p = int(q[1])
            before = S[p-1]
            after = ord(q[2])
            if before == after:
                continue
            S[p-1] = after

            idx = bisect_left(posit[before], p)

            posit[before].pop(idx)
            insort_left(posit[after], p)

        else:
            l = int(q[1])
            r = int(q[2])

            ret = 0
            for i in range(ord("a"), ord("z")+1):
                ll = bisect_left(l)
                rr = bisect_left(rr)
                if ll != rr:
                    ret += 1
            result.append(ret)


    #print(S)
    #print(posit)
    split_print_space(result)

    return



#####################################################ライブラリ集ここから

def split_print_space(s):
    print(" ".join([str(i) for i in s]))


def split_print_enter(s):
    print("\n".join([str(i) for i in s]))


def koenai_saidai_x_index(sorted_list, n):
    l = 0
    r = len(sorted_list)
    if len(sorted_list) == 0:
        return False
    if sorted_list[0] > n:
        return False

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] == n:
            return x
        elif sorted_list[x] > n:
            r = x
        else:
            l = x
    return l


def searchsorted(sorted_list, n, side):
    if side not in ["right", "left"]:
        raise Exception("sideはrightかleftで指定してください")

    l = 0
    r = len(sorted_list)

    if n > sorted_list[-1]:
        # print(sorted_list)
        return len(sorted_list)
    if n < sorted_list[0]:
        return 0

    while r - l > 1:
        x = (l + r) // 2
        if sorted_list[x] > n:
            r = x
        elif sorted_list[x] < n:
            l = x
        else:
            if side == "left":
                r = x
            elif side == "right":
                l = x

    if side == "left":
        if sorted_list[l] == n:
            return r - 1
        else:
            return r

    if side == "right":
        if sorted_list[l] == n:
            return l + 1
        else:
            return l


def soinsuu_bunkai(n):
    ret = []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            n //= i
            ret.append(i)
        if i > n:
            break
    if n != 1:
        ret.append(n)
    return ret


def conbination(n, r, mod, test=False):
    if n <= 0:
        return 0
    if r == 0:
        return 1
    if r < 0:
        return 0
    if r == 1:
        return n
    ret = 1
    for i in range(n - r + 1, n + 1):
        ret *= i
        ret = ret % mod

    bunbo = 1
    for i in range(1, r + 1):
        bunbo *= i
        bunbo = bunbo % mod

    ret = (ret * inv(bunbo, mod)) % mod
    if test:
        # print(f"{n}C{r} = {ret}")
        pass
    return ret


def inv(n, mod):
    return power(n, mod - 2)


def power(n, p, mod_= mod):
    if p == 0:
        return 1
    if p % 2 == 0:
        return (power(n, p // 2, mod_) ** 2) % mod_
    if p % 2 == 1:
        return (n * power(n, p - 1, mod_)) % mod_


if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

'''
111
abcdbbdtyyuhgjhguytuhgjhguyrtyetrdhggjutftfuyfyyabcdbbdtyyuhgjhguytuhgjhguyrtyetrdhggjutftfuyfyyabcdbbdtyyuhgjh
6
2 3 6
1 5 z
2 1 50000
1 4 a
1 7 d
2 1 1000000
'''

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

from helper import elapsed_time
from bisect import bisect_left, insort_left


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

# s = s * 5000
# print()
# print(len(s))

# a-zまでの26文字に対して、s文字列の各文字に該当するindexを格納しておく
d = {i: [] for i in range(26)}
for i, c in enumerate(s):
    d[ord(c) - ord("a")].append(i)
# print(d)


@elapsed_time
def convert(d: dict, s: list, q1: int, q2: str):
    if s[q1] == q2:
        return d, s

    didx_before = ord(s[q1]) - ord("a")
    didx_after = ord(q2) - ord("a")

    idx = bisect_left(d[didx_before], q1)
    d[didx_before].pop(idx)
    s[q1] = q2
    insort_left(d[didx_after], q1)

    # return s[:q1] + q2 + s[q1+1:]
    # s[q1] = q2
    return d, s


@elapsed_time
def calc(d: dict, q1: int, q2: int):
    ans = 0
    for i in range(26):
        idx = bisect_left(d[i], q1)
        if d[i] and q1 <= d[i][-1] and d[i][idx] < q2:
            ans += 1
    '''
    st = time.time()
    temp1 = s[q1:q2 + 1]
    print(f'>>- extract: {time.time()-st}')

    st = time.time()
    temp2 = set(temp1)
    print(f'>>- to set: {time.time()-st}')
    ans = len(list(temp2))
    '''

    return ans


for _ in range(Q):
    q, q1, q2 = input().split()
    q = int(q)
    if q == 1:
        d, s = convert(d, s, int(q1) - 1, q2)
    if q == 2:
        print(calc(d, int(q1) - 1, int(q2) - 1))

Submission status: Runtime Error

Solution code:
from bisect import bisect_left, insort_left
N = int(input())
S = [c for c in input()]
Q = int(input())
d = {i: [] for i in range(26)}
for i, c in enumerate(S):
    d[ord(c) - ord("a")].append(i)

# print(d)
for _ in range(Q):
    q = input().split()
    if int(q[0]) == 1:
        iq, cq = int(q[1]), q[2]
        iq -= 1
        if S[iq] == cq:
            continue
        else:
            idx = bisect_left(d[ord(S[iq]) - ord("a")], iq)
            if 0 < len(d[iq]):
                d[iq].pop(idx)
            S[iq] = cq
            insort_left(d[ord(cq) - ord("a")], iq)
    else:
        l, r = int(q[1]), int(q[2])
        l -= 1
        ans = 0
        for i in range(26):
            idx = bisect_left(d[i], l)
            if d[i] and l <= d[i][-1] and d[i][idx] < r:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
Q = int(input())
Query = [input() for _ in range(Q)]
dic = {chr(i+ord("a")):[] for i in range(26)}
for i, s in enumerate(S):
    dic[s].append(i)
for q in Query:
    t,a,b = q.split()
    if(t == "1"):
        a_index = int(a)-1
        if(S[a_index]==b):
            continue
        tmp_index = bisect_left(dic[S[a_index]],a_index)
        dic[s[a]].pop(tmp_index)
        insort.left(dic[b],a)
        s[a] = b
    elif(t == "2"):
        a_index = int(a)-1
        b_index = int(b)-1
        cnt = 0
        for li in dic.values():
            if(li and a_index <= li[-1] and li[bisect_left(li,a_index)] <= b_index):
                    cnt += 1
        print(cnt)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
Q = int(input())
Query = [input() for _ in range(Q)]
dic = {chr(i+ord("a")):[] for i in range(26)}
for i, s in enumerate(S):
    dic[s].append(i)
for q in Query:
    t,a,b = q.split()
    if(t == "1"):
        a_index = int(a)-1
        dic[S[a_index]].remove(a_index)
        dic[b].append(a_index)
    if(t == "2"):
        a_index = int(a)-1
        b_index = int(b)-1
        cnt = 0
        for i in range(26):
            for d in dic[chr(i+ord("a"))]:
                if(a_index<=d<=b_index):
                    cnt += 1
                    break
        print(cnt)

Submission status: Runtime Error

Solution code:
from bisect import insort_left, bisect_left, bisect_right

characters = [chr(ord('a') + i) for i in range(26)]

def main():
    N = int(input())
    S = input()
    Q = int(input())

    indices_dict = {a: [] for a in characters}
    for i, s in enumerate(S):
        indices_dict[s].append(i + 1)

    for i in range(Q):
        a, b, c = input().split()
        if int(a) == 2:
            l, r = int(b), int(c)
            cnt = 0
            for c in characters:
                if len(indices_dict[c]) > 0 and \
                    l <= indices_dict[c][-1] and \
                    indices_dict[c][bisect_left(indices_dict[c], l)] <= r:
                    cnt += 1
            print(cnt)
        else:
            from_c = S[ind - 1]
            ind, to_c = int(b), c
            if from_c == to_c:
                continue
            insort_left(indices_dict[to_c], ind)
            indices_dict[from_c].pop(bisect_left(indices_dict[from_c], ind))
            S[ind] = to_c

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
class SegTree:
    def __init__(self, N, S):
        self.N = 2 ** ((N-1).bit_length())
        self.tree = [0 for i in range(self.N * 2 - 1)]
        for i in range(len(S)):
            self.tree[self.N - 1 + i] = 1 << (ord(S[i] - ord("a")))

        for i in range(self.N - 2, -1, -1):
            self.tree[i] = self.tree[i*2 + 1] | self.tree[i*2 + 2]

    def update(self, index, char):
        i = self.N - 1 + index
        # アルファベットがある = bitが立っている
        self.tree[i] = 1 << (ord(char) - ord("a"))
        while i > 0:
            i = (i-1) // 2
            self.tree[i] = self.tree[i*2 + 1] | self.tree[i*2 + 2]

    def get(self, a, b):
        return self.query(a, b, 0, 0, self.N)

    # k : ノードの番号
    # l : ノードkの受け持つ区間
    # r : ノードkの受け持つ区間
    def query(self, a, b, k, l, r):
        if r <= a or b <= l: # 区間外
            return 0
        elif a <= l and r <= b: # 受け持ち区間は完全に含まれている
            return self.tree[k]
        else: # 一部含まれてる
            left = self.query(a, b, 2 * k + 1, l, (l+r)//2)
            right = self.query(a, b, 2 * k + 2, (l+r)//2, r)
            return left | right

def solve():
    N = int(input())
    S = list(input().strip())
    tree = SegTree(N, S)

    Q = int(input())
    for _ in range(Q):
        t_q, in_1, in_2 = input().split()
        if t_q == "1":
            i_q = int(in_1)
            c_q = in_2
            tree.update(i_q-1, c_q)
        else:
            l_q = int(in_1)
            r_q = int(in_2)
            print(bin(tree.get(l_q-1, r_q)).count(1))

solve()

Submission status: Runtime Error

Solution code:
import bisect

characters = [chr(ord('a') + i) for i in range(26)]

def main():
    N = int(input())
    S = input()
    Q = int(input())

    indices_dict = {a: [] for a in characters}
    for i, s in enumerate(S):
        indices_dict[s].append(i + 1)

    for i in range(Q):
        a, b, c = input().split()
        if int(a) == 2:
            l, r = int(b), int(c)
            cnt = 0
            for c in characters:
                l_ind = bisect.bisect_left(indices_dict[c], l)
                r_ind = bisect.bisect_right(indices_dict[c], r)
                if l_ind != r_ind:
                    cnt += 1
            print(cnt)
        else:
            ind, to_c = int(b), c
            bisect.insort_left(indices_dict[to_c], ind)
            from_c = S[ind - 1]
            indices_dict[from_c].pop(bisect.bisect_left(indices_dict[from_c], ind))

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import bisect

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

def ordN(x):
  return ord(x) - ord('a')

li = [[] for _ in range(26)]
for i,s in enumerate(S):
  li[ordN(s)].append(i)

for i in range(int(input())):
  Q1, Q2, Q3 = input().split()
  if Q1 == "1":
    Q2 = int(Q2) - 1
    if S[Q2] != Q3:
      I = bisect.bisect(li[ordN(S[Q2])], Q2)
      li[ordN(S[Q2])].pop(I)
      bisect.insort(li[ordN(Q3)], Q2)
      S[Q2] = Q3
  else:
    Q2, Q3 = int(Q2)-1, int(Q3)-1
    count = 0
    for j in range(26):
      I = bisect.bisect_left(li[j], Q2)
      if I < len(li[j]) and li[j][I] <= Q3:
        count += 1
    print(count)

Submission status: Runtime Error

Solution code:
import bisect

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

def ordN(x):
  return ord(x) - ord('a')

li = [[] for _ in range(26)]
for i,s in enumerate(S):
  li[ordN(s)].append(i)

for i in range(int(input())):
  Q1, Q2, Q3 = input().split()
  if Q1 == "1":
    Q2 = int(Q2) - 1
    if S[Q2] != Q3:
      I = bisect.bisect(li[ordN(S[Q2])])
      li[ordN(S[Q2])].pop(I)
      bisect.insort(li[ordN(Q3)], Q2)
      S[Q2] = Q3
  else:
    Q2, Q3 = int(Q2)-1, int(Q3)-1
    count = 0
    for j in range(26):
      I = bisect.bisect_left(li[j], Q2)
      if I < len(li[j]) and li[j][I] <= Q3:
        count += 1
    print(count)

Submission status: Runtime Error

Solution code:
import sys
def input():
	return sys.stdin.buffer.readline()[:-1]
n = int(input())
ss = list(input())
q = int(input())
s = []
for i in range(len(ss)):
    a = ord(ss[i])-97
    s.append(a)
#print(s) #test
h = 0
nn = n
while nn:
    nn //= 2
    h += 1

seg = [[0 for _ in range(26)] for _ in range((2**(h+1))-1)]
for i in range(2**h-1, n-1+2**h):
    nl = [i] #所属するsegの番号リスト
    y = i
    for j in range(h):
        y = (y-1)//2
        nl.append(y) #nl完成
    for k in nl:
        seg[k][s[i-2**h+1]] += 1

for _ in range(q):
    bs, cs, ds = input().split()
    b = int(bs)
    c = int(cs)
    if b == 1:
        #print("クエリ1処理開始") #test
        f = ord(ds)-97
        x = c + 2**h - 2
        cl = [x]
        for j in range(h):
            x = (x-1)//2
            cl.append(x)
        #print(cl) #test
        #print(c) #test
        #print(s[c-1]) #test
        for k in cl:
            seg[k][s[c-1]] -= 1
            seg[k][f] += 1
        #print(seg) #test
    else:
        #print("クエリ2処理開始") #test
        d = int(ds)
        C = 2**h + c - 1
        D = 2**h + d
        LI = [] #敷居リスト
        t = C
        u = 1
        jud = False
        while True:
            if t * u == D:
                break
            elif t%2 != 0:
                if (t+1) * u <= D:
                    LI.append(t)
                    t += 1
                else:
                    t *= 2
                    u //= 2
            else:
                if (t+2) * u <= D:
                    t //= 2
                    u *= 2
                elif (t+1) * u <= D:
                    LI.append(t)
                    t += 1
                else:
                    t *= 2
                    u //= 2
        #print(LI)
        sumlist = [0 for _ in range(26)] #範囲内の個数
        for sh in LI:
            sh -= 1
            for j in range(26):
                sumlist[j] += seg[sh][j]
        #print(sumlist)
        ans = 0
        for numbers in sumlist:
            if numbers != 0:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.buffer.readline()[:-1]
n = int(input())
ss = list(input())
q = int(input())
s = []
for i in range(len(ss)):
    a = ord(ss[i])-97
    s.append(a)
#print(s) #test
h = 0
nn = n
while nn:
    nn //= 2
    h += 1

seg = [[0 for _ in range(26)] for _ in range((2**(h+1))-1)]
for i in range(2**h-1, n-1+2**h):
    nl = [i] #所属するsegの番号リスト
    y = i
    for j in range(h):
        y = (y-1)//2
        nl.append(y) #nl完成
    for k in nl:
        seg[k][s[i-2**h+1]] += 1

for _ in range(q):
    bs, cs, ds = input().split()
    b = int(bs)
    c = int(cs)
    if b == 1:
        #print("クエリ1処理開始") #test
        f = ord(ds)-97
        x = c + 2**h - 2
        cl = [x]
        for j in range(h):
            x = (x-1)//2
            cl.append(x)
        #print(cl) #test
        #print(c) #test
        #print(s[c-1]) #test
        for k in cl:
            seg[k][s[c-1]] -= 1
            seg[k][f] += 1
        #print(seg) #test
    else:
        #print("クエリ2処理開始") #test
        d = int(ds)
        C = 2**h + c - 1
        D = 2**h + d
        LI = [] #敷居リスト
        t = C
        u = 1
        jud = False
        while True:
            if t * u == D:
                break
            elif t%2 != 0:
                if (t+1) * u <= D:
                    LI.append(t)
                    t += 1
                else:
                    t *= 2
                    u //= 2
            else:
                if (t+2) * u <= D:
                    t //= 2
                    u *= 2
                elif (t+1) * u <= D:
                    LI.append(t)
                    t += 1
                else:
                    t *= 2
                    u //= 2
        #print(LI)
        sumlist = [0 for _ in range(26)] #範囲内の個数
        for sh in LI:
            sh -= 1
            for j in range(26):
                sumlist[j] += seg[sh][j]
        #print(sumlist)
        ans = 0
        for numbers in sumlist:
            if numbers != 0:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
def input():
    sys.stdin.buffer.readline()[:-1]
n = int(input())
ss = list(input())
q = int(input())
s = []
for i in range(len(ss)):
    a = ord(ss[i])-97
    s.append(a)
#print(s) #test
h = 0
nn = n
while nn:
    nn //= 2
    h += 1

seg = [[0 for _ in range(26)] for _ in range((2**(h+1))-1)]
for i in range(2**h-1, n-1+2**h):
    nl = [i] #所属するsegの番号リスト
    y = i
    for j in range(h):
        y = (y-1)//2
        nl.append(y) #nl完成
    for k in nl:
        seg[k][s[i-2**h+1]] += 1

for _ in range(q):
    bs, cs, ds = input().split()
    b = int(bs)
    c = int(cs)
    if b == 1:
        #print("クエリ1処理開始") #test
        f = ord(ds)-97
        x = c + 2**h - 2
        cl = [x]
        for j in range(h):
            x = (x-1)//2
            cl.append(x)
        #print(cl) #test
        #print(c) #test
        #print(s[c-1]) #test
        for k in cl:
            seg[k][s[c-1]] -= 1
            seg[k][f] += 1
        #print(seg) #test
    else:
        #print("クエリ2処理開始") #test
        d = int(ds)
        C = 2**h + c - 1
        D = 2**h + d
        LI = [] #敷居リスト
        t = C
        u = 1
        jud = False
        while True:
            if t * u == D:
                break
            elif t%2 != 0:
                if (t+1) * u <= D:
                    LI.append(t)
                    t += 1
                else:
                    t *= 2
                    u //= 2
            else:
                if (t+2) * u <= D:
                    t //= 2
                    u *= 2
                elif (t+1) * u <= D:
                    LI.append(t)
                    t += 1
                else:
                    t *= 2
                    u //= 2
        #print(LI)
        sumlist = [0 for _ in range(26)] #範囲内の個数
        for sh in LI:
            sh -= 1
            for j in range(26):
                sumlist[j] += seg[sh][j]
        #print(sumlist)
        ans = 0
        for numbers in sumlist:
            if numbers != 0:
                ans += 1
        print(ans)