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:
import sys

input = lambda: sys.stdin.readline().rstrip()


class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):

        n = len(init_val)
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.num = 2**(n - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])

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

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


def solve():

    N = int(input())
    S = list(input())
    Q = int(input())
    seg = [[0 for _ in range(N)] for _ in range(26)]

    for i in range(N):
        al = ord(S[i]) - ord('a')
        seg[al][i] = 1

    segtree = []
    segfunc = lambda a, b: a | b

    for i in range(26):
        segtree.append(SegTree(seg[i], segfunc, 0))

    ans = []
    for i in range(Q):
        a, b, c = input().split()
        a = int(a)

        if a == 1:
            b = int(b) - 1
            ps = S[b]
            S[b] = c
            segtree[ord(ps) - ord('a')].update(b, 0)
            segtree[ord(c) - ord('a')].update(b, 1)
        elif a == 2:
            b, c = int(b) - 1, int(c)
            count = 0
            for i in range(26):
                count += segtree[i].query(b, c)
            ans.append(count)

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


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
stmp = list(input())
Q = int(input())
target = ord("a")
s = [ord(stmp[i])-target for i in range(n)]

class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)
	
	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def __init__(self, a):
		self.bitlen = len(a)+1
		self.bit = [0]*(len(a)+1)
		for i, j in enumerate(a):
			self.add(i, j)

b = [BIT([0 for _ in range(n)]) for i in range(26)]
for i in range(n):
	b[s[i]].add(i, 1)

for _ in range(Q):
	q,qtmpa,qtmpb = input().split()
	if q[0] == "1":
		qa = int(qtmpa)
		t = ord(qtmpb)-target
		b[t].add(qa-1, 1)
		b[s[qa-1]].add(qa-1, -1)
		s[qa-1] = t
	else:
		ans = 0
		qta = int(qtmpa)
		qtb = int(qtmpb)
		for i in range(26):
			if b[i].sum(qta-1, qtb) != 0:
				ans += 1
		print(ans)

Submission status: Time Limit Exceeded

Solution code:
n = int(input())
stmp = list(input())
Q = int(input())
target = ord("a")
s = [ord(stmp[i])-target for i in range(n)]
al = [chr(target+i) for i in range(26)]
k = [[0 for _ in range(n)] for _ in range(26)]

for i in range(n):
	k[s[i]][i] += 1


class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)
	
	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def __init__(self, a):
		self.bitlen = len(a)+1
		self.bit = [0]*(len(a)+1)
		for i, j in enumerate(a):
			self.add(i, j)


b = [BIT(k[i]) for i in range(26)]

for _ in range(Q):
	q,qtmpa,qtmpb = input().split()
	if q[0] == "1":
		qa = int(qtmpa)
		t = ord(qtmpb)-target
		b[t].add(qa-1, 1)
		b[s[qa-1]].add(qa-1, -1)
		s[qa-1] = t
	else:
		ans = 0
		qta = int(qtmpa)
		qtb = int(qtmpb)
		for i in range(26):
			if b[i].sum(qta-1, qtb) != 0:
				ans += 1
		print(ans)

Submission status: Time Limit Exceeded

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


class BIT:
    def __init__(self, n):
        """
        初期化
        Input:　
            n: 配列の大きさ
        """
        self.n = n
        self.bit = [0] * (n+10)

    def add(self, x, w):
        """
        更新クエリ(add)
        Input:
            x: インデックス
            w: 加える値
        Note:
            self.bitが更新される
        """        
        while x <= self.n:
            self.bit[x] += w
            x += x&-x
    
    def sum(self, x):
        """
        部分和算出クエリ
        Input:
            x: インデックス
        Return:
            [1,a]の部分和
        """
        cnt = 0
        while x > 0:
            cnt += self.bit[x]
            # 次の最下位桁はどこか
            x -= x&-x
        return cnt   
    
    def psum(self, a, b):
        """
        区間[a,b)(0-indexed)における和
        Input
            a,b: 半開区間
        Return
            [a,b)の和
        """
        return self.sum(b-1) - self.sum(a-1)


def str2num(s):
    return ord(s)-ord("a")

bits = [BIT(n) for i in range(26)]
# 入力
ans = []
for i, s in enumerate(S):
    ind = str2num(s)
    bits[ind].add(i+1, 1)

S = list(S)
for _ in range(q):
    x,a,b = input().split()
    if x == "1":
        i = int(a)
        # 更新処理
        ind_before = str2num(S[i-1])
        ind = str2num(b)
        bits[ind_before].add(i,-1)
        bits[ind].add(i, 1)
        S[i-1] = b
    else:
        l = int(a)
        r = int(b)
        cnt = 0
        for bit in bits:
            if bit.psum(l,r+1) > 0:
                cnt += 1
        ans.append(cnt)
