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:
# import bisect
# import heapq
# from copy import deepcopy
from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
# mod = 10**9 + 7

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

# n, k = map(int, input().split())
# a = list(map(int, input().split()))

for i in range(n):
    s[i] = ord(s[i]) - ord('a')

for i in range(q):
    n,l,r = input().split()
    if n == '1':
        s[int(l)-1] = ord(r) - ord('a')

    else:
        seen = [False] * 28
        count = 0
        for i in range(int(l)-1, int(r)):
            if not seen[s[i]]:
                seen[s[i]] = True
                count += 1

        print(count)

Submission status: Time Limit Exceeded

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

import sys

DEBUG = False

class SegmentTree:

    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.nodes = [0 for _ in range(self.n * 2)]
    
    def update(self, idx, val):
        nodes = self.nodes

        idx += self.n - 1
        if nodes[idx] == val:
            return

        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = nodes[idx * 2 + 1] | nodes[idx * 2 + 2]
    
    def _query(self, l, r, scope_idx, scope_l, scope_r):
        if r <= scope_l or l >= scope_r:
            return 0
        if l <= scope_l and r >= scope_r:
            return self.nodes[scope_idx]
        vl = self._query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
        vr = self._query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
        return vl | vr
    
    def query(self, l, r):
        return self._query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    read()
    s = read()

    a_ord = ord("a")
    bit_offsets = {chr(c_ord): c_ord - a_ord for c_ord in range(ord("a"), ord("z") + 1)}

    apps = SegmentTree(len(s))
    i = 0
    for c in s:
        apps.update(i, 1 << bit_offsets[c])
        i += 1

    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.update(int(i) - 1, 1 << bit_offsets[c])
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(bin(apps.query(int(l) - 1, int(r) - 1 + 1)).count("1"))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

DEBUG = False

class SegmentTree:

    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.nodes = [0 for _ in range(self.n * 2)]
    
    def update(self, idx, val):
        nodes = self.nodes

        idx += self.n - 1
        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = nodes[idx * 2 + 1] | nodes[idx * 2 + 2]
    
    def _query(self, l, r, scope_idx, scope_l, scope_r):
        if r <= scope_l or l >= scope_r:
            return 0
        if l <= scope_l and r >= scope_r:
            return self.nodes[scope_idx]
        vl = self._query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
        vr = self._query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
        return vl | vr
    
    def query(self, l, r):
        return self._query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    read()
    s = read()

    a_ord = ord("a")
    bit_offsets = {chr(c_ord): c_ord - a_ord for c_ord in range(ord("a"), ord("z") + 1)}

    apps = SegmentTree(len(s))
    i = 0
    for c in s:
        apps.update(i, 1 << bit_offsets[c])
        i += 1

    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.update(int(i) - 1, 1 << bit_offsets[c])
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(bin(apps.query(int(l) - 1, int(r) - 1 + 1)).count("1"))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

DEBUG = False

class SegmentTree:

    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.fillval = 0
        self.nodes = [0] * (2 * self.n)
    
    def update(self, idx, val):
        nodes = self.nodes

        idx += self.n - 1
        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = nodes[idx * 2 + 1] | nodes[idx * 2 + 2]
    
    def _query(self, l, r, scope_idx, scope_l, scope_r):
        if r <= scope_l or l >= scope_r:
            return 0
        if l <= scope_l and r >= scope_r:
            return self.nodes[scope_idx]
        vl = self._query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
        vr = self._query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
        return vl | vr
    
    def query(self, l, r):
        return self._query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    read()
    s = read()

    apps = SegmentTree(len(s))
    i = 0
    for c in s:
        bit = ord(c) - ord("a")
        apps.update(i, 1 << bit)
        i += 1

    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            bit = ord(c) - ord("a")
            apps.update(int(i) - 1, 1 << bit)
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(bin(apps.query(int(l) - 1, int(r) - 1 + 1)).count("1"))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

DEBUG = False

