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:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

tmp = 'abcdefghijklmnopqrstuvwxyz'
n = I()
s = list(input())
cnt = [0]*n
alpha = defaultdict(list)
for i in range(n):
    alpha[s[i]].append(i)

q = I()
f = defaultdict(list)
for _ in range(q):
    num, i, c = input().split()
    if int(num) == 1:
        if s[int(i)-1] == c:
            continue
        r = br(f[s[int(i)-1]],int(i)-1)
        f[s[int(i)-1]] = f[s[int(i)-1]][:r] + [int(i)-1] + f[s[int(i)-1]][r:]
        r = br(alpha[c],int(i)-1)
        alpha[c] = alpha[c][:r] + [int(i)-1] + alpha[c][r:]
        s[int(i)-1] = c
    else:
        cnt = 0
        for j in range(26):
            l = bl(alpha[tmp[j]],int(i)-1)
            r = br(alpha[tmp[j]],int(c)-1)
            L = bl(f[tmp[j]],int(i)-1)
            R = br(f[tmp[j]],int(c)-1)
            if r - l - (R - L) > 0:
                cnt += 1
            #print(tmp[j],alpha[tmp[j]],f[tmp[j]],int(i),int(c),l,r,L,R)
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
q=int(input())
c=[chr(i) for i in range(97, 97+26)]
l=[input().split() for i in range(q)]
L=[]
for i in range(q):
  if l[i][0]=='2':
    L.append([int(l[i][1]),int(l[i][2])])

a=[[0 for i in range(n)] for i in range(26)]
b=[]
for i in range(n):
  a[c.index(s[i])][i]=1
for i in range(26):
  x=[0]
  for j in range(n):
    x.append(x[-1]+a[i][j])
  b.append(x)

L2=[[0 for i in range(26)] for i in range(len(L))]
for i in range(len(L)):
  for j in range(26):
    L2[i][j]=b[j][L[i][1]]-b[j][L[i][0]-1]

j2=0
for i in range(q):
  if l[i][0]=='1':
    for j in range(len(L)):
      if L[j][0]<=int(l[i][1])<=L[j][1]:
        L2[j][c.index(l[i][2])]+=1
        L2[j][c.index(s[int(l[i][1])-1])]-=1
    s[int(l[i][1])-1]=l[i][2]
  else:
    ans=0
    for i in range(26):
      if L2[j2][i]!=0:
        ans+=1
    print(ans)
    j2+=1

Submission status: Time Limit Exceeded

Solution code:
import bisect
N=int(input())
S=list(input())
Q=int(input())
abc="abcdefghijklmnopqrstuvwxyz"

cnt=[[] for _ in range(26)]

for i in range(N):
  cnt[abc.index(S[i])].append(i)

for _ in range(Q):
  t,i,c=input().split()
  if t=="1":
    i=int(i)
    cnt[abc.index(S[i-1])].remove(i-1)
    S[i-1]=c
    cnt[abc.index(c)].insert(bisect.bisect(cnt[abc.index(c)],i-1),i-1)
  else:
    l,r=int(i),int(c)
    ans=0
    for i in range(26):
      if bisect.bisect_left(cnt[i],l-1)!=bisect.bisect_right(cnt[i],r-1):
        ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

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

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

for q in query:
    if q[0] == '1':
        i = int(q[1]) - 1
        c = q[2]
        S = S[:i] + c + S[i+1:]
    else:
        l = int(q[1]) - 1
        r = int(q[2]) - 1
        print(len(set(S[l:r+1])))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, or_

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)



