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:
from math import ceil, log
from operator import __or__

N = int(input())
S = input()
Q = int(input())
Query = [input().split() for _ in range(Q)]

ABC = dict(zip("abcdefghijklmnopqrstuvwxyz", range(26)))


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.init_value = init_value
        self.aggfunc = aggfunc

        self.data = [init_value] * ((1 << (1 + ceil(log(length, 2)))) - 1)
        self.origin = len(self.data) >> 1

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[(i << 1) + 1], self.data[(i << 1) + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self.origin + 1)

    def _query(self, start, stop, k, l, r):
        if (start <= l) & (r <= stop):
            return self.data[k]
        elif (r <= start) | (stop <= l):
            return self.init_value
        else:
            return self.aggfunc(
                self._query(start, stop, (k << 1) + 1, l, (l + r) >> 1),
                self._query(start, stop, (k << 1) + 2, (l + r) >> 1, r),
            )


S2 = [ABC[s] for s in S]

segs = [SegmentTree(N, False, __or__) for _ in range(26)]
for i in range(N):
    segs[S2[i]].update(i, True)

for q1, q2, q3 in Query:
    if q1 == "1":
        i = int(q2) - 1
        segs[S2[i]].update(i, False)
        letter = ABC[q3]
        segs[letter].update(i, True)
        S2[i] = letter
    else:
        ans = sum(seg.query(int(q2) - 1, int(q3)) for seg in segs)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log
from operator import __or__

N = int(input())
S = input()
Q = int(input())
Query = [input().split() for _ in range(Q)]

abc = dict(zip("abcdefghijklmnopqrstuvwxyz", range(26)))