class SegmentTree:

    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.fillval = 0
        self.nodes = [0] * (2 * self.n)
    
    def update(self, idx, val):
        nodes = self.nodes

        idx += self.n - 1
        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = nodes[idx * 2 + 1] | nodes[idx * 2 + 2]
    
    
    def query(self, l, r):
        fillval = self.fillval
        nodes = self.nodes
        
        def _query(l, r, scope_idx, scope_l, scope_r):
            if r <= scope_l or l >= scope_r:
                return fillval
            if l <= scope_l and r >= scope_r:
                return nodes[scope_idx]
            vl = _query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
            vr = _query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
            return vl | vr

        return _query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    read()
    s = read()

    apps = SegmentTree(len(s))
    i = 0
    for c in s:
        bit = ord(c) - ord("a")
        apps.update(i, 1 << bit)
        i += 1

    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            bit = ord(c) - ord("a")
            apps.update(int(i) - 1, 1 << bit)
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(bin(apps.query(int(l) - 1, int(r) - 1 + 1)).count("1"))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

DEBUG = False

class SegmentTree:

    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.fillval = 0
        self.nodes = [0 for _ in range(2 * self.n)]
    
    def update(self, idx, val):
        nodes = self.nodes

        idx += self.n - 1
        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = nodes[idx * 2 + 1] | nodes[idx * 2 + 2]
    
    
    def query(self, l, r):
        fillval = self.fillval
        nodes = self.nodes
        
        def _query(l, r, scope_idx, scope_l, scope_r):
            if r <= scope_l or l >= scope_r:
                return fillval
            if l <= scope_l and r >= scope_r:
                return nodes[scope_idx]
            vl = _query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
            vr = _query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
            return vl | vr

        return _query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

class LetterAppearance:
    def __init__(self, chars):
        self.chars_app = SegmentTree(len(chars))
        for i in range(0, len(chars)):
            bit = ord(chars[i]) - ord("a")
            self.chars_app.update(i, 1 << bit)
    
    def replace(self, pos, char):
        bit = ord(char) - ord("a")
        self.chars_app.update(pos, 1 << bit)

    def query(self, l, r):
        return bin(self.chars_app.query(l, r)).count("1")


def main():
    read()
    s = read()
    apps = LetterAppearance(s)
    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.replace(int(i) - 1, c)
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(apps.query(int(l) - 1, int(r) - 1 + 1))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

DEBUG = False

class SegmentTree:

    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.fillval = set()
        self.nodes = [set() for _ in range(2 * self.n)]
    
    def update(self, idx, val):
        nodes = self.nodes

        idx += self.n - 1
        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = nodes[idx * 2 + 1] | nodes[idx * 2 + 2]
    
    
    def query(self, l, r):
        fillval = self.fillval
        nodes = self.nodes
        
        def _query(l, r, scope_idx, scope_l, scope_r):
            if r <= scope_l or l >= scope_r:
                return fillval
            if l <= scope_l and r >= scope_r:
                return nodes[scope_idx]
            vl = _query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
            vr = _query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
            return vl | vr

        return _query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

class LetterAppearance:
    def __init__(self, chars):
        self.chars_app = SegmentTree(len(chars))
        for i in range(0, len(chars)):
            self.chars_app.update(i, set([chars[i]]))
    
    def replace(self, pos, char):
        self.chars_app.update(pos, set([char]))

    def query(self, l, r):
        return len(self.chars_app.query(l, r))


def main():
    read()
    s = read()
    apps = LetterAppearance(s)
    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.replace(int(i) - 1, c)
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(apps.query(int(l) - 1, int(r) - 1 + 1))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

DEBUG = False

class SegmentTree:

    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.fillval = set()
        self.nodes = [self.fillval] * (self.n * 2 - 1)
    
    def update(self, idx, val):
        nodes = self.nodes

        idx += self.n - 1
        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = nodes[idx * 2 + 1] | nodes[idx * 2 + 2]
    
    
    def query(self, l, r):
        fillval = self.fillval
        nodes = self.nodes
        
        def _query(l, r, scope_idx, scope_l, scope_r):
            if r <= scope_l or l >= scope_r:
                return fillval
            if l <= scope_l and r >= scope_r:
                return nodes[scope_idx]
            vl = _query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
            vr = _query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
            return vl | vr

        return _query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

