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:

class SegmentTree:
    def __init__(self, base_array,n , default_value = 0, segfunc = lambda a, b: a + b): #元配列、大きさ、デフォルト値
        self._num = 2 ** (n - 1).bit_length()
        self._seg = [default_value] * 2 * self._num
        self._segfunc = segfunc
        self._ide_ele = default_value
        for i in range(n):
            self._seg[i + self._num - 1] = base_array[i]
        for i in range(self._num - 2, -1, -1):
            self._seg[i] = segfunc(self._seg[2 * i + 1], self._seg[2 * i + 2])


    def update(self, k, x):
        k += self._num - 1
        self._seg[k] = x
        while k:
            k = (k - 1) // 2
            self._seg[k] = self._segfunc(self._seg[k * 2 + 1], self._seg[k * 2 + 2])


    def query(self, p, q): # qは含まない
        if q <= p:
            return self._ide_ele
        p += self._num - 1
        q += self._num - 2
        res = self._ide_ele
        while q - p > 1:
            if p & 1 == 0:
                res = self._segfunc(res, self._seg[p])
            if q & 1 == 1:
                res = self._segfunc(res, self._seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self._segfunc(res, self._seg[p])
        else:
            res = self._segfunc(self._segfunc(res, self._seg[p]), self._seg[q])
        return res

def main():
    N = int(input())
    S = [c for c in input()]
    M = int(input())

    A = [set() for i in range(N)]

    for i, c in enumerate(S):
        A[i] = {c}

    st = SegmentTree(A, N, set(), lambda a, b: a | b)

    for i in range(M):
        p, a, b = input().split()
        a  = int(a) - 1
        b = int(b) - 1 if p == '2' else b
        if p == '1':
            st.update(a, {b})

        if p == '2':
            s = st.query(a, b + 1)
            print(len(s))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, n):
        self.__tree = [0 for _ in range(n+1)]
        self.n = n

    def add(self,ind,v):
        while ind<=self.n:
            self.__tree[ind] += v
            ind += ind&-ind
    def get(self, ind):
        sum = 0
        while ind>0:
            sum += self.__tree[ind]
            ind -= ind&-ind
        return sum



if __name__ == "__main__":
    n = int(input())
    st = input()

    tree = [BIT(n) for _ in range(26)]
    for i,c in enumerate(st):
        #print(c,i+1,1)
        tree[ ord(c)-ord('a') ].add(i+1,1)
    saved = list(st)

    q = int(input())
    for _ in range(q):
        t,a,b = (x for x in input().split())
        a = int(a)
        if t == '2':
            b = int(b)
            print(sum( [1 if (tree[i].get(b)-tree[i].get(a-1)) > 0 else 0 for i in range(26)  ] ))
        elif saved[a-1] != b:
            tree[ ord(saved[a-1]) - ord('a') ].add(a,-1)
            tree[ ord(b) - ord('a') ].add(a,+1)
            saved[a-1] = b

Submission status: Time Limit Exceeded

Solution code:
class BIT:
    def __init__(self, n):
        self.__tree = [0] * (n+1)
        self.n = n

    def add(self,ind,v):
        while ind<=self.n:
            self.__tree[ind] += v
            ind += ind&-ind
    def get(self, ind):
        sum = 0
        while ind>0:
            sum += self.__tree[ind]
            ind -= ind&-ind
        return sum