def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
	def __init__(self, orig, func, unit):
		_len = len(orig)
		self.func = func
		self.size = 1 << (_len - 1).bit_length()
		self.tree = [unit] * self.size + orig + [unit] * (self.size - _len)
		self.unit = unit

		for i in range(self.size - 1, 0, -1):
			self.tree[i] = func(self.tree[i * 2], self.tree[i * 2 + 1])

	def update(self, i, v):
		i += self.size
		self.tree[i] = v
		while i:
			i //= 2
			self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def find(self, l, r):
		l += self.size
		r += self.size
		ret = self.unit
		while l < r:
			if l & 1:
				ret = self.func(ret, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				ret = self.func(ret, self.tree[r])
			l //= 2
			r //= 2
		return ret

@mt
def slv(N, S, Q):
    S = [c for c in S]
    st = SegmentTree([0] * N, or_, 0)
    for i, c in enumerate(S):
        st.update(i, 1 << (ord(c) - ord('a')))

    for q in Q:
        if q[0] == '1':
            i = int(q[1]) - 1
            c = q[2]
            st.update(i, 1 << (ord(c) - ord('a')))
        if q[0] == '2':
            i = int(q[1]) - 1
            j = int(q[2]) - 1
            ans = 0
            v = st.find(i, j+1)
            for k in range(26):
                if (1 << k) & v:
                    ans += 1
            print(ans)
    # return ans


def main():
    N = read_int()
    S = read_str()
    Q = [read_str_n() for _ in range(read_int())]
    (slv(N, S, Q))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

tmp = 'abcdefghijklmnopqrstuvwxyz'
n = I()
s = list(input())
cnt = [0]*n
alpha = defaultdict(list)
for i in range(n):
    alpha[s[i]].append(i)

q = I()
f = defaultdict(list)
for _ in range(q):
    num, i, c = input().split()
    if int(num) == 1:
        f[s[int(i)-1]].append(int(i)-1)
        f[s[int(i)-1]].sort()
        alpha[c].append(int(i)-1)
        alpha[c].sort()
        s[int(i)-1] = c
    else:
        cnt = 0
        for j in range(26):
            l = bl(alpha[tmp[j]],int(i)-1)
            r = br(alpha[tmp[j]],int(c)-1)
            L = bl(f[tmp[j]],int(i)-1)
            R = br(f[tmp[j]],int(c)-1)
            if r - l - (R-L) > 0:
                cnt += 1
            #print(tmp[j],alpha[tmp[j]],f[tmp[j]],int(i),int(c),l,r,L,R)
        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right, insort_left


def main():
    n = int(input())
    s = list(input())
    q = int(input())
    qs = [input().split() for _ in range(q)]

    abc = [[] for _ in range(26)]
    for i, e in enumerate(s):
        j = ord(e) - ord("a")
        abc[j].append(i)

    for t, e1, e2 in qs:
        if t == "1":
            i = int(e1) - 1
            c = e2

            let = s[i]

            idx = ord(let) - ord("a")
            popi = bisect_left(abc[idx], i)
            abc[idx].pop(popi)

            idx = ord(c) - ord("a")
            insort_left(abc[idx], i)

            s[i] = c

        else:
            l = int(e1) - 1
            r = int(e2) - 1

            cnt = 0
            for i in range(26):
                li = bisect_left(abc[i], l)
                ri = bisect_right(abc[i], r)
                if li != ri:
                    cnt += 1

            print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
N = int(input())
S =list(input())
Q = int(input())
T = []
while True:
    try:
        T.append(list(input().split()))
    except:
        break;

cnt = 0

def funk(x ,y):
    global S
    for s in range(x,y):
        S[int(T[s][1])-1] = T[s][2]    
    return S

for i in range(Q):
    if int(T[i][0]) == 2:
        funk(cnt,i)
        cnt = i+1        
        print(len(set(S[int(T[i][1])-1:int(T[i][2])])))

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(500000)
def input():
    return sys.stdin.readline()[:-1]

class SegmentTree:
    def __init__(self, L, op, ide):
        self.op = op
        self.ide = ide
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.ide]*(2*self.n-1)

        #for i in range(self.sz):
        #    self.node[i+self.n-1] = L[i]

        #for i in range(self.n-2,-1,-1):
        #    self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def substitute(self, a, x):
        k = a+self.n-1
        self.node[k] = x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break

    def get_one(self, a):
        k = a+self.n-1
        return self.node[k]
    
    def get(self, l, r):
        res = self.ide
        n = self.n
        if self.sz <= r or 0 > l:
            print('ERROR: the indice are wrong.')
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        #left
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        #right
        n1 = n//2        
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res
    


def main():
    #da=BIT([1,2,3])
    #print(da.bit)
    #print(da.sum(0))
    N = int(input())
    op = lambda a,b: a or b
    B = [SegmentTree([False]*N,op, False) for i in range(26)]

    S = list(input())

    for i in range(N):
        B[ord(S[i]) - ord("a")].add(i, True)

    Q = int(input())

    for i in range(Q):
        a,b,c = input().split()
        if a=="1":
            #print(B[0].bit)
            index = int(b)-1
            c = c
            if not S[index]==c:
                old = ord(S[index]) - ord("a")
                num = ord(c) - ord("a")
                B[num].add(index, True)
                B[old].substitute(index, False)
                S[index] = c
        else:
            #print(B[0].bit)
            #print(B[0].sum(1))
            l = int(b)-1
            r = int(c)-1
            ans = 0
            for j in range(26):
                if B[j].get(l,r):
                    ans+=1


            print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right, insort_left

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

abc = [[] for _ in range(26)]
for i, e in enumerate(s):
    j = ord(e) - ord("a")
    abc[j].append(i)