class LetterAppearance:
    def __init__(self, chars):
        self.chars_app = SegmentTree(len(chars))
        for i in range(0, len(chars)):
            self.chars_app.update(i, set([chars[i]]))
    
    def replace(self, pos, char):
        self.chars_app.update(pos, set([char]))

    def query(self, l, r):
        return len(self.chars_app.query(l, r))


def main():
    read()
    s = read()
    apps = LetterAppearance(s)
    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.replace(int(i) - 1, c)
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(apps.query(int(l) - 1, int(r) - 1 + 1))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

import sys

DEBUG = False

class SegmentTree:
    def __init__(self, n, merge_func, fillval=sys.maxsize):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.nodes = [fillval] * (self.n * 2 - 1)
        self.merge_func = merge_func
        self.fillval = fillval
    
    def update(self, idx, val):
        nodes = self.nodes
        mergef = self.merge_func

        idx += self.n - 1
        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = mergef(nodes[idx * 2 + 1], nodes[idx * 2 + 2])
    
    
    def query(self, l, r):
        fillval = self.fillval
        nodes = self.nodes
        mergef = self.merge_func
        
        def _query(l, r, scope_idx, scope_l, scope_r):
            if r <= scope_l or l >= scope_r:
                return fillval
            if l <= scope_l and r >= scope_r:
                return nodes[scope_idx]
            vl = _query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
            vr = _query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
            return mergef(vl, vr)

        return _query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

class LetterAppearance:
    def __init__(self, chars):
        self.chars = chars
        self.chars_app = SegmentTree(len(chars), lambda x, y: x.union(y), set())
        for i in range(0, len(chars)):
            self.chars_app.update(i, set([chars[i]]))
    
    def replace(self, pos, char):
        if self.chars[pos] == char:
            return
        self.chars_app.update(pos, set([char]))
        self.chars[pos] = char

    def query(self, l, r):
        return len(self.chars_app.query(l, r))


def main():
    read()
    s = read()
    apps = LetterAppearance(list(s))
    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.replace(int(i) - 1, c)
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(apps.query(int(l) - 1, int(r) - 1 + 1))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

DEBUG = False

class SegmentTree:
    def __init__(self, n, merge_func, fillval=sys.maxsize):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.nodes = [fillval] * (self.n * 2 - 1)
        self.merge_func = merge_func
        self.fillval = fillval
    
    def update(self, idx, val):
        idx += self.n - 1
        self.nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            self.nodes[idx] = self.merge_func(self.nodes[idx * 2 + 1], self.nodes[idx * 2 + 2])
    
    def _query(self, l, r, scope_idx, scope_l, scope_r):
        if r <= scope_l or l >= scope_r:
            return self.fillval
        if l <= scope_l and r >= scope_r:
            return self.nodes[scope_idx]
        vl = self._query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
        vr = self._query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
        return self.merge_func(vl, vr)
    
    def query(self, l, r):
        return self._query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

class LetterAppearance:
    def __init__(self, chars):
        self.chars = chars
        self.chars_app = SegmentTree(len(chars), lambda x, y: x.union(y), set())
        for i in range(0, len(chars)):
            self.chars_app.update(i, set([chars[i]]))
    
    def replace(self, pos, char):
        if self.chars[pos] == char:
            return
        self.chars_app.update(pos, set([char]))
        self.chars[pos] = char

    def query(self, l, r):
        return len(self.chars_app.query(l, r))


def main():
    read()
    s = read()
    apps = LetterAppearance(list(s))
    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.replace(int(i) - 1, c)
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(apps.query(int(l) - 1, int(r) - 1 + 1))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys

DEBUG = False