if __name__ == "__main__":
    n = int(input())
    st = input()

    tree = [BIT(n) for _ in range(26)]
    for i,c in enumerate(st):
        #print(c,i+1,1)
        tree[ ord(c)-ord('a') ].add(i+1,1)
    saved = list(st)

    q = int(input())
    for _ in range(q):
        t,a,b = (x for x in input().split())
        a = int(a)
        if t == '2':
            b = int(b)
            print(sum( [1 if (tree[i].get(b)-tree[i].get(a-1)) > 0 else 0 for i in range(26)  ] ))
        elif saved[a-1] != b:
            tree[ ord(saved[a-1]) - ord('a') ].add(a,-1)
            tree[ ord(b) - ord('a') ].add(a,+1)
            saved[a-1] = b

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
    n = int(input())
    s = list(input().rstrip())
    q = int(input())
    ans = []
    al = [[] for _ in range(26)]
    for i, c in enumerate(s):
        al[ord(c) - ord("a")].append(i)
    for _ in range(q):
        x, y, z = map(str, input().rstrip().split())
        if x == "1":
            y = int(y) - 1
            if s[y] == z:
                continue
            p = ord(z) - ord("a")
            al[p].insert(bisect_left(al[p], y), y)
            al[ord(s[y]) - ord("a")].remove(y)
            s[y] = z
        else:
            y = int(y)
            y -= 1
            z = int(z)
            cnt = 0
            for i in range(26):
                index = bisect_left(al[i], y)
                if index < len(al[i]) and al[i][index] < z:
                    cnt += 1
            ans.append(cnt)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
    n = int(input())
    s = input().rstrip()
    q = int(input())
    ans = []
    al = [[] for _ in range(26)]
    for i in range(n):
        al[ord(s[i]) - ord("a")].append(i)
    for _ in range(q):
        x, y, z = map(str, input().rstrip().split())
        if x == "1":
            y = int(y) - 1
            if s[y] == z:
                continue
            p = ord(z) - ord("a")
            al[p].insert(bisect_left(al[p], y), y)
            al[ord(s[y]) - ord("a")].remove(y)
            s = s[:y] + z + s[y+1:]
        else:
            y = int(y)
            y -= 1
            z = int(z)
            cnt = 0
            for i in range(26):
                index = bisect_left(al[i], y)
                if index < len(al[i]) and al[i][index] < z:
                    cnt += 1
            ans.append(cnt)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
    n = int(input())
    s = input().rstrip()
    q = int(input())
    ans = []
    al = [[] for _ in range(26)]
    for i in range(n):
        al[ord(s[i]) - ord("a")].append(i)
    for _ in range(q):
        x, y, z = map(str, input().rstrip().split())
        if x == "1":
            y = int(y)
            y -= 1
            if s[y] == z:
                continue
            al[ord(z) - ord("a")].insert(bisect_left(al[ord(z) - ord("a")], y), y)
            al[ord(s[y]) - ord("a")].remove(y)
            s = s[:y] + z + s[y+1:]
        else:
            y = int(y)
            y -= 1
            z = int(z)
            cnt = 0
            for i in range(26):
                index = bisect_left(al[i], y)
                if index < len(al[i]) and al[i][index] < z:
                    cnt += 1
            ans.append(cnt)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class SegTree():
    def segfunc(self, x, y):
        return x | y
        
    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def main():
    n = int(input())
    s = input().rstrip()
    q = int(input())
    ans = []
    init = [set() for _ in range(n)]
    for i in range(n):
        c = s[i]
        init[i].add(c)
    seg = SegTree(set(), n, init)
    for _ in range(q):
        x, y, z = map(str, input().rstrip().split())
        if x == "1":
            y = int(y)
            y -= 1
            buf = set()
            buf.add(z)
            seg.update(y, buf)
        else:
            y = int(y)
            y -= 1
            z = int(z)
            ans.append(len(seg.query(y, z)))
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
ql = [input().split() for i in range(q)]

for i in ql:
  if i[0] =="1":
    #print(int(i[1])) 
    s[int(i[1])-1] = i[2]
  else:
    #print(s[int(i[1])-1:int(i[2])])
    a = set(s[int(i[1])-1:int(i[2])])
    print(len(a))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
ql = [input().split() for i in range(q)]

for i in ql:
  if i[0] =="1":
    #print(int(i[1])) 
    s[int(i[1])-1] = i[2]
  else:
    #print(s[int(i[1])-1:int(i[2])])
    print(len(set(s[int(i[1])-1:int(i[2])])))
    
#print(s)

Submission status: Time Limit Exceeded

Solution code:

def main():
    n = int(input())
    s = bytearray(input().encode())
    q = int(input())
    for _ in range(q):
        t, a, b = [p for p in input().split()]
        t = int(t)
        a = int(a)
        if t == 1:
            s[a-1] = b.encode()[0]
        else:
            b = int(b)
            c = set(s[a-1:b])
            print(len(c))

main()

Submission status: Time Limit Exceeded

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

for _ in range(q):
    query = input().split()
    if int(query[0]) == 1:
        # 文字列書き換えるやつ
        index = int(query[1]) - 1
        s[index] = query[2]
    else:
        # 文字種をカウントするやつ
        start = int(query[1]) - 1
        end = int(query[2]) - 1
        s_slice = s[start:end + 1]
        count = len(set(s_slice))
        print(count)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections
import sys

input = sys.stdin.readline