print(*ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

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

    a_ord = ord('a')
    z_ord = ord('z')

    set_list = [[] for _ in range(z_ord+1)]
    for i in range(N):
        s = S[i]
        bisect.insort_left(set_list[ord(s)],i)

    Q = int(input())
    for q in range(Q):
        ipt = input().split()
        if ipt[0] == "1":
            i,c = int(ipt[1]), ipt[2]
            j = ord(S[i-1])

            if j == ord(c): continue
            set_list[j].remove(i-1)
            bisect.insort_left(set_list[ord(c)],i-1)
            S[i-1] = c
            # print(set_list[])

        else:
            l,r = int(ipt[1]), int(ipt[2])
            ans = 0
            # if l == r:
            #     print(1)
            #     continue

            for i in range(a_ord,z_ord+1):
                st = set_list[i]
                if not len(st) > 0: continue

                # print(i,set_list[i])
                l_p = bisect.bisect_left(st,l-1)
                r_p = bisect.bisect_right(st,r-1)

                # print(l-1,r-1,l_p,r_p)
                if l_p < r_p:
                    ans += 1

            # print(ans,"____")
            print(ans)



if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

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

    a_ord = ord('a')
    z_ord = ord('z')

    set_list = [[] for _ in range(z_ord+1)]
    for i in range(N):
        s = S[i]
        bisect.insort_left(set_list[ord(s)],i)

    Q = int(input())
    for q in range(Q):
        ipt = input().split()
        if ipt[0] == "1":
            i,c = int(ipt[1]), ipt[2]

            for j in range(a_ord,z_ord+1):
                if i-1 in set_list[j]:
                    break

            set_list[j].remove(i-1)
            bisect.insort_left(set_list[ord(c)],i-1)
            # print(set_list[])

        else:
            l,r = int(ipt[1]), int(ipt[2])
            ans = 0
            # if l == r:
            #     print(1)
            #     continue

            for i in range(a_ord,z_ord+1):
                st = set_list[i]
                if not len(st) > 0: continue

                # print(i,set_list[i])
                l_p = bisect.bisect_left(st,l-1)
                r_p = bisect.bisect_right(st,r-1)

                # print(l-1,r-1,l_p,r_p)
                if l_p < r_p:
                    ans += 1

            # print(ans,"____")
            print(ans)



if __name__ == "__main__":
  main()

Submission status: Time Limit Exceeded

Solution code:
import copy
n = int(input())
s = input()
q = int(input())
qry = [input().split() for j in range(q)]

moji = []

for i in range(n):
    moji.append(s[i])

dp = [[0 for i in range(26)] for j in range(n+1)]

for i in range(n):
    dp[i+1] = copy.deepcopy(dp[i])
    dp[i+1][ord(s[i])-ord('a')] += 1

li = []

#print(dp)
#exit()
        
for i in range(q):
    if qry[i][0] == '1':
        li.append([int(qry[i][1]),ord(qry[i][2])-ord('a')])
    else:
        ans = [0]*26
        for j in range(26):
            #print(qry[i][2],qry[i][1])
            ans[j] = dp[int(qry[i][2])][j] - dp[int(qry[i][1])-1][j]
        kt = 0
        #print(li)
        for j in range(len(li)):
            if li[j][0] >= int(qry[i][1]) and li[j][0] <= int(qry[i][2]):
                #print(moji[li[j][0]],li[j][0])
                ans[ord(moji[li[j][0]-1])-ord('a')] -= 1
                moji[li[j][0]-1] = chr(li[j][1]+ord('a'))
                ans[li[j][1]] += 1
        for j in range(26):
            #print(ans[j],j)
            if ans[j] > 0:
                kt += 1
        print(kt)
        #for i in range(len(li)):

Submission status: Time Limit Exceeded

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

for _ in range(Q):
    num,i,c = map(str,input().split())
    if num == "1":
        S[int(i)-1]=c

    else:
        print(len(set(S[int(i)-1:int(c)])))

Submission status: Time Limit Exceeded

Solution code:
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        self.data.append(None)
        self.p.append(random())
        self.left.append(None)
        self.right.append(None)
        self.parent.append(None)
        return len(self.data) - 1

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap性の確保
            while self.parent[i] != None and self.p[i] < self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.p[self.left[i]] > self.p[self.right[i]]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            else:
                j = self.left[i]
                self.parent[j] = self.parent[i]

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

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

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap性の確保
            while self.parent[i] != None and self.p[i] < self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.p[self.left[i]] > self.p[self.right[i]]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            else:
                j = self.left[i]
                self.parent[j] = self.parent[i]

            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

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

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
# Treapの実装
from random import random
class Treap():
    def __init__(self):
        # left, right, parent, root, debrisはdataのindexを格納
        self.data = []
        self.p = []
        self.left = []
        self.right = []
        self.parent = []
        self.root = None
        self.debris = []

    # xが見つかればxのindex、見つからなければ探索した最後のnodeのindexを返す
    def find(self, x):
        i = self.root
        while True:
            if self.data[i] == x:
                return i
            elif self.data[i] < x:
                if self.right[i] == None:
                    return i
                else:
                    i = self.right[i]
            elif self.left[i] == None:
                return i
            else:
                i = self.left[i]
    
    # 追加する場所のindexを返す
    def next_place(self):
        if self.debris == []:
            self.data.append(None)
            self.p.append(random())
            self.left.append(None)
            self.right.append(None)
            self.parent.append(None)
            return len(self.data) - 1
        else:
            return self.debris.pop(-1)

    def add(self, x):
        if self.root == None:
            self.data = [x]
            self.p = [random()]
            self.left = [None]
            self.right = [None]
            self.parent = [None]
            self.root = 0
            self.debris = []
        else:
            p = self.find(x) # p = (xの親となるindex)
            if self.data[p] != x:
                i = self.next_place()
                self.data[i] = x
                self.parent[i] = p
                if self.data[p] < x:
                    self.right[p] = i
                else:
                    self.left[p] = i
            
            # heap
            while self.parent[i] != None and self.p[i] > self.p[self.parent[i]]:
                if self.left[self.parent[i]] == i:
                    self.rotateRight(self.parent[i])
                else:
                    self.rotateLeft(self.parent[i])
    
    def remove(self, x):
        if self.root == None:
            return None
        i = self.find(x)
        if self.data[i] == x:
            while self.left[i] != None and self.right[i] != None:
                if self.left[i] > self.right[i]:
                    self.rotateLeft(i)
                else:
                    self.rotateRight(i)

            # parent[j]をparent[i]に変更
            if self.left[i] == None and self.right[i] == None:
                j = None
            elif self.left[i] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
            elif self.right[i] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
            else:
                print('error')
            '''
            elif self.left[self.right[i]] == None:
                j = self.right[i]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.parent[self.left[i]] = j
            elif self.right[self.left[i]] == None:
                j = self.left[i]
                self.parent[j] = self.parent[i]
                self.right[j] = self.right[i]
                self.parent[self.right[i]] = j
            
            else:
                j = self.right[i]
                while self.left[j] != None:
                    j = self.left[j]
                self.left[self.parent[j]] = self.right[j]
                if self.right[j] != None:
                    self.parent[self.right[j]] = self.parent[j]
                self.parent[j] = self.parent[i]
                self.left[j] = self.left[i]
                self.right[j] = self.right[i]
                self.parent[self.left[i]] = j
                self.parent[self.right[i]] = j
            '''
            # parent[i]の子をjに変更
            if self.root == i:
                self.root = j
            elif self.left[self.parent[i]] == i:
                self.left[self.parent[i]] = j
            else:
                self.right[self.parent[i]] = j
            
            # iの初期化
            self.data[i] = None
            self.left[i] = None
            self.right[i] = None
            self.parent[i] = None
            self.debris.append(i)

    def rotateRight(self, u):
        w = self.left[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.left[u] = self.right[w]
        if self.right[w] != None:
            self.parent[self.right[w]] = u
        self.parent[u] = w
        self.right[w] = u
    
    def rotateLeft(self, u):
        w = self.right[u]
        if self.root == u:
            self.root = w
        elif self.left[self.parent[u]] == u:
            self.left[self.parent[u]] = w
        else:
            self.right[self.parent[u]] = w
        self.parent[w] = self.parent[u]
        self.right[u] = self.left[w]
        if self.left[w] != None:
            self.parent[self.left[w]] = u
        self.parent[u] = w
        self.left[w] = u

    def exist(self, x):
        return self.data[self.find(x)] == x

    def empty(self):
        return self.root == None

    def debug(self):
        if self.root == None:
            return 'empty'
        tree = [[self.root]]
        flag = True
        while flag:
            l = []
            for i in tree[-1]:
                if i == '  ':
                    l.append('  ')
                    l.append('  ')
                    continue
                elif self.left[i] == None:
                    l.append('  ')
                else:
                    l.append(self.left[i])
                if self.right[i] == None:
                    l.append('  ')
                else:
                    l.append(self.right[i])
            flag = False
            for i in l:
                if i == '  ':
                    continue
                else:
                    tree.append(l)
                    flag = True
                    break
        for i in range(len(tree)):
            l = []
            for j in tree[i]:
                if j == '  ':
                    l.append(j)
                else:
                    k = str(self.data[j])
                    if len(k) == 1:
                        k = ' ' + k
                    l.append(k)
            n = len(tree) - i
            m = (2**n-1) * '  '
            l = (m.join(l))
            print((2**(n-1)-1) * '  ' + l)
        print()

    def search(self, l, r):
        i = self.root
        while i != None:
            if l <= self.data[i] <= r:
                return True
            elif self.data[i] < l:
                i = self.right[i]
            else:
                i = self.left[i]
        return False

import sys
def input():
    return sys.stdin.readline().strip()

def order(a):
    return ord(a) - 97

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

# alphabet毎に整理
alp = [Treap() for _ in range(26)]
from random import shuffle
l = [i for i in range(n)]
shuffle(l)
for i in l:
    alp[order(s[i])].add(i)

# クエリ処理
ans = []
for _ in range(q):
    a, b, c = input().split()
    b = int(b) - 1

    # type1
    if a == '1':
        alp[order(s[b])].remove(b)
        alp[order(c)].add(b)
        s[b] = c

    # type2
    else:
        c = int(c) - 1
        num = 0
        for i in alp:
            if i.search(b, c):
                num += 1
        ans.append(num)

for i in ans:
    print(i)