class SegmentTree:
    def __init__(self, n, merge_func, fillval=sys.maxsize):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.nodes = [fillval] * (self.n * 2 - 1)
        self.merge_func = merge_func
        self.fillval = fillval
    
    def update(self, idx, val):
        idx += self.n - 1
        self.nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            self.nodes[idx] = self.merge_func(self.nodes[idx * 2 + 1], self.nodes[idx * 2 + 2])
    
    def _query(self, l, r, scope_idx, scope_l, scope_r):
        if r <= scope_l or l >= scope_r:
            return self.fillval
        if l <= scope_l and r >= scope_r:
            return self.nodes[scope_idx]
        vl = self._query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
        vr = self._query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
        return self.merge_func(vl, vr)
    
    def query(self, l, r):
        return self._query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

class LetterAppearance:
    def __init__(self, chars):
        self.chars = chars
        self.chars_app = {}
        for c_ord in range(ord("a"), ord("z") + 1):
            c = chr(c_ord)
            self.chars_app[c] = SegmentTree(len(chars), lambda x, y: max([x, y]), 0)
        for i in range(0, len(chars)):
            c = chars[i]
            self.chars_app[c].update(i, 1)
    
    def replace(self, pos, char):
        if self.chars[pos] == char:
            return
        self.chars_app[self.chars[pos]].update(pos, 0)
        self.chars_app[char].update(pos, 1)
        self.chars[pos] = char

    def query(self, l, r):
        return sum((self.chars_app[chr(c_ord)].query(l, r) for c_ord in range(ord("a"), ord("z") + 1)))


def main():
    read()
    s = read()
    apps = LetterAppearance(list(s))
    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.replace(int(i) - 1, c)
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(apps.query(int(l) - 1, int(r) - 1 + 1))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
def query1(S,iq,cq):
    S_list=list(S)
    S_list[iq-1]=cq
    S="".join(S_list)
    return S

def query2(S,lq,rq):
    chosen=list(set(S[lq-1:rq]))
    return len(chosen)

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

    query_list=[]
    for n in range(Q):
        task=input().strip().split()
        if task[0]=="1":
            task[1]=int(task[1])
        elif task[0]=="2":
            task[1]=int(task[1])
            task[2]=int(task[2])
        query_list.append(task)

    #execute
    for n in range(Q):
        if query_list[n][0]=="1":
            S=query1(S,query_list[n][1],query_list[n][2])
        elif query_list[n][0]=="2":
            print(query2(S,query_list[n][1],query_list[n][2]))

main()

Submission status: Time Limit Exceeded

Solution code:
import collections

alphabets = list("abcdefghijklmnopqrstuvwxyz")

def do1(s_dic, i, c):
    for t in alphabets:
        if(s_dic[t] == 0):
            continue
        if(i in s_dic[t]):
            s_dic[t].remove(i)
            break
    if(s_dic[c] == 0):
        s_dic[c] = set()
    s_dic[c].add(i)
    
def do2(s_dic, l, r):
    ans = 0
    for t in alphabets:
        if(s_dic[t] == 0):
            continue
        for p in s_dic[t]:
            if(l-1 <= p and p < r):
                ans += 1
                break
    print(ans)
    
def make_dic(S):
    hist = collections.Counter()
    for i, s in enumerate(S):
        if(hist[s] == 0):
            hist[s] = set()
        hist[s].add(i)
    return hist

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

s_dic = make_dic(S)

for q in range(Q):
    query = input().split()
    if(query[0] == "1"):
        do1(s_dic, int(query[1]) - 1, query[2])
    else:
        do2(s_dic, int(query[1]), int(query[2]))

Submission status: Time Limit Exceeded

Solution code:
def do1(current_s, i, c):
    current_s[i] = c
    
def do2(current_s, l, r):
    ans = set()
    for i in range(l-1, r):
        ans.add(current_s[i])
    print(len(ans))
    

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

index = 0
for q in range(Q):
    query = input().split()
    if(query[0] == "1"):
        do1(S, int(query[1]) - 1, query[2])
    else:
        do2(S, int(query[1]), int(query[2]))