def main():
    n = int(input())

    s = list(input()[:-1])

    q = int(input()[:-1])

    li = list(s)

    d = {}

    for i in range(26):
        d[chr(i + 97)] = []

    for i, x in enumerate(s):
        d[x].append(i)


    for _ in range(q):
        a, *x = input().split()

        if a == "1":
            i = int(x[0]) - 1
            c = x[1]
            o = li[i]
            index = bisect.bisect_left(d[o], i)
            d[o].pop(index)
            d[c].insert(bisect.bisect_left(d[c], i), i)
            li[i] = c
        else:
            l = int(x[0]) - 1
            r = int(x[1]) - 1
            cnt = 0
            for v in d.values():
                if len(v) == 0:
                    continue
                index = bisect.bisect_left(v, l)
                if index == len(v):
                    continue
                if v[index] <= r:
                    cnt += 1
            print(cnt)

main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
import sys
import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

class fenwick_tree:
    def __init__(self, n):
        self.N = n
        self.n = 1 # pow of 2
        while(self.n < self.N):
            self.n *= 2
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        while idx <= self.n:
            self.data[idx] += x
            idx += (idx & -idx)

    def cumulate(self, idx):
        s = 0
        while idx > 0:
            s += self.data[idx]
            idx -= (idx & -idx)
        return s

def main():
    N = ri()
    S = rs()
    Q = ri()
    ans = []

    bit = [fenwick_tree(N) for i in range(26)]
    for i in range(N):
        d = ord(S[i]) - ord('a')
        bit[d].add(i + 1, 1)

    ca = [c for c in S]
    for _ in range(Q):
        ss = rsa()
        if ss[0] == '1':
            pos = int(ss[1]) - 1
            c = ss[2][0]
            bit[ord(ca[pos]) - ord('a')].add(pos + 1, -1)
            ca[pos] = c
            bit[ord(ca[pos]) - ord('a')].add(pos + 1, +1)
        else:
            l = int(ss[1]) - 1
            r = int(ss[2]) - 1
            cnt = 0
            for i in range(26):
                su = bit[i].cumulate(r + 1) - bit[i].cumulate(l)
                if su > 0: cnt += 1
            ans.append(cnt)
    
    print("\n".join([str(n) for n in ans]))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import math