S2 = [abc[s] for s in S]


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.init_value = init_value
        self.aggfunc = aggfunc

        self.data = [init_value] * (2 ** (1 + ceil(log(length, 2))) - 1)
        self.origin = len(self.data) // 2

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self.origin + 1)

    def _query(self, start, stop, k, l, r):
        if (start <= l) & (r <= stop):
            return self.data[k]
        elif (r <= start) | (stop <= l):
            return self.init_value
        else:
            return self.aggfunc(
                self._query(start, stop, k * 2 + 1, l, (l + r) // 2),
                self._query(start, stop, k * 2 + 2, (l + r) // 2, r),
            )


segs = [SegmentTree(N, False, __or__) for _ in range(26)]
for i in range(N):
    segs[S2[i]].update(i, True)

for q1, q2, q3 in Query:
    if q1 == "1":
        i = int(q2) - 1
        segs[S2[i]].update(i, False)
        letter = abc[q3]
        segs[letter].update(i, True)
        S2[i] = letter
    else:
        ans = sum(seg.query(int(q2) - 1, int(q3)) for seg in segs)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
from math import ceil, log
from operator import __or__

N = int(input())
S = list(input())
Q = int(input())
Query = [input().split() for _ in range(Q)]

abc = dict(zip("abcdefghijklmnopqrstuvwxyz", range(26)))


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.init_value = init_value
        self.aggfunc = aggfunc

        self.data = [init_value] * (2 ** (1 + ceil(log(length, 2))) - 1)
        self.origin = len(self.data) // 2

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self.origin + 1)

    def _query(self, start, stop, k, l, r):
        if (start <= l) & (r <= stop):
            return self.data[k]
        elif (r <= start) | (stop <= l):
            return self.init_value
        else:
            return self.aggfunc(
                self._query(start, stop, k * 2 + 1, l, (l + r) // 2),
                self._query(start, stop, k * 2 + 2, (l + r) // 2, r),
            )


segs = [SegmentTree(N, False, __or__) for _ in range(26)]
for i in range(N):
    letter = abc[S[i]]
    segs[letter].update(i, True)

for q1, q2, q3 in Query:
    if q1 == "1":
        i = int(q2) - 1
        letter = abc[S[i]]
        segs[letter].update(i, False)
        letter = abc[q3]
        segs[letter].update(i, True)
        S[i] = q3
    else:
        ans = sum(seg.query(int(q2) - 1, int(q3)) for seg in segs)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
s=list(input())
a={chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    a[c].append(i+1)
for i in range(int(input())):
    p,q,r=list(map(str,input().split()))
    if p=="1":q=int(q);b=s[q-1];a[b].pop(bisect.bisect_left(a[b],q));bisect.insort(a[r],q);s[q-1]=r
    else:
        d=0
        for l in a.values():
            g=bisect.bisect_left(l,int(q))
            if g<len(l) and l[g]<=int(r):d+=1
        print(d)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
s=list(input())
a={chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    bisect.insort(a[c],i+1)
for i in range(int(input())):
    p,q,r=list(map(str,input().split()))
    if p=="1":q=int(q);b=s[q-1];a[b].pop(bisect.bisect_left(a[b],q));bisect.insort(a[r],q);s[q-1]=r
    else:
        d=0
        for l in a.values():
            g=bisect.bisect_left(l,int(q))
            if g<len(l) and l[g]<=int(r):
                d+=1
        print(d)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n=int(input())
s=list(input())
a={chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    a[c].append(i+1)
for i in range(int(input())):
    p,q,r=list(map(str,input().split()))
    if p=="1":q=int(q);b=s[q-1];a[b].pop(bisect.bisect_left(a[b],q));bisect.insort(a[r],q);s[q-1]=r
    else:
        d=0
        for l in a.values():
            g=bisect.bisect_left(l,int(q))
            if g<len(l) and l[g]<=int(r):d+=1
        print(d)

Submission status: Time Limit Exceeded

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

for i in range(q):
    t, il, cr = input().split()
    if t == '1':
        s[int(il)-1] = cr
    elif t == '2':
        print(len(set(s[int(il)-1:int(cr)])))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
r = []
for _ in range(Q):
    qt, f, s = input().split()
    f = int(f)
    if int(qt) == 1:
        S[f-1] = s
    else: 
        s = int(s)
        r.append(len(set(S[f-1:s])))

for i in r: 
    print(i)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
Qs = [list(input().split()) for i in range(Q)]

for query in Qs:
    if query[0] == '1':
        S[int(query[1])-1] = query[2]
    else:
        print(len(set(S[int(query[1])-1:int(query[2])])))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
s = list(input())
q = int(input())
def type1(s, i, c):
    if s[i-1] == c:
        pass
    else:
        s[i-1] = c
    return None

def type2(s, l, r):
    l1 = s[l-1:r]
    l2 = list(set(l1))
    return len(l2)

listof3 = []
for i in range(q):
    listof3.append(list(input().split()))

for [a,b,c] in listof3:
    if a == "1":
        b = int(b)
        type1(s, b, c)
    elif a == "2":
        b = int(b)
        c = int(c)
        print(type2(s, b, c))

Submission status: Time Limit Exceeded

Solution code:
#input
N = int(input())
S = list(input())
Q = int(input())
Query = [input() for _ in range(Q)]

# process/output
for q in Query:
    t, x, y = q.split()
    if t == "1":
        S[int(x)-1] = y
    else:
        print(len(set(S[int(x)-1:int(y)])))

Submission status: Time Limit Exceeded

Solution code:
#input
N = int(input())
S = list(input())
Q = int(input())
Query = []
for _ in range(Q):
    t, x, y = input().split()
    if t == "1":
        Query.append((t, int(x)-1, y))
    else:
        Query.append((t, int(x)-1, int(y)))

# process/output
for q in Query:
    if q[0] == "1":
        S[q[1]] = q[2]
    else:
        print(len(set(S[q[1]:q[2]])))

Submission status: Time Limit Exceeded

Solution code:
#import numpy as np
#import sys
#sys.setrecursionlimit(10**7)
#from functools import reduce
#from fractions import gcd

#from collections import deque
#dq = deque([(r, c)])
#while dq:
#    cr, cc = dq.popleft()
            

#input
N = int(input())
S = list(input())
Q = int(input())
Query = []
for _ in range(Q):
    t, x, y = input().split()
    if t == "1":
        Query.append((int(t), int(x)-1, y))
    else:
        Query.append((int(t), int(x)-1, int(y)))

# process/output
for q in Query:
    if q[0] == 1:
        S[q[1]] = q[2]
#        print(S)
    else:
        sl = S
        print(len(set(sl[q[1]:q[2]])))

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

alpha_map = {chr(i):[] for i in range(97,123)}
for i,c in enumerate(s):
    bisect.insort(alpha_map[c],i+1)
    
for _ in range(q):
    x,y,z = map(str,input().split())
    if int(x) == 1:
        y = int(y)
        bef = s[y-1]
        if bef == z:
            continue
        alpha_map[bef].pop(bisect.bisect_left(alpha_map[bef],y))
        bisect.insort(alpha_map[z],y)
        s = s[:y-1]+z+s[y:]
    else:
        count = 0
        for i,j in alpha_map.items():
            idx = bisect.bisect_left(j,int(y))
            if idx < len(j) and j[idx] <= int(z):
                    count += 1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
class BinaryIndexTree:  # 1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


if __name__ == "__main__":
    N = int(input())
    S = list(input())
    d = {x: i for i, x in enumerate("abcdefghijklmnopqrstuvwxyz")}
    BIT = [BinaryIndexTree(N) for _ in range(26)]

    # initialize
    for i, s in enumerate(S, start=1):
        BIT[d[s]].add(i, 1)

    Q = int(input())
    ans = []
    for _ in range(Q):
        query, x, y = input().split()
        if query == "1":
            i = int(x)
            c_new = y
            c_old = S[i - 1]
            BIT[d[c_new]].add(i, 1)
            BIT[d[c_old]].add(i, -1)
            S[i - 1] = c_new
        else:
            cnt = 0
            l = int(x) - 1
            r = int(y)
            for b in BIT:
                tmp = b.sum(r) - b.sum(l)
                if tmp:
                    cnt += 1
            ans.append(cnt)

    print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

alpha = [chr(i) for i in range(97,123)]
alpha_map = {i:[] for i in alpha}
for i,c in enumerate(s):
    bisect.insort(alpha_map[c],i+1)
    
for _ in range(q):
    x,y,z = map(str,input().split())
    if int(x) == 1:
        y = int(y)
        bef = s[y-1]
        alpha_map[bef].pop(bisect.bisect_left(alpha_map[bef],y))
        bisect.insort(alpha_map[z],y)
        s = s[:y-1]+z+s[y:]
    else:
        count = 0
        for i in alpha:
            if len(alpha_map[i]) > 0:
                idx = bisect.bisect_left(alpha_map[i],int(y))
                if idx < len(alpha_map[i]) and alpha_map[i][idx] <= int(z):
                    count += 1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())
Query = []
for i in range(Q):
  Query.append(list(map(str, input().split())))

for i in range(Q):
  if Query[i][0] == '1':
    if Query[i][1]=='1':
      S = Query[i][2] + S[1:]
    elif int(Query[i][1]) == N:
      S = S[:N-1] + Query[i][2]
    else:
      S = S[:int(Query[i][1])-1] + Query[i][2] + S[int(Query[i][1]):]
  elif Query[i][0] == '2':
    ii = int(Query[i][1])
    jj = int(Query[i][2])
    SS = S[ii-1:jj]
    ss = []
    for m in range(len(SS)):
      add = False
      for n in range(len(ss)):
        if ss[n] == SS[m]:
          add = True
          break
      if not add:
        ss.append(SS[m])
    print(len(ss))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

Query = [[0] * 3 for i in range(Q)]
for i in range(Q):
    temp = input().split()
    Query[i][0] = temp[0]
    Query[i][1] = temp[1]
    Query[i][2] = temp[2]

for Q_temp in Query:
    if int(Q_temp[0]) is 1:
        S[int(Q_temp[1]) - 1] = Q_temp[2]
    else:
        output = Counter(S[int(Q_temp[1]) - 1: int(Q_temp[2])])
        print(len(output))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

Query = [[0] * 3 for i in range(Q)]
for i in range(Q):
    temp = input().split()
    Query[i][0] = temp[0]
    Query[i][1] = temp[1]
    Query[i][2] = temp[2]

for Q_temp in Query:
    if int(Q_temp[0]) is 1:
        S[int(Q_temp[1]) - 1] = Q_temp[2]
    else:
        output = collections.Counter(S[int(Q_temp[1]) - 1: int(Q_temp[2])])
        print(len(output))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

Query = []
for i in range(Q):
    Query.append(input().split())

for Q_temp in Query:
    if int(Q_temp[0]) is 1:
        S[int(Q_temp[1]) - 1] = Q_temp[2]
    else:
        output = collections.Counter(S[int(Q_temp[1]) - 1: int(Q_temp[2])])
        print(len(output))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

Query = []
for i in range(Q):
    Query.append(input().split())
    Query[i][0] = int(Query[i][0])
    Query[i][1] = int(Query[i][1]) - 1
    if Query[i][0] is 2:
        Query[i][2] = int(Query[i][2])

for Q_temp in Query:
    if Q_temp[0] is 1:
        S[Q_temp[1]] = Q_temp[2]
    else:
        output = collections.Counter(S[Q_temp[1]:Q_temp[2]])
        print(len(output))

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
class SegmentTree:
    def segfunc(self,x,y):
        #ここに評価
        po = [0 for i in range(26)]
        for i in range(26):
            po[i] = x[i]+y[i]
        return po

    #nは総数、initがlist,ide_eleが元
    def __init__(self,n,init,ide_ele):
        self.n = n
        self.ide_ele = ide_ele
        self.num = 2**(n-1).bit_length()
        self.seg = [ide_ele for i in range(2*self.num)]
        for i in range(n):
            self.seg[i+self.num-1] = init[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[2*k+1],self.seg[2*k+2])
    
    def query(self,p,q):
        if q <= p:
            po = [0] * 26
            po[0] = 1
            return po
        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 //= 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 solver():
    n = onem()
    s = input().split()[0]
    po = onem()

    abc = [[0 for i in range(26)] for j in range(n)]

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

    Se = SegmentTree(n,abc,[0 for i in range(26)])



    for i in range(po):
        a,b,c = input().split()
        a = int(a)
        b = int(b)
        if a == 1:
            ppp = [0] * 26
            ppp[ord(c) - ord('a')] = 1
            Se.update(b-1,ppp)      
        else:
            c = int(c)
            op = Se.query(b-1,c)
            co = 0
            for i in range(26):
                if op[i] >= 1:
                    co += 1
            print(co)


if __name__ == "__main__":
    solver()

Submission status: Time Limit Exceeded

Solution code:
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): #intのlist
    return list(map(int,input().split()))
def m(): #複数文字
    return map(int,input().split())
def onem(): #Nとかの取得
    return int(input())
def s(x): #圧縮
    a = []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): #listをスペースごとに分ける
    return " ".join(map(str,x))
def max2(x): #他のときもどうように作成可能
    return max(map(max,x))
def In(x,a): #aがリスト(sorted)
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False
"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""
class SegmentTree:
    def segfunc(self,x,y):
        #ここに評価
        po = [0 for i in range(26)]
        for i in range(26):
            po[i] = x[i]+y[i]
        return po

    #nは総数、initがlist,ide_eleが元
    def __init__(self,n,init,ide_ele):
        self.n = n
        self.ide_ele = ide_ele
        self.num = 2**(n-1).bit_length()
        self.seg = [ide_ele for i in range(2*self.num)]
        for i in range(n):
            self.seg[i+self.num-1] = init[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[2*k+1],self.seg[2*k+2])
    
    def query(self,p,q):
        if q <= p:
            return [1 if i == 0 else 0 for i in range(26)]
        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 //= 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 solver():
    n = onem()
    s = input().split()[0]
    po = onem()

    abc = [[0] * 26 for j in range(n)]

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

    Se = SegmentTree(n,abc,[0 for i in range(26)])



    for i in range(po):
        a,b,c = input().split()
        a = int(a)
        b = int(b)
        if a == 1:
            ppp = [0] * 26
            ppp[ord(c) - ord('a')] = 1
            Se.update(b-1,ppp)      
        else:
            c = int(c)
            op = Se.query(b-1,c)
            co = 0
            for i in range(26):
                if op[i] >= 1:
                    co += 1
            print(co)


if __name__ == "__main__":
    solver()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
r = []
for _ in range(Q):
    qt, f, s = input().split()
    f = int(f)
    if int(qt) == 1:
        S[f-1] = s
    else: 
        s = int(s)
        r.append(len({k:0 for k in S[f-1:s]}.keys()))

for i in r: 
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import sys

read = sys.stdin.read
readline = sys.stdin.readline


class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [[0] * (n + 1) for _ in range(26)]

    def build_tree(self, s):
        for idx, i in enumerate(s[1:], 1):
            for j in range(26):
                tmp = idx
                if j == i:
                    cnt = 1
                else:
                    cnt = 0
                cnt += self.bit_query(j, idx - 1) - self.bit_query(j, idx - (idx & (-idx)))
                self.tree[j][idx] = cnt

    def bit_query(self, character, idx):
        if idx == 0:
            return 0
        sum_of_query = 0
        while idx > 0:
            sum_of_query += self.tree[character][idx]
            idx -= idx & (-idx)
        return sum_of_query

    def update(self, character, idx, x):
        while idx <= self.n:
            self.tree[character][idx] += x
            idx += idx & (-idx)
        return


N = int(input())
S = [i - 97 for i in map(ord, list(input()))]
S = [-1] + S
Q, *query = map(str, read().split())
bit = BIT(N)
bit.build_tree(S)
for a, b, c in zip(*[iter(query)] * 3):
    b = int(b)
    if a == '1':
        c = ord(c) - 97
        if S[b] == c:
            continue
        bit.update(c, b, 1)
        bit.update(S[b], b, -1)
        S[b] = c
    else:
        c = int(c)
        print(sum(1 for i in range(26) if bit.bit_query(i, c) - bit.bit_query(i, b - 1) > 0))

Submission status: Time Limit Exceeded

Solution code:

l=int(input())
s=list(input())
t1=int(input())
for i in range(t1):
    a=input()
    t=a.split(" ")
    if int(t[0])==2:
        subs=s[int(t[1])-1:int(t[2])]
        print(len(set(subs)))
    elif int(t[0])==1:
        s[ int(t[1])-1 ]=t[2]

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
from functools import reduce
from operator import or_
from collections import defaultdict

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    N=len(S)
    lo, hi = 1, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = lo
    S1 = [None] * nn

    for i in range(nn):
        sd = S1[i] = defaultdict(int)
        i1 = i * nn
        for j in range(i1, min(N, i1+nn)):
            sd[S[j]] += 1

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            c1 = S[i]
            i1 = i // nn
            S1[i1][c1] -= 1
            S[i] = j
            S1[i1][j] += 1
        elif cmd == "2":
            j = int(j)

            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            if ia < ja:
                ss = set(k for i1 in range(ia, ja) for k, v in S1[i1].items() if v > 0)

                if ib > 0:
                    for i1 in range(i, i-ib+nn):
                        ss.add(S[i1])
                if jb > 0:
                    for i1 in range(ja*nn, j):
                        ss.add(S[i1])
            else:
                ss = set(S[k] for k in range(i, j))

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
from functools import reduce
from operator import or_

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    N=len(S)
    lo, hi = 100, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = lo
    S1 = [None] * nn

    for i in range(nn):
        i1 = i * nn
        S1[i] = set(S[j] for j in range(i1, min(N, i1+nn)))

    ans = []
    rebuild = set()
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            i1 = i // nn
            S[i] = j
            rebuild.add(i1)
        elif cmd == "2":
            j = int(j)

            for i1 in rebuild:
                i2 = i1 * nn
                S1[i1] = set(S[k] for k in range(i2, min(N, i2+nn)))
            rebuild.clear()

            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            if ia < ja:
                ss = set()
                ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

                if ib > 0:
                    for i1 in range(i, i-ib+nn):
                        ss.add(S[i1])
                if jb > 0:
                    for i1 in range(ja*nn, j):
                        ss.add(S[i1])
            else:
                ss = set(S[k] for k in range(i, j))

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
from functools import reduce
from operator import or_

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    N=len(S)
    lo, hi = 100, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = lo
    S1 = [None] * nn

    for i in range(nn):
        i1 = i * nn
        S1[i] = set(S[j] for j in range(i1, min(N, i1+nn)))

    ans = []
    rebuild = set()
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            i1 = i // nn
            S[i] = j
            rebuild.add(i1)
        elif cmd == "2":
            j = int(j)

            for i1 in rebuild:
                i2 = i1 * nn
                S1[i1] = set(S[k] for k in range(i2, min(N, i2+nn)))

            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            if ia < ja:
                ss = set()
                ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

                if ib > 0:
                    for i1 in range(i, i-ib+nn):
                        ss.add(S[i1])
                if jb > 0:
                    for i1 in range(ja*nn, j):
                        ss.add(S[i1])
            else:
                ss = set(S[k] for k in range(i, j))

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
#!python3

import sys
from functools import reduce
from operator import or_

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    N=len(S)
    lo, hi = 100, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = lo
    S1 = [None] * nn

    for i in range(nn):
        i1 = i * nn
        S1[i] = set(S[j] for j in range(i1, min(N, i1+nn)))

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            i1 = i // nn
            S[i] = j
            i2 = i1 * nn
            S1[i1] = set(S[k] for k in range(i2, min(N, i2+nn)))
        elif cmd == "2":
            j = int(j)
            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            if ia < ja:
                ss = set()
                ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

                if ib > 0:
                    for i1 in range(i, i-ib+nn):
                        ss.add(S[i1])
                if jb > 0:
                    for i1 in range(ja*nn, j):
                        ss.add(S[i1])
            else:
                ss = set(S[k] for k in range(i, j))

            ans.append(len(ss))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

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