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:
N = int(input())
s = input()
S = []
for k in range(N):
  S.append(s[k])
Q = int(input())
a = ord('a')
alpha = [[0 for _ in range(26)] for _ in range(N)]
alpha[0][ord(S[0])-a] = 1
for k in range(1, N):
  alpha[k] = [] + alpha[k-1]
  alpha[k][ord(S[k])-a] += 1
change = set()
substitute = []
inp = []
for k in range(Q):
  s,t,u = map(str, input().split())
  inp.append([s,t,u])
  if s == '2':
    l = int(t) -1
    r = int(u) -1
    change.add(max(l-1, 0))
    change.add(r)

for item in inp:
  if item[0] == '1':
    for ch in change:
      if int(item[1]) -1 <= ch:
        alpha[ch][ord(item[2]) -a] += 1
        alpha[ch][ord(S[int(item[1])-1]) - a] -= 1
    S[int(item[1])-1] = item[2]
  else:
    l = int(item[1]) -1
    r = int(item[2]) -1
    ans = 0
    if l == 0:
      for k in range(26):
        if alpha[r][k] >0:
          ans += 1
    else:
      for k in range(26):
        if alpha[r][k] - alpha[l-1][k] > 0:
          ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = input()
S = []
for k in range(N):
  S.append(s[k])
Q = int(input())

for k in range(Q):
  s,t,u = map(str, input().split())
  if s == '1':
    i = int(t) -1
    S[i] = u

  if s == '2':
    l = int(t) -1
    r = int(u) -1
    print(len(set(S[l:r+1])))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = input()
S = []
for k in range(N):
  S.append(s[k])
Q = int(input())
a = ord('a')
alpha = [[0 for _ in range(26)] for _ in range(N)]
alpha[0][ord(S[0])-a] = 1
for k in range(1, N):
  alpha[k] = [] + alpha[k-1]
  alpha[k][ord(S[k])-a] += 1

substitute = [-1 for _ in range(N)]
for k in range(Q):
  s,t,u = map(str, input().split())
  if s == '1':
    i = int(t) -1
    c = u
    substitute[i] = c
      

  if s == '2':
    l = int(t) -1
    r = int(u) -1
    count = [0 for _ in range(26)]
    for j in range(l, r+1):
      if substitute[j] != -1:
        count[ord(substitute[j])-a] += 1
        count[ord(S[j])-a] -= 1 
    ans = 0
    if l == 0:
      for k in range(26):
        if alpha[r][k] + count[k] > 0:
          ans += 1
    else:
      for k in range(26):
        if alpha[r][k] - alpha[l-1][k] + count[k] > 0:
          ans += 1      
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
s = input()
S = []
for k in range(N):
  S.append(s[k])
Q = int(input())
a = ord('a')
alpha = [[] for _ in range(ord('z') - a + 1)]
for k in range(N):
  alpha[ord(S[k])- a].append(k)

for k in range(Q):
  s,t,u = map(str, input().split())
  if s == '1':
    i = int(t) -1
    c = u
    if S[i] != c:
      del alpha[ord(S[i])-a][alpha[ord(S[i])-a].index(i)]
      alpha[ord(c)-a].append(i)
      S[i] = c

  if s == '2':
    l = int(t) -1
    r = int(u) -1
    ans = 0
    for j in range(len(alpha)):
      for k in range(len(alpha[j])):
        if l <= alpha[j][k] <= r:
          ans += 1
          break
      
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


# SegTreeの関数
def segfunc(x, y):
    return x | y
# 単位元
# min->inf, max->-inf, add->0, mul->1
ide_ele = set()