for t, e1, e2 in qs:
    if t == "1":
        i = int(e1) - 1
        c = e2

        let = s[i]

        idx = ord(let) - ord("a")
        popi = bisect_left(abc[idx], i)
        abc[idx].pop(popi)

        idx = ord(c) - ord("a")
        insort_left(abc[idx], i)

        s[i] = c

    else:
        l = int(e1) - 1
        r = int(e2) - 1

        cnt = 0
        for i in range(26):
            li = bisect_left(abc[i], l)
            ri = bisect_right(abc[i], r)
            if li != ri:
                cnt += 1

        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right, insort_left

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

abc = [[-1, n] for _ in range(26)]
for i, e in enumerate(s):
    j = ord(e) - ord("a")
    abc[j].append(i)

for i in range(26):
    abc[i].sort()

for t, e1, e2 in qs:
    if t == "1":
        i = int(e1) - 1
        c = e2

        let = s[i]

        idx = ord(let) - ord("a")
        popi = bisect_left(abc[idx], i)
        abc[idx].pop(popi)

        idx = ord(c) - ord("a")
        insort_left(abc[idx], i)

        s[i] = c

    else:
        l = int(e1) - 1
        r = int(e2) - 1

        cnt = 0
        for i in range(26):
            li = bisect_left(abc[i], l)
            ri = bisect_right(abc[i], r)
            if li != ri:
                cnt += 1

        print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import math

