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: Wrong Answer

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def _get(T, a, b, k, l, r):
    if r <= a or b <= l:
        return set()

    if a <= l and r <= b:
        return T[k]
    else:
        s1 = _get(T, a, b, 2 * k + 1, l, (l + r) // 2)
        s2 = _get(T, a, b, 2 * k + 2, (l + r) // 2, r)
        return s1.union(s2)


def get(T, d, a, b):
    return _get(T, a, b, 0, 0, 2 ** d)


def main():
    N = int(input())
    S = input().strip()
    Q = [input().strip().split() for _ in range(int(input()))]
    d = N.bit_length()
    T = [set() for _ in range(2 ** (d + 1) - 1)]
    for i, s in enumerate(S):
        T[i + 2 ** d - 1].add(s)
    for i in range(2 ** d - 2, -1, -1):
        T[i] =T[2 * i + 1] .union(T[2 * i + 2])

    for s, a, b in Q:
        if s == "1":
            a = int(a) - 1
            i = a + 2 ** d - 1
            T[i] = {b}
            while i > 0:
                i //= 2
                T[i] = T[2 * i + 1] .union(T[2 * i + 2])
        elif s == "2":
            a = int(a) - 1
            b = int(b) - 1
            print(len(get(T, d, a, b + 1)))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def _get(T, a, b, k, l, r):
    if r <= a or b <= l:
        return set()

    if a <= l and r <= b:
        return T[k]
    else:
        s1 = _get(T, a, b, 2 * k + 1, l, (l + r) // 2)
        s2 = _get(T, a, b, 2 * k + 2, (l + r) // 2, r)
        return s1 | s2


def get(T, d, a, b):
    return _get(T, a, b, 0, 0, 2 ** d)


def main():
    N = int(input())
    S = input().strip()
    Q = [input().strip().split() for _ in range(int(input()))]
    d = N.bit_length()
    T = [set() for _ in range(2 ** (d + 1) - 1)]
    for i, s in enumerate(S):
        T[i + 2 ** d - 1].add(s)
    for i in range(2 ** d - 2, -1, -1):
        T[i] = T[2 * i + 1] | T[2 * i + 2]

    for s, a, b in Q:
        if s == "1":
            a = int(a) - 1
            i = a + 2 ** d - 1
            T[i] = {b}
            while i > 0:
                i //= 2
                T[i] = T[2 * i + 1] | T[2 * i + 2]
        elif s == "2":
            a = int(a) - 1
            b = int(b) - 1
            print(len(get(T, d, a, b + 1)))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
# ----- BIT -----
class Bit:
    """ used for only int(>=0) 
        1-indexed (ignore 0-index)
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

    def get_less_than_x_cnt(self, x):
        """ 累積和がx未満 の個数 """
        lb_pos, lb_sum = self.lower_bound(x)
        return lb_pos-1

    def get_less_than_and_x_cnt(self, x):
        """ 累積和がx以下 の個数 """
        lb_pos, lb_sum = self.lower_bound(x+1)
        return lb_pos-1
    
    def get_more_than_x_cnt(self, x):
        """ 累積和がxより大きい 個数 """
        return self.size - self.get_less_than_and_x_cnt(x)


def main():
    n = int(input())
    s = list(input())
    q = int(input())
    alps = 'abcdefghijklmnopqrstuvwxyz'

    
    alp_d = {chr(ord('a') + i): Bit(n) for i in range(26)}
    for i,si in enumerate(s):
        alp_d[si].add(i+1,1) 

    ansl = []
    for i in range(q):
        com,a,b = map(str, input().split())
        if com == '1':
            i,c = int(a),b
            si = s[i-1]
            alp_d[si].add(i, -1)
            alp_d[c].add(i, 1)
        else:
            l,r = int(a),int(b)
            ans = 0
            for alp in alps:
                cnt = alp_d[alp].sum(r) - alp_d[alp].sum(l-1)
                if cnt > 0:
                    ans+=1
            ansl.append(ans)

    for a in ansl:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def _get(T, a, b, k, l, r):
    if r <= a or b <= l:
        return set()

    if a <= l and r <= b:
        return T[k]
    else:
        s1 = _get(T, a, b, 2 * k + 1, l, (l + r) // 2)
        s2 = _get(T, a, b, 2 * k + 2, (l + r) // 2, r)
        return s1.union(s2)


def get(T, d, a, b):
    return _get(T, a, b, 0, 0, 2 ** d)


def main():
    N = int(input())
    S = input().strip()
    Q = [input().strip().split() for _ in range(int(input()))]
    d = N.bit_length()
    T = [set() for _ in range(2 ** (d + 1) - 1)]
    for i, s in enumerate(S):
        T[i + 2 ** d - 1].add(s)
    for i in range(2 ** d - 2, -1, -1):
        T[i] = T[2 * i + 1].union(T[2 * i + 2])

    for s, a, b in Q:
        if s == "1":
            a = int(a) - 1
            i = a + 2 ** d - 1
            T[i] = {b}
            while i > 0:
                i //= 2
                T[i] = T[2 * i + 1].union(T[2 * i + 2])
        elif s == "2":
            a = int(a) - 1
            b = int(b) - 1
            print(len(get(T, d, a, b + 1)))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def _get(T, a, b, k, l, r):
    if r <= a or b <= l:
        return set()

    if a <= l and r <= b:
        return T[k]
    else:
        s1 = _get(T, a, b, 2 * k + 1, l, (l + r) // 2)
        s2 = _get(T, a, b, 2 * k + 2, (l + r) // 2, r)
        return s1.union(s2)


def get(T, N, a, b):
    return _get(T, a, b, 0, 0, N)


def main():
    N = int(input())
    S = input().strip()
    Q = [input().strip().split() for _ in range(int(input()))]
    d = N.bit_length()
    T = [set() for _ in range(2 ** (d + 1) - 1)]
    for i, s in enumerate(S):
        T[i + 2 ** d - 1].add(s)
    for i in range(2 ** d - 2, -1, -1):
        T[i] = T[2 * i + 1].union(T[2 * i + 2])

    for s, a, b in Q:
        if s == "1":
            a = int(a) - 1
            i = a + 2 ** d - 1
            T[i] = {b}
            while i > 0:
                i //= 2
                T[i] = T[2 * i + 1].union(T[2 * i + 2])
        elif s == "2":
            a = int(a) - 1
            b = int(b) - 1
            print(len(get(T, N, a, b + 1)))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def _get(T, a, b, k, l, r):
    if r <= a or b <= l:
        return set()

    if a <= l and r <= b:
        return T[k]
    else:
        s1 = _get(T, a, b, 2 * k + 1, l, (l + r) // 2)
        s2 = _get(T, a, b, 2 * k + 2, (l + r) // 2, r)
        return s1.union(s2)


def get(T, a, b):
    return _get(T, a, b, 0, 0, (len(T) + 1) // 2)


def main():
    N = int(input())
    S = input().strip()
    Q = [input().strip().split() for _ in range(int(input()))]
    d = N.bit_length()
    T = [set() for _ in range(2 ** (d + 1) - 1)]
    for i, s in enumerate(S):
        T[i + 2 ** d - 1].add(s)
    for i in range(2 ** d - 2, -1, -1):
        T[i] = T[2 * i + 1].union(T[2 * i + 2])

    for s, a, b in Q:
        if s == "1":
            a = int(a) - 1
            i = a + 2 ** d - 1
            T[i] = {b}
            while i > 0:
                i //= 2
                T[i] = T[2 * i + 1].union(T[2 * i + 2])
        elif s == "2":
            a = int(a) - 1
            b = int(b) - 1
            print(len(get(T, a, b + 1)))

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

# nodeをリストに変換したらクソ遅かった

import pprint

class BalancingTree:
    def __init__(self, n):
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def __str__(self):
        def debug_info(nd):
            return (nd.value - 1, nd.left.value - 1 if nd.left else None, nd.right.value - 1 if nd.right else None)

        def debug_node(nd):
            v = debug_info(nd) if nd.value else ()
            left = debug_node(nd.left) if nd.left else []
            right = debug_node(nd.right) if nd.right else []
            return [v, left, right]

        return pprint.PrettyPrinter(indent=4).pformat(debug_node(self.root))

    __repr__ = __str__

    def append(self, v):# v を追加（その時点で v はない前提）
        v += 1
        nd = self.root
        while True:
            # v がすでに存在する場合に何か処理が必要ならここに書く
            if v == nd.value:
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        return self.leftmost(nd.left) if nd.left else nd

    def rightmost(self, nd):
        return self.rightmost(nd.right) if nd.right else nd

    def find_l(self, v): # vより真に小さいやつの中での最大値（なければ-1）
        v += 1
        nd = self.root
        prev = nd.value if nd.value < v else 0
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v): # vより真に大きいやつの中での最小値（なければRoot）
        v += 1
        nd = self.root
        prev = nd.value if nd.value > v else 0
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def max(self):
        return self.find_l((1<<self.N)-1)

    def min(self):
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None): # 値がvのノードがあれば削除（なければ何もしない）
        v += 1
        if not nd:
            nd = self.root
        if not prev:
            prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    # v以下のものの中での最大値
    def upper_bound(self, v):
        upper = self.find_r(v)
        return self.find_l(upper)

    def lower_bound(self, v):
        lower = self.find_l(v)
        return self.find_r(lower)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

def main():
    N = I()
    s = S()
    Q = I()
    query = LR(Q)

    trees = {ch: BalancingTree(25) for ch in alphabets}

    for i, ch in enumerate(s):
        trees[ch].append(i)

    for q in query:
        if q[0] == "1":
            _, i, c = q
            i = int(i) - 1
            prev = s[i]
            trees[prev].delete(i)
            trees[c].append(i)
        else:
            _, l, r = q
            l, r = int(l) - 1, int(r) - 1
            count = 0
            for _, tree in trees.items():
                first = tree.lower_bound(l)
                if first != tree.root.value - 1 and first <= r:
                    count += 1
            print(count)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

# nodeをリストに変換したらクソ遅かった

import pprint

class BalancingTree:
    def __init__(self, n):
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def __str__(self):
        def debug_info(nd):
            return (nd.value - 1, nd.left.value - 1 if nd.left else None, nd.right.value - 1 if nd.right else None)

        def debug_node(nd):
            v = debug_info(nd) if nd.value else ()
            left = debug_node(nd.left) if nd.left else []
            right = debug_node(nd.right) if nd.right else []
            return [v, left, right]

        return pprint.PrettyPrinter(indent=4).pformat(debug_node(self.root))

    __repr__ = __str__

    def append(self, v):# v を追加（その時点で v はない前提）
        v += 1
        nd = self.root
        while True:
            # v がすでに存在する場合に何か処理が必要ならここに書く
            if v == nd.value:
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        return self.leftmost(nd.left) if nd.left else nd

    def rightmost(self, nd):
        return self.rightmost(nd.right) if nd.right else nd

    def find_l(self, v): # vより真に小さいやつの中での最大値（なければ-1）
        v += 1
        nd = self.root
        prev = nd.value if nd.value < v else 0
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v): # vより真に大きいやつの中での最小値（なければRoot）
        v += 1
        nd = self.root
        prev = nd.value if nd.value > v else 0
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def max(self):
        return self.find_l((1<<self.N)-1)

    def min(self):
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None): # 値がvのノードがあれば削除（なければ何もしない）
        v += 1
        if not nd:
            nd = self.root
        if not prev:
            prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    # v以下のものの中での最大値
    def upper_bound(self, v):
        upper = self.find_r(v)
        return self.find_l(upper)

    def lower_bound(self, v):
        lower = self.find_l(v)
        return self.find_r(lower)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

def main():
    N = I()
    s = S()
    Q = I()
    query = LR(Q)

    trees = {ch: BalancingTree(20) for ch in alphabets}

    for i, ch in enumerate(s):
        trees[ch].append(i)



    for q in query:
        if q[0] == "1":
            _, i, c = q
            i = int(i) - 1
            prev = s[i]
            trees[prev].delete(i)
            trees[c].append(i)
        else:
            _, l, r = q
            l, r = int(l) - 1, int(r) - 1
            count = 0
            for ch, tree in trees.items():
                first = tree.lower_bound(l)
                if first != tree.root.value - 1 and first <= r:
                    count += 1
            print(count)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
#!usr/bin/env python3
from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def S(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

alphabets = "abcdefghijklmnopqrstuvwxyz"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007

# nodeをリストに変換したらクソ遅かった

import pprint

class BalancingTree:
    def __init__(self, n):
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def __str__(self):
        def debug_info(nd):
            return (nd.value - 1, nd.left.value - 1 if nd.left else None, nd.right.value - 1 if nd.right else None)

        def debug_node(nd):
            v = debug_info(nd) if nd.value else ()
            left = debug_node(nd.left) if nd.left else []
            right = debug_node(nd.right) if nd.right else []
            return [v, left, right]

        return pprint.PrettyPrinter(indent=4).pformat(debug_node(self.root))

    __repr__ = __str__

    def append(self, v):# v を追加（その時点で v はない前提）
        v += 1
        nd = self.root
        while True:
            # v がすでに存在する場合に何か処理が必要ならここに書く
            if v == nd.value:
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        return self.leftmost(nd.left) if nd.left else nd

    def rightmost(self, nd):
        return self.rightmost(nd.right) if nd.right else nd

    def find_l(self, v): # vより真に小さいやつの中での最大値（なければ-1）
        v += 1
        nd = self.root
        prev = nd.value if nd.value < v else 0
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v): # vより真に大きいやつの中での最小値（なければRoot）
        v += 1
        nd = self.root
        prev = nd.value if nd.value > v else 0
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def max(self):
        return self.find_l((1<<self.N)-1)

    def min(self):
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None): # 値がvのノードがあれば削除（なければ何もしない）
        v += 1
        if not nd:
            nd = self.root
        if not prev:
            prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    # v以下のものの中での最大値
    def upper_bound(self, v):
        upper = self.find_r(v)
        return self.find_l(upper)

    def lower_bound(self, v):
        lower = self.find_l(v)
        return self.find_r(lower)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

def main():
    N = I()
    s = S()
    Q = I()
    query = LR(Q)

    trees = {ch: BalancingTree(20) for ch in alphabets}

    for i, ch in enumerate(s):
        trees[ch].append(i)



    for q in query:
        if q[0] == "1":
            _, i, c = q
            i = int(i) - 1
            prev = s[i]
            trees[prev].delete(i)
            trees[c].append(i)
        else:
            _, l, r = q
            l, r = int(l) - 1, int(r) - 1
            count = 0
            for ch, tree in trees.items():
                first = tree.lower_bound(l)
                if first != tree.root.value and first <= r:
                    count += 1
            print(count)



if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque
import bisect
import copy
import heapq
import itertools
import math
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
mod = 10 ** 9 + 7

def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


def _get(T, a, b, k, l, r):
    if r <= a or b <= l:
        return set()

    if a <= l and r <= b:
        return T[k]
    else:
        s1 = _get(T, a, b, 2 * k + 1, l, (l + r) // 2)
        s2 = _get(T, a, b, 2 * k + 2, (l + r) // 2, r)
        return s1.union(s2)


def get(T, a, b):
    return _get(T, a, b, 0, 0, (len(T) + 1) // 2)


def main():
    N = int(input())
    S = input().strip()
    Q = [input().strip().split() for _ in range(int(input()))]
    d = N.bit_length()
    T = [set() for _ in range(2 ** (d + 1) - 1)]
    for i, s in enumerate(S):
        T[i + 2 ** d - 1].add(s)
    for i in range(2 ** d - 2, -1, -1):
        T[i] = T[2 * i + 1].union(T[2 * i + 2])

    for s, a, b in Q:
        if s == "1":
            a = int(a) - 1
            T[a + 2 ** d - 1] = {b}
            while a > 0:
                a //= 2
                T[a] = T[2 * a + 1].union(T[2 * a + 2])
        elif s == "2":
            a = int(a) - 1
            b = int(b) - 1
            print(len(get(T, a, b + 1)))


if __name__ == "__main__":
    main()