def solve(N, S, Q, queries):
    def update(i, c):
        values[i] = c
        s = (i // sN) * sN
        buckets[i//sN] = 0
        for v in values[s:min(s+sN, len(values))]:
            buckets[i//sN] |= 1 << v

    def count(l, r):
        res = 0
        for i in range(sN):
            ll = i * sN
            rr = ll + sN
            if r <= ll or rr <= l:
                continue
            if l <= ll and rr <= r:
                res |= buckets[i]
            else:
                for j in range(max(l, ll), min(r, rr)):
                    res |= 1 << values[j]
        return sum(b == '1' for b in bin(res))
        
    sN = math.ceil(N ** 0.5)
    values = [ord(c)-ord('a') for c in S]
    buckets = [0] * sN
    for i, v in enumerate(values):
        buckets[i//sN] |= 1 << v
    for t, x, y in queries:
        if t == 1:
            update(int(x)-1, ord(y)-ord('a'))
        else:
            yield count(int(x)-1, int(y))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    S = next(tokens)
    Q = int(next(tokens))
    queries = [(int(next(tokens)), next(tokens), next(tokens)) for _ in range(Q)]
    for result in solve(N, S, Q, queries):
        print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

class BIT(object):
    def __init__(self, N, init=0):
        self.N = N
        self.bit = [init for _ in range(N)]

    def add(self, k, w):
        x = k
        while x < self.N:
            self.bit[x] += w
            x |= x + 1

    def sum(self, k):
        s = 0
        x = k - 1
        while x >= 0:
            s += self.bit[x]
            x = (x & (x + 1)) - 1
        return s

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

d = defaultdict(lambda: BIT(n))
for i, si in enumerate(s):
    d[si].add(i, 1)

for i in range(q):
    k, x, y = input().split()
    if k == '1':
        x = int(x) - 1
        d[s[x]].add(x, -1)
        d[y].add(x, 1)
        s[x] = y
    else:
        l = int(x) - 1
        r = int(y) - 1
        ans = 0
        for v in d.values():
            ans += (v.sum(r + 1) - v.sum(l)) > 0
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import collections

def main():
    n = int(input())

    s = list(input())

    q = int(input())

    li = list(s)

    d = {}

    for i in range(26):
        d[chr(i + 97)] = []

    for i, x in enumerate(s):
        d[x].append(i)


    for _ in range(q):
        a, *x = input().split()

        if a == "1":
            i = int(x[0]) - 1
            c = x[1]
            o = li[i]
            index = bisect.bisect_left(d[o], i)
            d[o].pop(index)
            d[c].insert(bisect.bisect_left(d[c], i), i)
            li[i] = c
        else:
            l = int(x[0]) - 1
            r = int(x[1]) - 1
            cnt = 0
            for v in d.values():
                if len(v) == 0:
                    continue
                index = bisect.bisect_left(v, l)
                if index == len(v):
                    continue
                if v[index] <= r:
                    cnt += 1
            print(cnt)

main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import math
 
def solve(N, S, Q, queries):
    def update(i, c):
        cc = values[i]
        buckets[i//sN][cc] -= 1
        buckets[i//sN][c] += 1
        values[i] = c
 
    def count(l, r):
        res = [0] * (ord('z')-ord('a')+1)
        for i in range(sN):
            ll = i * sN
            rr = ll + sN
            if r <= ll or rr <= l:
                continue
            if l <= ll and rr <= r:
                for i, v in enumerate(buckets[i]):
                    res[i] += v
            else:
                for i in range(max(l, ll), min(r, rr)):
                    res[values[i]] += 1
        return sum(n > 0 for n in res)
        
    sN = math.ceil(N ** 0.5)
    values = [ord(c)-ord('a') for c in S]
    buckets = [[0] * (ord('z')-ord('a')+1) for _ in range(sN)]
    for i, v in enumerate(values):
        buckets[i//sN][v] += 1
    for t, x, y in queries:
        if t == 1:
            update(int(x)-1, ord(y)-ord('a'))
        else:
            yield count(int(x)-1, int(y))
 
# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    S = next(tokens)
    Q = int(next(tokens))
    queries = [(int(next(tokens)), next(tokens), next(tokens)) for _ in range(Q)]
    for result in solve(N, S, Q, queries):
        print(result)
 
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import math

def solve(N, S, Q, queries):
    def update(i, c):
        cc = values[i]
        buckets[i//sN][cc] -= 1
        buckets[i//sN][c] += 1
        values[i] = c

    def count(l, r):
        res = [0] * (ord('z')-ord('a')+1)
        for i in range(sN):
            ll = i * sN
            rr = ll + sN
            if r <= ll or rr <= l:
                continue
            if l <= ll and rr <= r:
                for i, v in enumerate(buckets[i]):
                    res[i] += v
            else:
                for i in range(max(l, ll), min(r, rr)):
                    res[values[i]] += 1
        return sum(n > 0 for n in res)
        
    sN = math.ceil(N ** 0.5)
    values = [ord(c)-ord('a') for c in S]
    buckets = [[0] * (ord('z')-ord('a')+1) for _ in range(sN)]
    for i, v in enumerate(values):
        buckets[i//sN][v] += 1
    for t, x, y in queries:
        if t == 1:
            update(int(x)-1, ord(y)-ord('a'))
        else:
            yield count(int(x)-1, int(y))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))
    S = next(tokens)
    Q = int(next(tokens))
    queries = [(int(next(tokens)), next(tokens), next(tokens)) for _ in range(Q)]
    for result in solve(N, S, Q, queries):
        print(result)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import bisect

alphabet="abcdefghijklmnopqrstuvwxyz"

bS = int(input())
S= input()
nQ = int(input())

S = [i for i in S]

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

locs =defaultdict(list)

for i,char in enumerate(S):
    locs[char].append(i)
    
def countChars(iter,ss,ee):
  nChar = 0
  for i in alphabet:
    if len(locs[i]) == 0:
      pass
    else:
      sptr = bisect.bisect_right(locs[i],ss)
      eptr = bisect.bisect_left(locs[i],ee)
      if sptr == eptr:
        if sptr < 1 or sptr > len(locs[i]):
          continue
        else:
          if locs[i][sptr-1] == ss:
            nChar+=1
      else:
        nChar += 1
  return nChar
    
  
res = []
for iter,iQ in enumerate(query):
  if int(iQ[0]) == 2:
    res.append(str( countChars(iter,int(iQ[1])-1,int(iQ[2])) ))
  if int(iQ[0]) == 1:
    location = int(iQ[1])-1
    curChar  = S[location]
    if curChar != iQ[2]:
      locs[curChar].remove(location) #remove from old
      bisect.insort(locs[iQ[2]],location)
      S[location] = iQ[2]
      
print(" ".join(res))

Submission status: Time Limit Exceeded

Solution code:
def ctoi(c):  # a~zを0~25に変換する(各アルファベットを数字に変換する)
    return ord(c) - 97


N = int(input())
S = list(input())
bits = [[0]*(N+1) for _ in range(26)]  # Binary Indexed Treeを26種類の各アルファベットについてもつ(0初期化, 1-index)


def BIT_query(idx):  # 各文字について1からidx番目までの文字数を数える
    res = [0]*26
    for i in range(26):
        tmp = 0
        p = idx
        while p > 0:  # 1からidx番目までの要素の和を取る
            tmp += bits[i][p]
            p -= p&(-p)  # 区間の長さを引くことで次のindexを得ることができる
        res[i] = tmp
    return res


def BIT_update(idx, alphabet, x):  # alphabet番目のアルファベットについてidx番目の要素の値にxを加える
    while idx <= N:  # idx番目の要素を含む全ての要素についてxを加える
        bits[alphabet][idx] += x
        idx += idx&(-idx)


for i in range(N):  # 各BITを与えられた文字列で初期化する
    BIT_update(i+1, ctoi(S[i]), 1)  # Sのi番目(0-index)の文字に対応するBITのi+1番目の要素を1として更新する

Q = int(input())
for _ in range(Q):
    flag, a, b = map(str, input().split())
    flag = int(flag)
    a = int(a)
    if flag == 1:
        if S[a-1] == b:  # 同じ文字の場合, 変更しない
            continue
        else:
            BIT_update(a, ctoi(S[a-1]), -1)  # a番目の要素を別のものに変えるので、-1
            BIT_update(a, ctoi(b), 1)  # a番目の要素を文字bに変えるので+1
            S[a-1] = b  # 文字列のa番目の文字を変更する
    elif flag == 2:  # aとbは区間の左端と右端
        b = int(b)
        cnt1 = BIT_query(b)  # 1からbまでの各文字の文字数
        cnt2 = BIT_query(a-1)  # 1からa-aまでの各文字の文字数
        ans = 0
        for i in range(26):
            if cnt1[i]-cnt2[i] > 0:  # lからrまでのその文字の文字数が1以上であれば、その文字はlからrまでの部分文字列に現れるので種類数を1増やす
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = list(input())

    c = lambda x: ord(x) - ord('a')
    tree = [SegmentTree(N, lambda x,y:x|y) for _ in range(26)]
    for i, l in enumerate(S):
        tree[c(l)].update(i, 1)

    Q = int(input())
    for _ in range(Q):
        t, a, b = input().split()
        if t == '1':
            a = int(a) - 1
            tree[c(S[a])].update(a, 0)
            tree[c(b)].update(a, 1)
            S[a] = b
        else:
            a, b = int(a)-1, int(b)-1
            ans = 0
            for i in range(26):
                t = tree[i].query(a, b+1)
                ans += 1 if t else 0
            print(ans)

class SegmentTree:
    def __init__(self, n=None, f=max, zero_factory=int, initial_values=None):
        assert(n, initial_values)
        size = n if n else len(initial_values)
        self.__f, self.__z, = f, zero_factory
        self.__n = 1 << ((size - 1).bit_length())
        self.__dat = [zero_factory() for _ in range(2 * self.__n)]
        if initial_values:
            zi = self.__get_leaf(0)
            for i, v in enumerate(initial_values): self.__dat[zi + i] = v
            for i in range(zi-1, -1, -1): self.__dat[i] = f(*self.__get_children(i))

    def update(self, index, value):
        i, v = self.__get_leaf(index), value
        if self.__dat[i] == v: return
        self.__dat[i] = v
        while i:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__z()
        if to_exclusive <= from_inclusive: return ans
        l, r = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        while r - l > 1:
            if self.__is_right(l): ans = self.__f(ans, self.__dat[l])
            if self.__is_left(r): ans, r = self.__f(ans, self.__dat[r]), r-1
            l, r = l//2, self.__get_parent(r)
        ans = self.__f(ans, self.__dat[l])
        if l != r: ans = self.__f(ans, self.__dat[r])
        return ans

    def __get_leaf(self, i): return self.__n + i - 1
    def __get_parent(self, i): return (i-1)//2
    def __get_children(self, i): return (self.__dat[2*i+1], self.__dat[2*i+2])
    def __is_left(self, i): return i&1 == 1
    def __is_right(self, i): return i&1 == 0

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = list(input())

    c = lambda x: ord(x) - ord('a')
    tree = [SegmentTree(N, lambda x,y:x|y) for _ in range(26)]
    for i, l in enumerate(S):
        tree[c(l)].update(i, 1)

    Q = int(input())
    for _ in range(Q):
        t, a, b = input().split()
        if t == '1':
            a = int(a) - 1
            tree[c(S[a])].update(a, 0)
            tree[c(b)].update(a, 1)
            S[a] = b
        else:
            a, b = int(a)-1, int(b)-1
            ans = 0
            for i in range(26):
                t = tree[i].query(a, b+1)
                ans += 1 if t else 0
            print(ans)

class SegmentTree:
    def __init__(self, n=None, f=max, zero_factory=int, converter=lambda x:x, initial_values=None):
        assert(n, initial_values)
        size = n if n else len(initial_values)
        self.__f, self.__z, self.__c = f, zero_factory, converter
        self.__n = 1 << ((size - 1).bit_length())
        self.__dat = [zero_factory() for _ in range(2 * self.__n)]
        if initial_values:
            zi = self.__get_leaf(0)
            for i, v in enumerate(initial_values): self.__dat[zi + i] = converter(v)
            for i in range(zi-1, -1, -1): self.__dat[i] = f(*self.__get_children(i))

    def update(self, index, value):
        i, v = self.__get_leaf(index), self.__c(value)
        if self.__dat[i] == v: return
        self.__dat[i] = v
        while i:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__z()
        if to_exclusive <= from_inclusive: return ans
        l, r = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        while r - l > 1:
            if self.__is_right(l): ans = self.__f(ans, self.__dat[l])
            if self.__is_left(r): ans, r = self.__f(ans, self.__dat[r]), r-1
            l, r = l//2, self.__get_parent(r)
        ans = self.__f(ans, self.__dat[l])
        if l != r: ans = self.__f(ans, self.__dat[r])
        return ans

    def __get_leaf(self, i): return self.__n + i - 1
    def __get_parent(self, i): return (i-1)//2
    def __get_children(self, i): return (self.__dat[2*i+1], self.__dat[2*i+2])
    def __is_left(self, i): return i&1 == 1
    def __is_right(self, i): return i&1 == 0

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N = int(input())
    S = list(input())

    c = lambda x: ord(x) - ord('a')
    tree = [SegmentTree(N) for _ in range(26)]
    for i, l in enumerate(S):
        tree[c(l)].update(i, 1)

    Q = int(input())
    for _ in range(Q):
        t, a, b = input().split()
        if t == '1':
            a = int(a) - 1
            tree[c(S[a])].update(a, 0)
            tree[c(b)].update(a, 1)
            S[a] = b
        else:
            a, b = int(a)-1, int(b)-1
            ans = 0
            for i in range(26):
                t = tree[i].query(a, b+1)
                ans += 1 if t else 0
            print(ans)

class SegmentTree:
    def __init__(self, n=None, f=max, zero_factory=int, converter=lambda x:x, initial_values=None):
        assert(n, initial_values)
        size = n if n else len(initial_values)
        self.__f, self.__z, self.__c = f, zero_factory, converter
        self.__n = 1 << ((size - 1).bit_length())
        self.__dat = [zero_factory() for _ in range(2 * self.__n)]
        if initial_values:
            zi = self.__get_leaf(0)
            for i, v in enumerate(initial_values): self.__dat[zi + i] = converter(v)
            for i in range(zi-1, -1, -1): self.__dat[i] = f(*self.__get_children(i))

    def update(self, index, value):
        i, v = self.__get_leaf(index), self.__c(value)
        if self.__dat[i] == v: return
        self.__dat[i] = v
        while i:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__z()
        if to_exclusive <= from_inclusive: return ans
        l, r = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        while r - l > 1:
            if self.__is_right(l): ans = self.__f(ans, self.__dat[l])
            if self.__is_left(r): ans, r = self.__f(ans, self.__dat[r]), r-1
            l, r = l//2, self.__get_parent(r)
        ans = self.__f(ans, self.__dat[l])
        if l != r: ans = self.__f(ans, self.__dat[r])
        return ans

    def __get_leaf(self, i): return self.__n + i - 1
    def __get_parent(self, i): return (i-1)//2
    def __get_children(self, i): return (self.__dat[2*i+1], self.__dat[2*i+2])
    def __is_left(self, i): return i&1 == 1
    def __is_right(self, i): return i&1 == 0

if __name__ == '__main__':
    main()