# セグメント木
class SegTree:
    """
    init(init_val, segfunc, ide_ele): 配列init_valで初期化、構築
    update(k, x): k番目の値をxに更新
    query(l, r): 区間[l, r)をsegfuncしたものを返す
    """
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n-1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセットする
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        :param k: index(0-index)
        :param x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k>>1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        :param l: 0-index
        :param r: 0-index
        :return:
        """
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r-1])
            l >>= 1
            r >>= 1
        return res


def main():
    N = NI()
    S = SI()
    Q = NI()
    querys = [list(SI().split()) for _ in range(Q)]
    S_sets = []
    for s in S:
        tmp = set()
        tmp.add(s)
        S_sets.append(tmp)

    segtree = SegTree(S_sets, segfunc, ide_ele)

    for query in querys:
        if query[0] == "1":
            segtree.update(int(query[1]) - 1, {query[2]})
        else:
            l, r = int(query[1])-1, int(query[2])
            print(len(segtree.query(l, r)))



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

n=int(input())
s=list(input().strip())
q=int(input())
A=[list(input().strip().split()) for _ in range(q)]

for i in A:
    t,a,b=i
    t = int(t)
    a = int(a)
    if t==2:
        b = int(b)
        print(len(set(s[a-1:b])))
    if t==1:
        s[a-1] = b

Submission status: Time Limit Exceeded

Solution code:

class SegmentTree:
    def __init__(self, n):
        # 0-indexed.
        x = 1
        while x < n:
            x *= 2

        self.n = x
        self.base = 0
        self.dat = [self.base] * (2 * x - 1)

    def update(self, k, v):
        # Update dat[k] to v.
        k += self.n - 1
        self.dat[k] = v
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.dat[k * 2 + 1] + self.dat[k * 2 + 2]

    def query(self, a, b, k=0, l=0, r=0):
        # Returns value in [a, b).
        if l >= r:
            r = self.n

        if b <= l or r <= a:
            return self.base

        if a <= l and r <= b:
            return self.dat[k]

        vl = self.query(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self.query(a, b, k * 2 + 2, (l + r) // 2, r)
        return vl + vr


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

trees = [SegmentTree(N + 1) for _ in range(26)]
for i in range(N):
    trees[ord(S[i]) - ord("a")].update(i, 1)

for _ in range(Q):
    s, *x = input().split()
    if s == "1":
        i = int(x[0]) - 1
        c = x[1]
        trees[ord(S[i]) - ord("a")].update(i, 0)
        trees[ord(c) - ord("a")].update(i, 1)
        S[i] = c
    else:
        l, r = map(int, x)
        cnt = 0
        for i in range(26):
            cnt += int(trees[i].query(l - 1, r) > 0)
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#coding:utf-8
import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
from collections import Counter, deque
from random import random
class Node:
        def __init__(self,value:int=-1):
            self.left = None
            self.right = None
            self.value = value
            self.priority = random()
            self.count_partial = 1
            self.sum_partial = value
class Treap:
    
    #Node [left, right, key, value, priority, num_partial, sum_partial]
    def __init__(self):
        self.root = None

    def update(self, node):
        if node.left is None:
            left_count = 0
            left_sum = 0
        else:
            left_count = node.left.count_partial
            left_sum = node.left.sum_partial
        if node.right is None:
            right_count = 0
            right_sum = 0
        else:
            right_count = node.right.count_partial
            right_sum = node.right.sum_partial

        node.count_partial = left_count + right_count + 1
        node.sum_partial = left_sum + right_sum + node.value
        return node

    def merge(self, left :Node, right:Node):
        if left is None or right is None:
            return left if right is None else right

        if left.priority > right.priority:
            left.right = self.merge(left.right,right)
            return self.update(left)
        else:
            right.left = self.merge(left,right.left)
            return self.update(right)


    def node_size(self, node:Node):
        return 0 if node is None else node.count_partial
    
    def node_key(self, node:None):
        return -1 if node is None else node.key

    #指定された場所のノードは右の木に含まれる

    def split(self, node:Node, key:int, level=0):
        if node is None:
            return (None,None)

        if key <= self.node_size(node.left):
            left,right = self.split(node.left, key,level+1)
            node.left = right
            return left, self.update(node)
        else:
            left,right = self.split(node.right, key - self.node_size(node.left) - 1,level+1)
            node.right = left
            return self.update(node),right 
    def split(self, node:None, value):
        if node is None:
            return None,None
        if value <= node.value:
            left,right = self.split(node.left, value)
            node.left = right
            return left, self.update(node)
        else:
            left,right = self.split(node.right, value)
            node.right = left
            return self.update(node),right

    
    def insert(self, pos:int,value:int =-1):
        value = value if value > 0 else pos
        left, right = self.split(self.root, pos)
        new_node = Node(value)
        self.root = self.merge(self.merge(left,new_node),right)
    
    def erase(self, pos:int):
        middle,right = self.split(self.root, pos+1)
        left,middle = self.split(middle, pos)
        self.root = self.merge(left,right)

        

    def printTree(self, node=None, level=0):
        node = self.root if node is None else node
        if node is None:
            print('level=',level,'root is None')
            return
        else:
            print('level=',level,'v=',node.value,'c=',node.count_partial, 'p=',node.priority)
        if node.left is not None:
            self.printTree(node.left,level+1)
        
        if node.right is not None:
            self.printTree(node.right,level+1)
        
    

    def search(self, pos):
        #return self.search_recursively(pos,self.root)
        v = self.root
        while v:
            left_count = self.node_size(v.left)
            if pos < left_count:
                v = v.left
            elif pos == left_count:
                return v.value
            else:
                v = v.right
                pos -= left_count + 1
        return -1

    def search2(self, value):
        v = self.root
        upper = 10**18
        while v:

            if value == v.value:
                return value

            elif value < v.value:
                upper = v.value
                v = v.left
            else:
                v = v.right
        return upper

    def search_recursively(self, pos, node):
        if node is None:
            return -1
        num_left = 0 if node.left is None else node.left.count_partial
        if num_left + 1 == pos:
            return node.value
        if pos <= num_left:
            return self.search_recursively(pos, node.left)
        else:
            return self.search_recursively(pos - num_left - 1, node.right)
        


    
                










def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    S = list(input())


    trees = []
    for i in range(26):
        trees.append(Treap())
    

    for i,c in enumerate(S):
        trees[ord(c)-ord('a')].insert(i)
    
    Q = int(input())
    out = []
    for _ in range(Q):
        q1,q2,q3 = input().split()
        if int(q1) == 1:
            iq = int(q2)-1
            before = S[iq]
            after = q3
            S[iq] = after
            trees[ord(before)-ord('a')].erase(iq)
            trees[ord(after)-ord('a')].insert(iq)

        else:
            l,r = int(q2)-1,int(q3)-1
            count = 0
            for i in range(26):
                if trees[i].search2(l) <= r:
                    count += 1
            out.append(count)
    print('\n'.join(map(str,out)))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#####segfunc######
def segfunc(x, y):
    return x | y


def init(init_val):
    # set_val
    for i in range(n):
        seg[i + num - 1] = set(init_val[i])
        # built
    for i in range(num - 2, -1, -1):
        seg[i] = segfunc(seg[2 * i + 1], seg[2 * i + 2])


def update(k, x):
    k += num - 1
    seg[k] = set(x)
    while k:
        k = (k - 1) // 2
        seg[k] = segfunc(seg[k * 2 + 1], seg[k * 2 + 2])


def query(p, q):
    if q <= p:
        return ide_ele
    p += num - 1
    q += num - 2
    res = ide_ele
    while q - p > 1:
        if p & 1 == 0:
            res = segfunc(res, seg[p])
        if q & 1 == 1:
            res = segfunc(res, seg[q])
            q -= 1
        p = p // 2
        q = (q - 1) // 2
    if p == q:
        res = segfunc(res, seg[p])
    else:
        res = segfunc(segfunc(res, seg[p]), seg[q])
    return res


#####単位元######
ide_ele = set()

n = int(input())
S = input().strip()
Q = int(input())

num = 2 ** (n - 1).bit_length()
seg = [set()] * 2 * num

init(S)


for _ in range(Q):
    a, b, c = [x for x in input().split()]
    if a == "1":
        update(int(b) - 1, c)
    else:
        print(len(query(int(b) - 1, int(c))))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=list(input())
Q=int(input())
for i in range(Q):
  q,a,b=input().split()
  if q=='1':
    S[int(a)-1] = b
  else:
    print(len(set(S[int(a)-1:int(b)])))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())

for _ in range(q):
    question = input().split()
    if question[0] == "1":
        i = int(question[1])-1
        c = question[2]
        s[i] = c
    else:
        l = int(question[1])-1
        r = int(question[2])
        print(len(set(s[l:r])))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import bisect_left, insort_left
import sys
input = sys.stdin.readline
N = int(input())
S = list(input())

dic = defaultdict(list)
for i, s in enumerate(S):
    dic[s].append(i)

Q = int(input())
for _ in [0]*Q:
    t, *q = input().split()
    if t == '1':
        i, c = q
        i = int(i)-1

        s = S[i]
        S[i] = c
        dic[s].pop(bisect_left(dic[s], i))
        insort_left(dic[c], i)

    else:
        l, r = map(int, q)
        l -= 1
        r -= 1
        cnt = 0
        for L in dic.values():
            i = bisect_left(L, l)
            if i != len(L) and L[i] <= r:
                cnt += 1
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
import bisect

alp = [[] for _ in range(26)]
cur = [0]*n

for i in range(n):
    x = ord(s[i]) - 97
    alp[x].append(i)
    cur[i] = x
    
q = int(input())
for i in range(q):
    a,b,c = input().split()
    
    if a == "1":
        bb = int(b)
        x = cur[bb-1]
        alp[x].remove(bb-1)
        
        y = ord(c) - 97
        cc = bisect.bisect(alp[y],bb-1)
        alp[y].insert(cc,bb-1)
        cur[bb-1] = y
        
    else:
        ans = 0
        l,r = int(b)-1,int(c)-1
        for j in range(26):
            if alp[j] != []:
                c = bisect.bisect(alp[j],l-1)
                if c == len(alp[j]):
                    continue
                else:
                    if alp[j][c] <= r:
                        ans += 1
                        
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = input()
import bisect

alp = [set() for _ in range(26)]
cur = [0]*n

for i in range(n):
    x = ord(s[i]) - 97
    alp[x].add(i)
    cur[i] = x
    
q = int(input())
for i in range(q):
    a,b,c = input().split()
    
    if a == "1":
        bb = int(b)
        x = cur[bb-1]
        alp[x].remove(bb-1)
        
        y = ord(c) - 97
        alp[y].add(bb-1)
        cur[bb-1] = y
        
    else:
        ans = 0
        l,r = int(b)-1,int(c)-1
        for j in range(26):
            if alp[j] != set():
                b = list(alp[j])
                b.sort()
                
                c = bisect.bisect(b,l-1)
                if c == len(b):
                    continue
                else:
                    if b[c] <= r:
                        ans += 1
                        
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
N = int(input())
S = list(input())
Q = int(input())
D = {chr(ord('a') + i): [] for i in range(26)}
for i, s in enumerate(S):
    D[s].append(i)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue
        D[s].remove(i)
        ni = bisect_left(D[x], i)
        D[x].insert(ni, i)
        S[i] = x
    else:
        l, r = int(query[1]), int(query[2])
        l -= 1
        r -= 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)
            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)
            if ri - li > 0:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
que = [list(input().split()) for _i in range(q)]
for x, y, z in que:
    if x == '1':
        s[int(y)-1] = z
    else:
        print(len(set(s[int(y)-1:int(z)])))

Submission status: Time Limit Exceeded

Solution code:
class SegT():
    def __init__(self, size):
        self.size = 1
        while self.size < size: self.size *= 2
        self.data = [set() for _ in range(self.size * 2 - 1)] 
    
    def update(self, i, x):
        i += (self.size - 1)
        self.data[i] = {x}
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]
        
    def get(self, a, b, node=0, l=0, r=-1):
        if r < 0: r = self.size
        if r <= a or b <= l: return set()
        if a <= l and r <= b: return self.data[node]
        vl = self.get(a, b, node*2+1, l, (l+r)//2)
        vr = self.get(a, b, node*2+2, (l+r)//2, r)
        return vl | vr

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

segt = SegT(N)
for i in range(N):
    segt.update(i, S[i])

for i in range(Q):
    t, l, r = input().split()
    if t == "1":
        segt.update(int(l)-1, r)
    else:
        x = segt.get(int(l)-1,int(r))
        print(len(x))

Submission status: Time Limit Exceeded

Solution code:
class SegT():
    def __init__(self, size):
        self.size = 1
        while self.size < size: self.size *= 2
        self.data = [0] * (self.size * 2 - 1)
    
    def update(self, i, x):
        i += (self.size - 1)
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]
        
    def get(self, a, b, node=0, l=0, r=-1):
        if r < 0: r = self.size
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.data[node]
        vl = self.get(a, b, node*2+1, l, (l+r)//2)
        vr = self.get(a, b, node*2+2, (l+r)//2, r)
        return vl | vr

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

segt = SegT(N)
for i in range(N):
    x = ord(S[i]) - ord('a')
    segt.update(i, (1<<x))

for i in range(Q):
    t, l, r = input().split()
    if t == "1":
        x = ord(r) - ord('a')
        segt.update(int(l)-1, (1<<x))
    else:
        x = segt.get(int(l)-1,int(r))
        ans = 0
        for i in range(26):
            if x>>i&1: ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
s = list(input())
Q = int(input())
for i in range(Q):
    a, b, c = map(str, input().split())
    if a == '1':
        s[int(b)-1] = c
    else:
        m = set(s[int(b)-1:int(c)])
        print(len(m))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N = int(input())
s = list(input())
Q = int(input())
for i in range(Q):
    a, b, c = map(str, input().split())
    if a == '1':
        s[int(b)-1] = c
    else:
        m = Counter(s[int(b)-1:int(c)])
        print(len(m))

Submission status: Time Limit Exceeded

Solution code:
class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0 for _ in range(2 * N)]

    def update(self, i, x):
        index = self.N + i - 1
        self.data[index] = x
        while index > 0:
            index = (index - 1) // 2  # parent
            self.data[index] = max(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            vl = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
            vr = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
            return max(vl, vr)


def main():
    N = int(input())
    pw2 = 1
    while pw2 < N:
        pw2 *= 2
    S = input()
    Q = int(input())
    query_list = [input().split(' ') for _ in range(Q)]
    trees = [None for _ in range(26)]
    for cn in range(26):
        trees[cn] = SegTree(pw2)
    for i, c in enumerate(S):
        cn = ord(c) - ord('a')
        trees[cn].update(i, 1)
    for query in query_list:
        if query[0] == '1':
            # type 1 query
            i = int(query[1]) - 1
            new_cn = ord(query[2]) - ord('a')
            for cn in range(26):
                x = (1 if cn == new_cn else 0)
                trees[cn].update(i, x)
        else:
            # type 2 query
            left = int(query[1]) - 1
            right = int(query[2]) - 1
            kinds = sum([trees[cn].query(left, right + 1, 0, 0, pw2) for cn in range(26)])
            print(kinds)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0 for _ in range(2 * N)]

    def update(self, i, x):
        index = self.N + i - 1
        self.data[index] = x
        while index > 0:
            index = (index - 1) // 2  # parent
            self.data[index] = max(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            vl = self.query(a, b, 2 * k + 1, l, (l + r) // 2)
            vr = self.query(a, b, 2 * k + 2, (l + r) // 2, r)
            return max(vl, vr)


def main():
    chars = [chr(ord('a') + i) for i in range(26)]
    N = int(input())
    pw2 = 1
    while pw2 < N:
        pw2 *= 2
    S = input()
    Q = int(input())
    query_list = [input().split(' ') for _ in range(Q)]
    trees = dict()
    for c in chars:
        trees[c] = SegTree(pw2)
    for i, c in enumerate(S):
        trees[c].update(i, 1)
    for query in query_list:
        if query[0] == '1':
            # type 1 query
            i = int(query[1]) - 1
            new_c = query[2]
            for c in chars:
                x = (1 if c == new_c else 0)
                trees[c].update(i, x)
        else:
            # type 2 query
            left = int(query[1]) - 1
            right = int(query[2]) - 1
            kinds = sum([trees[c].query(left, right + 1, 0, 0, pw2) for c in chars])
            print(kinds)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0 for _ in range(2 * N)]

    def update(self, i, x):
        index = self.N + i - 1
        self.data[index] = x
        while index > 0:
            index = (index - 1) // 2  # parent
            self.data[index] = max(self.data[2 * index + 1], self.data[2 * index + 2])

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            vl = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
            vr = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
            return max(vl, vr)

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


def main():
    chars = [chr(ord('a') + i) for i in range(26)]
    N = int(input())
    pw2 = 1
    while pw2 < N:
        pw2 *= 2
    S = input()
    Q = int(input())
    query_list = [input().split(' ') for _ in range(Q)]
    trees = dict()
    for c in chars:
        trees[c] = SegTree(pw2)
    for i, c in enumerate(S):
        trees[c].update(i, 1)
    for query in query_list:
        if query[0] == '1':
            # type 1 query
            i = int(query[1]) - 1
            new_c = query[2]
            for c in chars:
                x = (1 if c == new_c else 0)
                trees[c].update(i, x)
        else:
            # type 2 query
            left = int(query[1]) - 1
            right = int(query[2]) - 1
            kinds = sum([trees[c].query(left, right + 1) for c in chars])
            print(kinds)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegTree:

    def __init__(self, N):
        self.N = N
        self.data = [0 for _ in range(2 * N)]

    def update(self, i, x):
        index = self.N + i - 1
        self.data[index] = x
        while index > 0:
            index = (index - 1) // 2  # parent
            self.data[index] = max(self.data[2 * index + 1], self.data[2 * index + 2])

    def _query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return 0
        if a <= l and r <= b:
            return self.data[k]
        else:
            vl = self._query(a, b, 2 * k + 1, l, (l + r) // 2)
            vr = self._query(a, b, 2 * k + 2, (l + r) // 2, r)
            return max(vl, vr)

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


def main():
    chars = [chr(ord('a') + i) for i in range(26)]
    N = int(input())
    pw2 = 1
    while pw2 < N:
        pw2 *= 2
    S = input()
    Q = int(input())
    query_list = [input().split(' ') for _ in range(Q)]
    trees = dict()
    for c in chars:
        trees[c] = SegTree(pw2)
    for i, c in enumerate(S):
        trees[c].update(i, 1)
    for query in query_list:
        if query[0] == '1':
            # type 1 query
            i = int(query[1]) - 1
            new_c = query[2]
            for c in chars:
                x = (1 if c == new_c else 0)
                trees[c].update(i, x)
        else:
            # type 2 query
            left = int(query[1]) - 1
            right = int(query[2]) - 1
            kinds = sum([trees[c].query(left, right + 1) for c in chars])
            print(kinds)


if __name__ == '__main__':
    main()