class SegmentTree:
	def update(self, i, x):
		i += self.num_leaves-1
		self.nodes[i] = x
		while i > 0:
			i = (i-1) // 2
			self.nodes[i] = self.monoid(self.nodes[i*2+1],self.nodes[i*2+2])
			
	def query(self,a,b,k=0,l=0,r=None):
		if r is None:
			r = self.num_leaves
		if r <= a or b <= l:
			return None
		if a <= l and r <= b:
			return self.nodes[k]
		else:
			vl = self.query(a,b,k*2+1,l,(l+r)//2)
			vr = self.query(a,b,k*2+2,(l+r)//2,r)
			return self.monoid(vl,vr)
		
	def __init__(self, monoid, values):
		self.monoid = lambda x, y : monoid(x, y) if x is not None and y is not None else (x if x is not None else y)
		self.num_leaves = 2**math.ceil(math.log2(len(values)))
		self.nodes = [None for i in range(self.num_leaves*2-1)]
		for i in range(len(values)):
			self.update(i,values[i])

n = int(input())
s = input()
q = int(input())
Q = [input().split() for i in range(q)]

SGT = [SegmentTree(lambda x,y: x or y, [False for i in range(n)]) for j in range(26)]

for i in range(n):
    SGT[ord(s[i]) - ord('a')].update(i, True)

for i in range(q):
    a,b,c = Q[i]
    b = int(b)
    if a == "1":
        for j in range(26):
            SGT[j].update(b-1, ord(c)-ord('a') == j)
    else:
        c = int(c)
        cnt = 0
        for j in range(26):
            cnt += SGT[j].query(b-1,c)
        print(cnt)

Submission status: Time Limit Exceeded

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


class BIT:

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

    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

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:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, or_

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)



def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N, operator, identity_element):
        """ operator and identity_element has to be a monoid.
        """
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__op = operator
        self.__ie = identity_element

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        t = self.__table
        o = self.__op

        t[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            li = 2*pi + 1
            ri = 2*pi + 2
            v = o(t[li], t[ri])
            if t[pi] != v:
                t[pi] = v
            else:
                break
            i = pi

    def query(self, a, b):
        stack = [(0, 0, self.__N)]
        t = self.__table
        o = self.__op

        ans = self.__ie
        c = 0
        while stack:
            c += 1
            k, l, r = stack.pop()
            cnd = t[k]
            if a <= l and r <= b:
                ans = o(ans, cnd)
            else:
                if (l + r) // 2 > a and b > l:
                    stack.append((2 * k + 1, l, (l + r) // 2))

                if r > a and b > (l + r) // 2:
                    stack.append((2 * k + 2, (l + r) // 2, r))
        return ans

    def print(self):
        print(self.__table)



@mt
def slv(N, S, Q):
    S = [c for c in S]
    st = SegmentTree(N, or_, 0)
    for i, c in enumerate(S):
        st.update(i, 1 << (ord(c) - ord('a')))

    for q in Q:
        if q[0] == '1':
            i = int(q[1]) - 1
            c = q[2]
            st.update(i, 1 << (ord(c) - ord('a')))
        if q[0] == '2':
            i = int(q[1]) - 1
            j = int(q[2]) - 1
            ans = 0
            v = st.query(i, j+1)
            for k in range(26):
                if (1 << k) & v:
                    ans += 1
            print(ans)
    # return ans


def main():
    N = read_int()
    S = read_str()
    Q = [read_str_n() for _ in range(read_int())]
    (slv(N, S, Q))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N = int(input())
S = list(input())
Q = int(input())

for i in range(Q):
  query = input().split()
  if query[0]=='1':
    i = int(query[1])
    c = query[2]
    S[i-1] = c
  else:
    l = int(query[1])
    r = int(query[2])
    print(len(set(S[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
import collections
n=int(input())
s=input()
q=int(input())
for i in range(q):
    a,b,c=map(str,input().split())
    a=int(a)
    b=int(b)
    if a==1:
        s=s[:b-1]+c+s[b:]
    else:
        print(len(collections.Counter(s[b-1:int(c)])))

Submission status: Time Limit Exceeded

Solution code:
def solve():
    import sys
    input = sys.stdin.readline

    numChar = 26
    #numChar = 5
    ordA = ord('a')

    N = int(input())
    Ss = input()
    nos = [ord(S)-ordA for S in Ss]
    Q = int(input())

    def makeBIT(numEle):
        numPow2 = 2 ** (numEle-1).bit_length()
        datas = [[0]*(numPow2+1) for _ in range(numChar)]
        return datas, numPow2
    def addValue(no, iA, A):
        data = datas[no]
        iB = iA + 1
        while iB <= numPow2:
            data[iB] += A
            iB += iB & -iB
    def getSum(no, iA):
        data = datas[no]
        iB = iA + 1
        ans = 0
        while iB > 0:
            ans += data[iB]
            iB -= iB & -iB
        return ans
    def getRangeSum(no, iFr, iTo):
        return getSum(no, iTo) - getSum(no, iFr-1)


    datas, numPow2 = makeBIT(N)

    for i in range(N):
        no = nos[i]
        addValue(no, i, 1)

    anss = []
    for _ in range(Q):
        tp, v1, v2 = input().split()
        if tp == '1':
            pos = int(v1)-1
            no1 = nos[pos]
            no2 = ord(v2)-ordA
            addValue(no1, pos, -1)
            addValue(no2, pos, 1)
            nos[pos] = no2
        else:
            L, R = int(v1)-1, int(v2)-1
            ans = 0
            for no in range(numChar):
                if getRangeSum(no, L, R):
                    ans += 1
            anss.append(ans)

    print('\n'.join(map(str, anss)))


solve()

Submission status: Time Limit Exceeded

Solution code:
# from heapq import heapify, heappop, heappush
# from bisect import bisect_left, bisect_right
# from collections import defaultdict
# import sys
# input = lambda: sys.stdin.readline().rstrip()
# sys.setrecursionlimit(10**9)
# MOD = 10**9 + 7
inpl = lambda: list(map(int,input().split()))
class SegmentTree:
    def __init__(self, value=[], N=0, comp=lambda x,y: x<=y, reverse=False):
        M = max(len(value),N)
        N = 2**(len(bin(M))-3)
        if N < M: N *= 2
        self.N = N
        self.node = [0] * (2*N-1)
        for i in range(N):
            self.node[N-1+i] = i
        self.value = [None] * N
        for i, v in enumerate(value):
            self.value[i] = v
        self.comp = lambda x, y: True if y is None else False if x is None else comp(x,y)^reverse
        for i in range(N-2,-1,-1):
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            self.node[i] = left_i if self.comp(left_v, right_v) else right_i

    def update(self, n, v):
        self.value[n] = v
        i = (self.N-1) + n
        while i > 0:
            i = (i-1)//2
            left_i, right_i = self.node[2*i+1], self.node[2*i+2]
            left_v, right_v = self.value[left_i], self.value[right_i]
            new_i = left_i if self.comp(left_v, right_v) else right_i
            if new_i == self.node[i] and new_i != n:
                break
            else:
                self.node[i] = new_i

    def at(self, n):
        if n is None:
            return None
        else:
            return self.value[n]

    def query(self, l=0, r=-1):
        return self.at(self.query_index(l,r))

    def query_index(self, l=0, r=-1):
        if r < 0: r = self.N
        L = l + self.N; R = r + self.N
        s = None
        while L < R:
            if R & 1:
                R -= 1
                if self.comp(self.at(self.node[R-1]), self.at(s)):
                    s = self.node[R-1]
            if L & 1:
                if self.comp(self.at(self.node[L-1]), self.at(s)):
                    s = self.node[L-1]
                L += 1
            L >>= 1; R >>= 1
        return s
N = int(input())
S = list(input())
Q = int(input())
sg = [ SegmentTree(N=N) for _ in range(26)]
for i in range(N):
    sg[ord(S[i])-ord('a')].update(i,1)
for q in range(Q):
    query = input().split()
    k = int(query[0])
    if k == 1:
        i = int(query[1]) - 1
        c = query[2]
        if S[i] != c:
            sg[ord(c)-ord('a')].update(i,1)
            sg[ord(S[i])-ord('a')].update(i,None)
            S[i] = c
    else:
        l = int(query[1])-1
        r = int(query[2])
        ans = 0
        for c in range(26):
            if sg[c].query(l,r):
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import bisect
n = int(sys.stdin.readline().strip())
s = list(sys.stdin.readline().strip())
alpha = "abcdefghijklmnopqrstuvwxyz"
dict = {i:[] for i in alpha}
for i, _s in enumerate(s):
    dict[_s].append(i)
q = int(sys.stdin.readline().strip())
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 ls in dict.values():
            if bisect.bisect_left(ls, first) != bisect.bisect_right(ls, last):
                cnt += 1
        print(cnt)
    else:
        first = int(first)
        first -= 1
        _s = s[first]
        del dict[_s][(bisect.bisect_left(dict[_s], 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())
query = []
a = []
for _ in range(q):
    method, i, c = input().split()
    if method == "1":
        a.append([i, c])
    else:
        a.append([i, c])
        query.append(a)
        a = []
string = []
now = s
for qq in query:
    if len(qq) == 1:
        string.append("".join(now))
        continue
    for i, c in qq[:-1]:
        i = int(i)
        now[i-1] = c
    string.append("".join(now))
for qq, ss in zip(query, string):
    l, r = map(int, qq[-1])
    print(len(set(ss[l-1:r])))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

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

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

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
class SegmentTree():
    def __init__(self,arr,func=min,ie=2**63):
        self.n = 2**(len(arr)-1).bit_length()
        self.ie = ie
        self.func = func
        self.tree = [ie for _ in range(2*self.n)]
        for i in range(len(arr)):
            self.tree[self.n+i-1] = arr[i]
        for i in range(self.n-1)[::-1]:
            self.tree[i] = func(self.tree[2*i+1],self.tree[2*i+2])

    def set(self,index,x):
        index += self.n-1
        tree = self.tree
        func = self.func
        tree[index] = x
        while index:
            index = (index-1)//2
            tree[index] = func(tree[2*index+1],tree[2*index+2])

    def query(self,left,right):
        ie = self.ie
        tree = self.tree
        func = self.func
        if right <= left:
            return ie
        left += self.n-1
        right += self.n-2
        tmp_l = self.ie
        tmp_r = self.ie
        while right-left>1:
            if left & 1 == 0:
                tmp_l = func(tmp_l,tree[left])
            if right & 1 == 1:
                tmp_r = func(tree[right],tmp_r)
                right -= 1
            left = left//2
            right = (right-1)//2
        if left == right:
            tmp_l = func(tmp_l,tree[left])
        else:
            tmp_l = func(func(tmp_l,tree[left]),tree[right])
        return func(tmp_l,tmp_r)

import sys
input = sys.stdin.readline

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

A = []
for i in range(N):
    A.append(set(S[i]))

def func(x,y):
    return x|y
ie = set([])

st = SegmentTree(A,func,ie)

ans = []

for _ in range(Q):
    q,x,y = input().split()
    q = int(q)
    if q == 1:
        st.set(int(x)-1,set([y]))
    else:
        ans.append(len(st.query(int(x)-1,int(y))))

print('\n'.join(map(str,ans)))

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':
        S[int(b)-1] = c
    elif a == '2':
        print(len(set(S[int(b)-1:int(c)])))

Submission status: Time Limit Exceeded

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

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

for i in range(Q):
  a,b,c = list(input().split())

  if a == "1":
      S = S[:int(b)-1] + c + S[int(b):]

  else:
      partial = S[int(b)-1:int(c)]
      u = ''.join(set(partial))
      print(len(u))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
for _ in range(Q):
  t, i, c = map(str, input().split())
  t = int(t)
  i = int(i)
  if t==1 and S[i-1]!=c:
    S.insert(i-1, c)
    S.pop(i)
  elif t==2:
    c = int(c)
    print(len(set(S[i-1:c])))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
S = list(input())
Q = int(input())
for _ in range(Q):
  t, i, c = map(str, input().split())
  t = int(t)
  i = int(i)
  if t==1 and S[i-1]!=c:
    S.insert(i-1, c)
    S.pop(i)
  elif t==2:
    c = int(c)
    print(len(set(S[i-1:c])))