Problem: 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).

Submission attempts (in order):
# -*- coding: utf-8 -*-





# from helper import elapsed_time
from bisect import bisect_left, insort_left


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


# print()
# print(len(s))


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 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))


# -*- coding: utf-8 -*-





from helper import elapsed_time
from bisect import bisect_left, insort_left


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


# print()
# print(len(s))


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 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))


# -*- coding: utf-8 -*-



# from helper import elapsed_time
from bisect import bisect_left, insort_left


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


d = {i: [] for i in range(26)}
for i, c in enumerate(s):
    d[ord(c) - ord("a")].append(i)


# @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 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 + 1:
            ans += 1

    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))


Verdicts: Wrong Answer

Runtime Error

Accepted