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 collections import defaultdict

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

w = 800
sl = []
dl = []
for i in range((n+w-1)//w):
    ss = s[i*w:min((i+1)*w,n)]
    dl.append(set(ss))
    sl.append(ss)
if len(dl)%2==1:
    dl.append(set())
dl2 = []
for i in range(len(dl)//2):
    dl2.append(dl[2*i] | dl[2*i+1])
for i in range(q):
    if ql[i][0]=="1":
        idx = int(ql[i][1])-1
        c = ql[i][2]

        ss = sl[idx//w]
        ss[idx%w] = c
        s[idx] = c
        sl[idx//w] = ss
        dl[idx//w] = set(ss)
        if (idx//w)%2==0:
            dl2[idx//w//2] = dl[idx//w] | dl[idx//w+1]
        else:
            dl2[idx//w//2] = dl[idx//w-1] | dl[idx//w]
    else:
        l = int(ql[i][1])-1
        r = int(ql[i][2])-1

        li = l//w
        ri = r//w
        if abs(li-ri)<2:
            print(len(set(s[l:r+1])))
        else:
            u = set(sl[li][l%w:])
            u = u | set(sl[ri][:r%w+1])
            if (li+1)%2==1:
                u = u | dl[li+1]
                li += 1
            if (ri-1)%2==0:
                u = u | dl[ri-1]
                ri -= 1
            for j in range(li+1,ri,2):
                u = u | dl2[j//2]
            print(len(u))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
for i in range(Q):
  q = input().split()
  if int(q[0])==1:
    iq,cq = int(q[1])-1,q[2]
    S[iq] = cq
  elif int(q[0])==2:
    lq,rq = map(int, q[1:])
    print(len(set(S[lq-1:rq])))

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
S = input()
Q = int(input())
querys = [input().split() for i in range(Q)]
for i in range(Q):
    if querys[i][0] == "1":
        S = S[:int(querys[i][1])-1] + querys[i][2] + S[int(querys[i][1]):]
    else:
        c = collections.Counter(S[int(querys[i][1]) - 1:int(querys[i][2])])
        print(len(c))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    s = list(input())
    q = int(input())
    qry = []
    ans = []
    for _ in range(q):
        qq  = input().split()
        qry.append(qq)
        if int(qq[0]) == 1:
            s[int(qq[1])-1] = qq[2]
        else:
            tmp = s[int(qq[1])-1:int(qq[2])]
            ans.append(len(set(tmp)))
    for _,a in enumerate(ans):
        print(a)

    # for i, query in enumerate(qry):
    #     if int(query[0]) == 1:
    #         s[int(query[1])-1] = query[2]
    #     else:
    #         tmp = s[int(query[1])-1:int(query[2])]
    #         print(len(set(tmp)))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    input()
    S = list(input())
    for q in range(int(input())):
        a, b, c = input().split(' ')
        if a == '1':
            S[int(b) - 1] = c
        if a == '2':
            print(len(set(S[int(b) - 1:int(c)])))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n = int(input())
s = list(input())
s = np.asarray(s)
q = int(input())

for i in range(q):
    select, v1, v2 = input().split()
    if select == "1":
        s[int(v1)-1] = v2
    if select == "2":
        print(len(set(s[int(v1)-1:int(v2)])))

Submission status: Time Limit Exceeded

Solution code:


def solv(N, S, Q):
    ans = []
    S = [c for c in S]
    for q in Q:
        if q[0] == 1:
            S[q[1]-1] = q[2]
        else:
            ans.append(len(set(S[q[1]-1:q[2]])))
    return ans


if __name__ == "__main__":

    # N
    # S
    # Q
    # Query_1
    # \vdots
    # Query_Q
    #
    N = int(input())
    S = input()
    QN = int(input())
    Q = []
    for _ in range(QN):
        t, a, b = input().split()
        if t == "1":
            Q.append((1, int(a), b))
        else:
            Q.append((2, int(a), int(b)))

    ans = solv(N, S, Q)

    for a in ans:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
import string
import numpy
import functools
L = len(string.ascii_lowercase)


class BIT:

    def __init__(self, N):
        self.bit = numpy.zeros((N + 1, L), dtype=numpy.int32)
        self.N = N

    @functools.lru_cache(maxsize=20480)
    def sum_all(self, i):
        s = numpy.zeros(L, dtype=numpy.int32)
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x, c):
        c = ord(c) - ord('a')
        while i <= self.N:
            self.bit[i][c] += x
            i += i & -i
        self.sum_all.cache_clear()

def solve(N, S, Q, query):
    bits = BIT(N)

    for i, c in enumerate(S):
        bits.add(i + 1, 1, c)

    ans = []
    for q, i, cr in query:
        if q == "1":
            i = int(i)
            if S[i-1] != cr:
                bits.add(i, -1, S[i-1])
                bits.add(i, 1, cr)
                S[i-1] = cr
        else:
            l = int(i)
            r = int(cr)
            diff = bits.sum_all(r) - bits.sum_all(l)
            k = ord(S[l-1]) - ord('a')
            diff[k] += 1
            ans.append(str(numpy.count_nonzero(diff)))
    return "\n".join(ans)

if __name__ == "__main__":
    N = int(input())
    S = list(input())
    Q = int(input())

    query = []
    for _ in range(Q):
        query.append(tuple(input().split(" ")))
    print(solve(N, S, Q, query))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

d = {'a': 0, 'b': 1, 'c': 2, 'd': 3, 'e': 4, 'f': 5, 'g': 6, 'h': 7, 'i': 8, 'j': 9, 'k': 10, 'l': 11, 'm': 12, 'n': 13, 'o': 14, 'p': 15, 'q': 16, 'r': 17, 's': 18, 't': 19, 'u': 20, 'v': 21, 'w': 22, 'x': 23, 'y': 24, 'z': 25}

input = stdin.readline

n = int(input())

tree = [[0] * n * 2 for _ in range(26)]

def build(arr):
    for i in range(n):
        tree[ddd][n + i] = arr[i]

    for i in range(n - 1, 0, -1):
        tree[ddd][i] = tree[ddd][i << 1] + tree[ddd][i << 1 | 1]

def update(p, value):
    p += n
    tree[ddd][p] = value

    i = p

    while i > 1:
        tree[ddd][i >> 1] = tree[ddd][i] + tree[ddd][i ^ 1]
        i >>= 1

def query(l, r):
    res = 0

    l += n
    r += n

    while l < r:

        if l & 1:
            res += tree[ddd][l]
            l += 1

        if r & 1:
            r -= 1
            res += tree[ddd][r]

        l >>= 1
        r >>= 1

    return res

s = list(input())

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

for i in range(n):
    arrs[d[s[i]]][i] = 1

for ddd in range(26):
    build(arrs[ddd])

for _ in range(int(input())):
    t = input().split()

    if t[0] == '1':
        i, c = t[1:]
        i = int(i) - 1

        new = d[c]
        cur = d[s[i]]

        s[i] = c

        ddd = cur
        update(i, 0)

        ddd = new
        update(i, 1)

    if t[0] == '2':
        l, r = map(int, t[1:])
        l -= 1
        r -= 1

        ans = 0

        for ddd in range(26):
            if query(l, r + 1) != 0:
                ans += 1

        print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
q=int(input())
ss=[]

for i in range(n):
    ss.append(ord(s[i]))
for qq in range(q):
    t,i,c=input().split()
    if t=="1":
        ss[int(i)-1]=ord(c)
    else:
        qs=ss[int(i)-1:int(c)]
        qs.sort()
        ans=1
        for j in range(len(qs)-1):
            if qs[j]!=qs[j+1]:ans+=1
        print(ans)

Submission status: Time Limit Exceeded

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

for _ in range(q):
    m,l,r=input().split()
    
    if m=='1':
        s[int(l)-1]=r
    else:
        print(len(set(s[int(l)-1:int(r)])))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
for _ in range(Q):
    a, b, c = input().split()
    if a == '1':
        if S[int(b)-1] == c:
            continue
        S[int(b)-1] = c
    elif a == '2':
        print(len(set(S[int(b)-1: int(c)])))

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
t = input()
s = [t[i] for i in range(n)]
q = int(input())


for n in range(q):
    a,x,y = input().split()
    if a == "1":
        x = int(x)
        s[x-1] = y
    else:
        x,y = int(x),int(y)
        print(len(set(s[x-1:y])))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
def main():
    import sys
    input = sys.stdin.readline
    N = int(input())
    S = input()
    Q = int(input())
    S_list = list(S)
    Query = [input().split() for i in range(Q)]
    for q in Query:
        if q[0] == "1":
            a = int(q[1]) - 1
            S_list[a] = q[2]
        elif q[0] == "2":
            a = int(q[1]) -1
            b = int(q[2])
            print(len(set(S_list[a:b])))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
S = input()
Q = int(input())
querys = []
for i in range(Q):
    querys.append(input().split())
for i in range(Q):
    if querys[i][0] == "1":
        S = S[:int(querys[i][1])-1] + querys[i][2] + S[int(querys[i][1]):]
    else:
        c = collections.Counter(S[int(querys[i][1]) - 1:int(querys[i][2])])
        print(len(c))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import bisect

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

dictList=[defaultdict(int) for _ in range(n+1)]

for i in range(n):
    dictList[i+1]=dictList[i].copy()
    dictList[i+1][s[i]]+=1

ans_list=[]
change={}

#print(dictList)

for g in range(q):
    a,b,c=map(str,input().split())
    a=int(a)
    b=int(b)
    if a==1:
        change[b]=[s[b-1],c] #[before,after]
    else:
        ans=0
        c=int(c)
        Judge = defaultdict(int)
        lDict = dictList[b-1].copy()
        rDict = dictList[c].copy()
        #print(lDict,rDict)
        for i,m in lDict.items():
            Judge[i]-=m
        for i,m in rDict.items():
            Judge[i]+=m
        for i,m in change.items():
            if b<=i and i<=c:
                Judge[m[0]]-=1
                Judge[m[1]]+=1
        #print(Judge)
        for i,m in Judge.items():
            if m>0:
                ans+=1
        ans_list.append(ans)

for i in range(len(ans_list)):
    print(ans_list[i])

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())

Query = list()
for i in range(Q):
    Query_tmp = list(map(str, input().split()))
    Query.append(Query_tmp)

S_list = list()
for i in range(N):
    S_list.append(S[i])


for i in range(Q):
    if Query[i][0] == "1":
        S_list[int(Query[i][1]) - 1] = Query[i][2]
    if Query[i][0] == "2":
        left = int(Query[i][1])
        right = int(Query[i][2])
        tmp = S_list[left - 1:right]
        tmp.sort()

        
        length = len(tmp)
        ans = 1
        if length != 1:
            for j in range(length - 1):
                if tmp[j] != tmp[j+1]:
                    ans += 1
        
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import  Counter
import  re

n=int(input())
s=input()
q=int(input())
for i in range(q):
    #print(s)
    f=list(map(str,input().split()))
    if int(f[0])==1:
        s=s[:int(f[1])-1]+str(f[2])+s[int(f[1]):]
    elif int(f[0])==2:
        l=int(f[1])
        r=int(f[2])
        tmp=s[l-1:r]
        tm=Counter(tmp)
        ans=len(tm.keys())
        #print(tmp)
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
q=int(input())
que=[]
for i in range(q):
    a=input().split()
    que.append((int(a[0]),int(a[1]),a[2]))
for j in que:
    if j[0]==1:
        s[j[1]-1]=j[2]
    if j[0]==2:
        b=int(j[1])
        c=int(j[2])
        l=[]
        for m in range(b-1,c):
            l.append(s[m])
        ans=len(list(set(l)))
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
# vim:fenc=utf-8 ff=unix


def solv(N, S, Q):
    ans = []
    S = [c for c in S]
    for q in Q:
        if q[0] == 1:
            S[q[1]-1] = q[2]
        else:
            ans.append(len(set(S[q[1]-1:q[2]])))
    return ans


if __name__ == "__main__":

    # N
    # S
    # Q
    # Query_1
    # \vdots
    # Query_Q
    #
    N = int(input())
    S = input()
    QN = int(input())
    Q = []
    for _ in range(QN):
        t, a, b = input().split()
        if t == "1":
            Q.append((1, int(a), b))
        else:
            Q.append((2, int(a), int(b)))

    ans = solv(N, S, Q)

    for a in ans:
        print(a)

Submission status: Time Limit Exceeded

Solution code:
#  --*-coding:utf-8-*--

def bit_inc(bit, x, n):
    m = len(bit)
    
    bit[x-1] += n
    b = 1

    while b < m:
        if x & b:
            x += b
            if x <= m:
                bit[x-1] += n

        b <<= 1



def bit_count(bit, x):
    m = len(bit)

    n = 0
    b = 1

    while b < m:
        if x & b:
            n += bit[x-1]
            x -= b

        b <<= 1

    return n

N = int(input())
bits = [[0]*(N+1) for _ in range(26)]

S = list(input())
for i, s in enumerate(S):
    bit_inc(bits[ord(s) - 97], i+1, 1)

Q = int(input())
for _ in range(Q):
    q1,q2, q3 = input().split()
    q2 = int(q2)

    if q1 == '1':
        s0 = S[q2-1]
        if s0 != q3:
            S[q2-1] = q3
            bit_inc(bits[ord(s0) - 97], q2, -1)
            bit_inc(bits[ord(q3) - 97], q2, 1)
    else:
        cnt = 0
        q3 = int(q3)
        for bit in bits:
            t = bit_count(bit, q3)

            if q2 > 1:
                t -= bit_count(bit, q2-1)

            if t > 0:
                cnt += 1

        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
s = sys.stdin.readlines()
N = int(s[0])
S = s[1]
Q = int(s[2])


seg = [set([]) for _ in range(2*N-1)]
def update(k, x):
    k += N-1
    seg[k] = {x:1}
    while k:
        k = (k-1)//2
        seg[k] = set(seg[2*k+1]) | set(seg[2*k+2])
        
def query(p, q):
    p += N-1
    q += N-2
    res = set([])
    while q-p > 1:
        if p&1 == 0:
            if p >= N-1:
                seg[p] = set(seg[p])
            res = res | seg[p]
        if q&1 == 1:
            if q >= N-1:
                seg[q] = set(seg[q])
            res = res | seg[q]
            q -= 1
        p //= 2
        q = (q-1)//2
    if p == q:
        if q >= N-1:
            seg[q] = set(seg[q])
        res |= seg[q]
    else:
        if p >= N-1:
            seg[p] = set(seg[p])
        if q >= N-1:
            seg[q] = set(seg[q])
        res |= seg[p] | seg[q]
    return len(res)

for i in range(N):
    update(i, S[i])
    
for e in s[3:]:
    a,b,c = map(str, e.split())
    if a == "1":
        update(int(b)-1, c)
    else:
        print(query(int(b)-1, int(c)))

Submission status: Time Limit Exceeded

Solution code:
leng = int(input())
 
strin = input()
 
num = int(input())
 
a = [list(input().split()) for i in range(num)]
 
for kk in range(num):
    if int(a[kk][0]) == 1:
        strin = strin[:int((int(a[kk][1])-1))] + a[kk][2]+ strin[int((a[kk][1])):]
    else:
        print(len(set(strin[int((int(a[kk][1])-1)):int((a[kk][2]))])))

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
q=int(input())
dic=dict()
for i,j in enumerate("qwertyuioplkjhgfdsazxcvbnm"):
    dic[j]=i
No=2
while n>No:
    No*=2
tree=[set()]*(2*No)
def add(k,x):
    k+=No-1
    tree[k]=set([dic[x]])
    while k>0:
        k=(k-1)//2
        tree[k]=tree[2*k+1]|tree[2*k+2]
def query(l,r):
    L=l+No-1
    R=r+No-1
    s=set()
    while L<=R:
        if R&1:
            s|=tree[R]
            R-=2
        else:
            R-=1
        if L&1:
            L-=1
        else:
            s|=tree[L]
        L>>=1;R>>=1
    return len(s)
for i,j in enumerate(s):
    add(i,j)
for i in range(q):
    a,b,c=input().split()
    a,b=int(a),int(b)
    if a==1:
        add(b-1,c)
    if a==2:
        c=int(c)
        print(query(b-1,c-1))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

n = int(input())
s = input()
q = int(input())
qq = [''] * n

ans = []

for i in range(n):
    qq[i] = s[i]

for _ in range(q):
    f,i,c = input().split()
    if f == '1':
        qq[int(i)-1] = str(c)
    if f == '2':
        ans.append(len(Counter(qq[int(i)-1:int(c)])))
        
for i in range(len(ans)):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
# n, m, k = map(int,input().split())
# ab = []
# cd = []

# for i in range(m):
#     ab.append(list(map(int,input().split())))

# for i in range(k):
#     cd.append(list(map(int,input().split())))

# for i in range(1, n+1):

n = int(input())
s = list(input())
Q = int(input())
querys = []
for i in range(Q):
    querys.append(list(map(str,input().split())))

for q in querys:
    if q[0] == "1":
        s[int(q[1])-1] = q[2]
        # print(s)
    elif q[0] == "2":
        substr = s[int(q[1]) - 1 : int(q[2])]
        print(len(list(set(substr))))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

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

alpha2num = lambda c: ord(c) - ord('a')
acount = [[0 for i in range(26)]]

for i, s in enumerate(S):
  ac = deepcopy(acount[i])
  ac[alpha2num(s)] += 1
  acount.append(ac)

Q1 = []
for _ in range(Q):
  qtype, arg1, arg2 = input().split()
  if qtype == '1':
    i = int(arg1)
    c = arg2
    Q1.append((i, c))
  elif qtype == '2':
    l = int(arg1)
    r = int(arg2)
    acl = acount[l-1]
    acr = acount[r]
    ac = [cr-cl for cl, cr in zip(acl, acr)]
    for i, c in Q1:
      Scopy = deepcopy(S)
      if l <= i and i <= r and Scopy[i-1] != c:
        ac[alpha2num(Scopy[i-1])] -= 1
        ac[alpha2num(c)] += 1
        Scopy = Scopy[:i-1] + c + Scopy[i:]
    alpha_count = 0
    for i in range(26):
      if ac[i] > 0:
        alpha_count += 1
    print(alpha_count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def f(S, alp, a, b):
  out=0
  for nums in alp:
    p=np.searchsorted(nums, a, side='left')
    if p<len(nums) and nums[p]<b:
      out+=1
  return out

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

alp=[[] for i in range(26)]
alphabet='abcdefghijklmnopqrstuvwxyz'
def alp2num(s):
  return alphabet.index(s)

for i in range(N):
  alp[alp2num(S[i])].append(i)

def g(x):
  for i in range(26):
    tmp=np.searchsorted(alp[i], x, side='left')
    if tmp<len(alp[i]) and alp[i][tmp]==x:
      return i

S=list(S)
ans=[]
for _ in range(Q):
  x, y, z=input().split()
  x=int(x)
  y=int(y)
  if x==1:
    alp[g(y-1)].remove(y-1)
    t=alp2num(z)
    tmp=np.searchsorted(alp[t], y-1, side='left')
    alp[t]=alp[t][:tmp]+[y-1]+alp[t][tmp:]
    S[y-1]=z
  else:
    z=int(z)
    ans.append(f(S, alp, y-1, z))
    
ans=[str(ans[i]) for i in range(len(ans))]
print('\n'.join(ans))

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

n = int(input())
s = input().rstrip()
bit_array = [0] * 26
orda = ord("a")
for i, ch in enumerate(s):
    bit_array[ord(ch) - orda] |= 1 << i

q = int(input())
for _ in range(q):
    q1, q2, q3 = [item for item in input().split()]
    if q1 == "1":
        iq = int(q2) - 1
        cq = q3
        for index in range(26):
            bit_array[index] &= ~(1 << iq)
        bit_array[ord(cq) - orda] |= 1 << iq
    else:
        lq = int(q2) - 1
        rq = int(q3) - 1
        mask = (1 << (rq + 2) - 1) - (1 << (lq + 1) - 1)
        ret = 0
        for index in range(26):
            if bit_array[index] & mask:
                ret += 1
        print(ret)

Submission status: Time Limit Exceeded

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

def main():
    N = int(input())
    S = list(input().strip())
    Q = int(input())

    for _ in range(Q):
        t, hoge, huga = input().strip().split()
        if t == "1":
            i, c = int(hoge), huga
            S[i-1] = c

        else:
            l, r = int(hoge), int(huga)
            target = S[l-1:r]
            print(len(list(set(target))))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import string
import numpy
import functools
L = len(string.ascii_lowercase)
class BIT:

    def __init__(self, N):
        self.bit = numpy.zeros((N + 1, L))
        self.N = N

    @functools.lru_cache(maxsize=20480)
    def sum_all(self, i):
        s = numpy.zeros(L)
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x, c):
        c = ord(c) - ord('a')
        while i <= self.N:
            self.bit[i][c] += x
            i += i & -i
        self.sum_all.cache_clear()

def solve(N, S, Q, query):
    bits = BIT(N)

    for i, c in enumerate(S):
        bits.add(i + 1, 1, c)

    ans = []
    for q, i, cr in query:
        if q == "1":
            i = int(i)
            if S[i-1] != cr:
                bits.add(i, -1, S[i-1])
                bits.add(i, 1, cr)
                S[i-1] = cr
        else:
            l = int(i)
            r = int(cr)
            diff = bits.sum_all(r) - bits.sum_all(l)
            k = ord(S[l-1]) - ord('a')
            diff[k] += 1
            ans.append(str(numpy.count_nonzero(diff)))
    return "\n".join(ans)

if __name__ == "__main__":
    N = int(input())
    S = list(input())
    Q = int(input())

    query = []
    for _ in range(Q):
        query.append(tuple(input().split(" ")))
    print(solve(N, S, Q, query))

Submission status: Time Limit Exceeded

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

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

def segfunc(x,y):
    return x | y

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]={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] = 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()

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(s)
#print(seg)

for i in range(q):
    t, x, y = map(str, sys.stdin.readline().split())
    if t == '2':
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))
    else:
        i = int(x)-1
        c = {y}
        update(i, c)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


N = [int(i) for i in input().split()][0]
array = np.zeros([N, 26])
string = list(input())
strs = []
a0 = ord("a")
for n, s in enumerate(string):
  i = ord(s) - a0
  array[n, i] = 1
  strs.append(i)
qumsum = np.cumsum(array, axis=0)

Q = [int(i) for i in input().split()][0]
queries =[[i for i in input().split()] for _ in range(Q)]

changed = []
for que in queries:
  type_, pos, st = que
  if type_ == "1":
    p = int(pos) - 1
    s1 = strs[p]
    array[p, s1] = 0
    s2 = ord(st) - a0
    strs[p] = s2
    array[p, s2] = 1
    qumsum[p:, s1] -= 1
    qumsum[p:, s2] += 1
#    changed.append((p, s1, s2))
  else:
    lq = int(pos) - 1
    rq = int(st)
    sums = qumsum[rq-1, :] - qumsum[lq, :] + array[lq, :]
    print(np.sum(sums>0))

Submission status: Time Limit Exceeded

Solution code:
def main():
    n = int(input())
    S = list(input())
    q = int(input())
    for _ in range(q):
        t, i, c = input().split()
        if t == '1':
            S[int(i)-1] = c
        else:
            print(len(set(S[int(i)-1:int(c)])))
        
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter, defaultdict
N = int(input())
S = list(input())
Q = int(input())

l = 2**((N-1).bit_length())
data = [Counter([]) for i in range(2*l)]
for i in range(N):
    data[l+i][S[i]] = 1
for i in range(l-1,0,-1):
    data[i] = data[2*i] + data[2*i+1]

for cnt in range(Q):
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        if S[b-1] == c:
            continue
        oldc = S[b-1]
        S[b-1] = c
        n = l + b - 1
        while n > 0:
            data[n][oldc] -= 1
            data[n][c] += 1
            n = n // 2
    else:
        c = int(c)
        i = b + l -1
        j = c + l
        temp = Counter()
        while j-i > 0:
            if i & 1:
                temp += data[i]
                i += 1
            if j & 1:
                temp += data[j-1]
                j -= 1
            i //= 2
            j //= 2
        print(len(temp))

Submission status: Time Limit Exceeded

Solution code:
import collections

N = int(input())

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

A = [list(map(str,input().split())) for i in range(Q)]

c = collections.Counter
c.update(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'w', 'x', 'y', 'z'])
for i in range(Q):
    #a, b, c = map(str,input().split())
    if A[i][0] == '1':
        S[int(A[i][1])-1] = A[i][2]
    else:
        print(len(c(S[int(A[i][1])-1:int(A[i][2])])))

Submission status: Time Limit Exceeded

Solution code:
import collections
N = int(input())
S = input()
Q = int(input())
querys = [list(map(str, input().split())) for i in range(Q)]
for i in range(Q):
    if querys[i][0] == "1":
        S = S[:int(querys[i][1])-1] + querys[i][2] + S[int(querys[i][1]):]
    else:
        c = collections.Counter(S[int(querys[i][1]) - 1:int(querys[i][2])])
        print(len(c))

Submission status: Time Limit Exceeded

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

ans = []
for _ in range(q):
    i, _1, _2 = input().split()
    i = int(i)
    _1 = int(_1)
    if i == 1: #文字置換
        s = s[:_1-1] + _2 + s[_1:]
    else: # 種類回答
        _2 = int(_2)
        #print("--", s[_1-1:_2-1])
        ans.append(len(set(s[_1-1:_2])))

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = input()
Q = int(input())

ide_ele = set()

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] = 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

#num:n以上の最小の2のべき乗
num =2**(N-1).bit_length()
seg=[ide_ele]*2*num

init(S)

for _ in range(Q):
    t, a, b = input().split()
    if t == '1':
        a = int(a)
        update(a-1, set((b)))
    else:
        a, b = int(a)-1, int(b)
        print(len(query(a,b)))

Submission status: Time Limit Exceeded

Solution code:
N=int(input())
S=list(input())
Q=int(input())

for i in range(Q):
  q=input().split()
  if q[0]=="1":
    S[int(q[1])-1]=q[2]
  else:
    print(len(set(S[int(q[1])-1:int(q[2])])))

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
n = int(input())
s = list(input())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(input())
for i in range(q):
    type, first, last = [i for i in sys.stdin.readline().split()]
    if type == "2":
        first = int(first)
        last = int(last)
        first -= 1
        last -= 1
        cnt = 0
        for a in alpha:
            ls = dict[a]
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        dict[s[first]].remove(first)
        s[first] = last
        bisect.insort_left(dict[last], first)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())

for _ in range(Q):
    q_type, a, b = input().split()
    q_type = int(q_type)
    a = int(a)
    
    if q_type == 1:
        S[a - 1] = b
        continue    
    
    q_str = S[a - 1 : int(b)]
    print(len(set(q_str)))

Submission status: Time Limit Exceeded

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

# int = int(input())
# s = input().split()
# i = list(map(int, input().split()))
# s = [input() for i in range(3)]

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


for i in range(q):
    x, y, z = input().split()
    if x == "1":
        s = s[:int(y)-1] + z + s[int(y):]
    else:
        print(len(list(set(s[int(y)-1:int(z)]))))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import copy
import queue
input = sys.stdin.readline
n = int(input())
s = list(input().rstrip())
q = int(input())
for _ in range(q):
    t,i,c = input().split()

    if t == '1':
        s[int(i)-1] = c
    else:
        ss = set(s[int(i)-1:int(c)])
        print (len(ss))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
  
N = int(input())
S = list(input())
Q = int(input())

for _ in range(Q):
  hoge = input().split()
  if hoge[0] == "1":
    S[int(hoge[1]) - 1] = hoge[2]
  else:
    print(len(set(S[int(hoge[1]) - 1:int(hoge[2])])))