Submission status: Time Limit Exceeded

Solution code:
def do1(current_s, i, c):
    current_s[i] = c
    
def do2(current_s, l, r):
    print(len(set(current_s[l-1:r])))
    

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

index = 0
for q in range(Q):
    query = input().split()
    if(query[0] == "1"):
        do1(S, int(query[1]) - 1, query[2])
    else:
        do2(S, int(query[1]), int(query[2]))

Submission status: Time Limit Exceeded

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

N = int(input())
S = list(input().rstrip())
ord_a = ord("a")

# N: 処理する区間の長さ
INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [[0]*(2*N0) for _ in range(26)]
lazy = [[0]*(2*N0) for _ in range(26)]

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(k, *ids):
    for i in reversed(ids):
        v = lazy[k][i-1]
        if not v:
            continue
        lazy[k][2*i-1] += v; lazy[k][2*i] += v
        data[k][2*i-1] += v; data[k][2*i] += v
        lazy[k][i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x, k):
    *ids, = gindex(l, r)
    propagates(k, *ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[k][R-1] += x; data[k][R-1] += x
        if L & 1:
            lazy[k][L-1] += x; data[k][L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[k][i-1] = max(data[k][2*i-1], data[k][2*i])

# 区間[l, r)内の最大値を求める
def query(l, r, k):
    propagates(k, *gindex(l, r))
    L = N0 + l; R = N0 + r

    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[k][R-1])
        if L & 1:
            s = max(s, data[k][L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for j in range(N):
    u = S[j]
    update(j, N, 1, ord(u) - ord_a)

Q = int(input())

for _ in range(Q):
    q = input().rstrip().split()
    if q[0] == "2":
        l, r = int(q[1]) - 1, int(q[2]) - 1
        cnt = 0
        for i in range(26):
            if l == 0:
                cnt += int(query(r, r + 1, i) > 0)
            else:
                cnt += int((query(r, r + 1, i) - query(l - 1, l, i) > 0))

        print(cnt)
    else:
        i, c = int(q[1]) - 1, q[2]
        update(i, N, -1, ord(S[i]) - ord_a)
        S[i] = c
        update(i, N, 1, ord(S[i]) - ord_a)

Submission status: Time Limit Exceeded

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

N = int(input())
S = list(input().rstrip())
ord_a = ord("a")

# N: 処理する区間の長さ
INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [[0]*(2*N0) for _ in range(26)]
lazy = [[0]*(2*N0) for _ in range(26)]

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(k, *ids):
    for i in reversed(ids):
        v = lazy[k][i-1]
        if not v:
            continue
        lazy[k][2*i-1] += v; lazy[k][2*i] += v
        data[k][2*i-1] += v; data[k][2*i] += v
        lazy[k][i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x, k):
    *ids, = gindex(l, r)
    propagates(k, *ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[k][R-1] += x; data[k][R-1] += x
        if L & 1:
            lazy[k][L-1] += x; data[k][L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[k][i-1] = max(data[k][2*i-1], data[k][2*i])

# 区間[l, r)内の最大値を求める
def query(l, r, k):
    propagates(k, *gindex(l, r))
    L = N0 + l; R = N0 + r

    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[k][R-1])
        if L & 1:
            s = max(s, data[k][L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for j in range(N):
    u = S[j]
    update(j, N, 1, ord(u) - ord_a)

Q = int(input())

for _ in range(Q):
    q = input().rstrip().split()
    if q[0] == "2":
        l, r = int(q[1]) - 1, int(q[2]) - 1
        cnt = 0
        for i in range(26):
            if l == 0:
                cnt += int(query(r, r + 1, i) > 0)
            else:
                cnt += int((query(r, r + 1, i) - query(l - 1, l, i) > 0))
        print(cnt)
    else:
        i, c = int(q[1]) - 1, q[2]
        update(i, N, -1, ord(S[i]) - ord_a)
        S[i] = c
        update(i, N, 1, ord(S[i]) - ord_a)