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() 

def resolve():

    class BinaryIndexedTree:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)
    
        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s
    
        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

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

    pos_bit_list = [BinaryIndexedTree(len(S)) for _ in range(26)]

    for i, c in enumerate(S):
        pos_bit_list[ord(c)-ord('a')].add(i+1, 1)

    for q in Query:
        if q[0] == '1':
            i = int(q[1])
            c = q[2]
            pos_bit_list[ord(S[i-1])-ord('a')].add(i, -1)
            pos_bit_list[ord(c)-ord('a')].add(i, 1)
            S[i-1] = c
        else:
            print(len([p for p in pos_bit_list if p.sum(int(q[2])) - p.sum(int(q[1])-1) > 0]))

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

def resolve():

    class BinaryIndexedTree():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        def add(self, item, pos):
            index = pos
            while index < self.n+1:
                self.bit[index] += item
                index += index & (-index)

        def sum(self, pos):
            ret = 0
            index = pos
            while index > 0:
                ret += self.bit[index]
                index -= index & -index
            return ret

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

    pos_bit_list = [BinaryIndexedTree(len(S)) for _ in range(26)]

    for i, c in enumerate(S):
        pos_bit_list[ord(c)-ord('a')].add(1, i+1)

    for q in Query:
        if q[0] == '1':
            pos_bit_list[ord(S[int(q[1])-1])-ord('a')].add(-1, int(q[1]))
            pos_bit_list[ord(q[2])-ord('a')].add(1, int(q[1]))
            S[int(q[1])-1] = q[2]
        else:
            ans = 0
            for p in pos_bit_list:
                if p.sum(int(q[2])) - p.sum(int(q[1])-1) > 0:
                    ans += 1
            print(ans)


if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()


def func(a, b):
    return a+b


class SegmentTree:
    """
    各ノードが半開区間に対応した完全二分木。
    子は親を半分にした区間を持つ。
    構築O(n), 区間に対する操作O(logn), 値の更新O(logn)
    区間に対する操作は最小値, 最大値, 区間に対する和など柔軟に変更して用いよう！
    """

    def __init__(self, x, init_val):  # 構築, init_valは配列の初期値
        self.init_val = init_val
        self.length = 2 ** ((len(x) - 1).bit_length())
        self.data = [init_val] * 2 * self.length
        for i in range(len(x)):
            self.data[i + self.length - 1] = x[i]
        for i in range(self.length - 2, -1, -1):
            self.data[i] = func(self.data[2 * i + 1], self.data[2 * i + 2])

    def teach_current_val(self, index):
        return self.data[index + self.length - 1]

    def replace(self, index, val):  # indexの値をvalに更新
        index += self.length - 1
        self.data[index] = val
        while index:
            index = (index - 1) // 2
            self.data[index] = func(self.data[2 * index + 1], self.data[2 * index + 2])

    def query(self, left, right):  # 半開区間の最小値等を求める, 葉からさかのぼっていくイメージ。
        if right <= left:
            return self.init_val
        left += self.length - 1  # self.dataの位置に合わせる。
        right += self.length - 2  # self.dataの位置に合わせる。半開区間
        ans_ = self.init_val
        while right > left + 1:
            if left & 1 == 0:  # if left_index%2 == 0:
                ans_ = func(ans_, self.data[left])
            if right & 1 == 1:  # if right_index%2 == 1:
                ans_ = func(ans_, self.data[right])
                right -= 1
            left //= 2
            right = (right - 1) // 2
        if left == right:
            ans_ = func(ans_, self.data[left])
        else:
            ans_ = func(func(ans_, self.data[left]), self.data[right])
        return ans_


N = int(input())
S = input()
Q = int(input())
alphabets = string.ascii_lowercase
segs = []
check = dict()
for i in alphabets:
    segs.append([1 if S[l] == i else 0 for l in range(N)])
for i in range(26):
    segs[i] = SegmentTree(segs[i], 0)
for _ in range(Q):
    Query = list(map(str, input().split()))
    if Query[0] == "1":
        i, c = int(Query[1]), Query[2]
        if check.get(str(i - 1)):
            segs[ord(check[str(i - 1)]) - 97].replace(i - 1, 0)
            segs[ord(c) - 97].replace(i - 1, 1)
            check[str(i - 1)] = c
        else:
            segs[ord(S[i - 1]) - 97].replace(i - 1, 0)
            segs[ord(c) - 97].replace(i - 1, 1)
            check[str(i - 1)] = c
    else:
        l, r = map(int, (Query[1], Query[2]))
        ans = 0
        for i in segs:
            if i.query(l-1, r) > 0:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

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

def resolve():

    class BinaryIndexedTree():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        def add(self, item, pos):
            index = pos
            while index < self.n+1:
                self.bit[index] += item
                index += index & (-index)

        def sum(self, pos):
            ret = 0
            index = pos
            while index > 0:
                ret += self.bit[index]
                index -= index & -index
            return ret

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

    pos_bit_list = [BinaryIndexedTree(len(S)) for _ in range(26)]

    for i, c in enumerate(S):
        pos_bit_list[ord(c)-ord('a')].add(1, i+1)

    for q in Query:
        if q[0] == '1':
            pos_bit_list[ord(S[int(q[1])-1])-ord('a')].add(-1, int(q[1]))
            pos_bit_list[ord(q[2])-ord('a')].add(1, int(q[1]))
            S[int(q[1])-1] = q[2]
        else:
            print(len([p for p in pos_bit_list if p.sum(int(q[2])) - p.sum(int(q[1])-1) > 0]))

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=list(input())
q=int(input())
for i in range(q):
    dd=input()
    if dd[0]=="1":
        _,x,i =map(str,dd.split())
        x=int(x)
        s[x-1]=i
    else:
        _,i,j=map(int,dd.split())
        print(len(set(s[i-1:j])))

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

def func(l, r):
    res = [inf for _ in range(26)]
    aa = ord('a')
    for i in range(l, r + 1):
        for j in range(26):
            if chr(j + aa) == s[i]:
                res[j] = min(res[j], j)
    return res

n = INT()
s = list(STR())
q = INT()
for _ in range(q):
    que = S_LIST()
    if que[0] == '1':
        i = int(que[1])
        c = que[2]
        s[i - 1] = c
    else:
        l = int(que[1])
        r = int(que[2])
        u = func(l - 1, r - 1)
        ans = 0
        for i in range(26):
            if u[i] < inf:
                ans += 1
        print(ans)

Submission status: Time Limit Exceeded

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

def ctoi(c):
    return ord(c) - ord('a')

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w): # 0-indexed
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def _sum(self,x): # 1-indexed
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
    def sum(self,l,r): # [l,r)
        return self._sum(r) - self._sum(l)
    def __str__(self): # for debug
        arr = [self.sum(i,i+1) for i in range(self.N)]
        return str(arr)
bits = [BinaryIndexedTree(N) for i in range(26)]

s = []
for i,c in enumerate(S):
    bits[ctoi(c)].add(i,1)
    s.append(c)

ans = []
for a,b,c in qs:
    if a=='1':
        i = int(b)-1
        bits[ctoi(s[i])].add(i,-1)
        bits[ctoi(c)].add(i,1)
        s[i] = c
    else:
        l,r = int(b)-1,int(c)
        a = 0
        for i in range(26):
            if bits[i].sum(l,r):
                a += 1
        ans.append(a)
print(*ans,sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

n = INT()
s = list(STR())
q = INT()
for _ in range(q):
    que = S_LIST()
    if que[0] == '1':
        i = int(que[1])
        c = que[2]
        s[i - 1] = c
    else:
        l = int(que[1])
        r = int(que[2])
        ss = s[l - 1:r]
        print(len(set(ss)))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

n = int(input())
s = input()
S = []
for i in range(n):
    S.append(s[i])
q = int(input())
for i in range(q):
    qw = input()
    if qw[0] == "1":
        qw = qw[2:]
        i, ch = map(str, qw.split())
        S[int(i) - 1] = ch
    else:
        qw = qw[2:]
        l, r = map(int, qw.split())
        new = defaultdict(str)
        c = 0
        for i in range(l - 1, r):
            if new[S[i]] != True:
                new[S[i]] = True
                c += 1
                
        print(c)

Submission status: Time Limit Exceeded

Solution code:
class Segment_tree():
    def __init__(self, n, s):
        self.n = n
        self.s = s
        self.N = 1
        while self.N < self.n:
            self.N *= 2
        self.size = self.N * 2
        self.size -= 1
        self.N -= 1
        self.segment = [set()]*self.size
        for i in range(self.n):
            self.segment[i+self.N] = {self.s[i]}
        for i in range(self.N-1, -1, -1):
            a = self.segment[2*i+1] 
            b = self.segment[2*i+2]
            self.segment[i] = a|b
        
    def undate(self, i, x):
        i += (self.N-1)
        self.segment[i] = {x}
        while i > 0:
            i = (i-1)//2
            self.segment[i] = self.segment[2*i+1] | self.segment[2*i+2]
        
    def find(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set()
        elif a <= l and r <= b:
            return self.segment[k]
        else:
            find_l = self.find(a, b, 2*k+1, l, (l+r)//2)
            find_r = self.find(a, b, 2*k+2, (l+r)//2, r)
            return find_l | find_r
    
    def count(self, a, b):
        return len(self.find(a, b, 0, 0, self.size-self.N))

n = int(input())
s = input()
segment_tree = Segment_tree(n, s)
q = int(input())
for i in range(q):
    key = [str(x) for x in input().split()]
    if key[0] == "1":
        segment_tree.undate(int(key[1]), key[2])
    else:
        print(segment_tree.count(int(key[1])-1, int(key[2])))

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
N = int(input())
S = list(input())
Q = int(input())
 
D = {chr(ord('a') + i): [] for i in range(26)}
 
for i, s in enumerate(S):
    D[s].append(i)
 
for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1]), query[2]
        i -= 1
        s = S[i]
        if s == x:
            continue
 
        D[s].remove(i)
        next_i = bisect_left(D[x], i)
        D[x].insert(next_i, i)
        S[i] = x
 
    if query[0] == '2':
        l, r = int(query[1]), int(query[2])
        l, r = l - 1, r - 1
        ans = 0
        for i in range(26):
            s = chr(ord('a') + i)
 
            li = bisect_left(D[s], l)
            ri = bisect_right(D[s], r)
 
            if ri - li > 0:
                ans += 1
 
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
#segtree
#https://juppy.hatenablog.com/entry/2019/05/02/%E8%9F%BB%E6%9C%AC_python_%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder
#####segfunc######
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のべき乗
n=int(input())
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
s=input()
init([{ord(i)-97}for i in s])
q=int(input())
for _ in range(q):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,{ord(c)-97})
  else:
    _,l,r=quer
    print(len(query(int(l)-1,int(r))))

Submission status: Time Limit Exceeded

Solution code:
#####segfunc######
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のべき乗
n=int(input())
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
s=input()
init([{i}for i in s])
q=int(input())
for _ in range(q):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,{c})
  else:
    _,l,r=quer
    print(len(query(int(l)-1,int(r))))

Submission status: Time Limit Exceeded

Solution code:
#####segfunc######
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のべき乗
n=int(input())
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
s=input()
init([{i}for i in s])
q=int(input())
for _ in range(q):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,{c})
  else:
    _,l,r=quer
    print(len(query(int(l)-1,int(r))))

Submission status: Time Limit Exceeded

Solution code:
class SegTree:
  def segfunc(self,x,y):
    return x|y
  def __init__(self,a,x):
    n=len(a);self.num=1<<(n-1).bit_length();self.seg=[x if type(x)==type(1) else x.copy() for _ in range(2*self.num-1)]
    for i in range(n):self.seg[i+self.num-1]=a[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):
    i=k+self.num-1;self.seg[i]=x
    while i!=0:i=(i-1)>>1;self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2])
  def query(self,p,q):
    l,r=p+self.num-1,q+self.num-1
    if l==r:return self.seg[l]
    ans=self.seg[l];l+=1
    for _ in range(10000):
      if r-l<2:break
      if ~l&1:ans=self.segfunc(self.seg[l],ans)
      if r&1:ans=self.segfunc(self.seg[r],ans);r-=1
      l>>=1;r=(r-1)>>1
    ans=self.segfunc(self.seg[l],ans)
    if l!=r:ans=self.segfunc(self.seg[r],ans)
    return ans
n=int(input())
s=input()
seg=SegTree([{i}for i in s],set())
q=int(input())
for _ in range(q):
  query=input().split()
  if query[0]=="1":
    _,i,c=query
    seg.update(int(i)-1,{c})
  else:
    _,l,r=query
    print(len(seg.query(int(l)-1,int(r)-1)))

Submission status: Time Limit Exceeded

Solution code:
import bisect

def resolve():
    N = int(input())
    S = list(input().strip())
    Q = int(input())
    table = [[] for _ in range(26)]
    for i in range(len(S)):
        ch = S[i]
        bisect.insort(table[ord(ch)-ord('a')], i+1)

    for i in range(Q):
        query = input().strip().split()
        if query[0] == '1':
            pos = int(query[1])
            old_ch = ord(S[pos-1]) - ord('a')
            new_ch = ord(query[2]) - ord('a')
            if old_ch != new_ch:
                bisect.insort(table[new_ch], pos)
                table[old_ch].remove(pos)
                S[pos-1] = query[2]
        else:
            left = int(query[1])
            right = int(query[2])
            count = 0
            for j in range(26):
                k = bisect.bisect_left(table[j], left)
                if k != len(table[j]) and table[j][k] <= right:
                    count +=1
            print(count)

resolve()

Submission status: Time Limit Exceeded

Solution code:
import sys
import string
import random

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()


class Node:
    def __init__(self, x):
        self.data = x
        self.priority = random.random()
        self.left = None
        self.right = None


def rotate_right(node):
    l_node = node.left
    node.left = l_node.right
    l_node.right = node
    return l_node


def rotate_left(node):
    r_node = node.right
    node.right = r_node.left
    r_node.left = node
    return r_node


def search_min(node):
    while node.left is not None:
        node = node.left
    return node.data


def traverse_(node):
    if node is not None:
        for x in traverse_(node.left):
            yield x
        yield node.data
        for x in traverse_(node.right):
            yield x


class Treap:
    """
    動的ランダム二分探索木の中の一つ。構築:O(nlogn), 他の操作:期待値O(logn)
    """

    def __init__(self):
        self.root = None

    def search(self, x):
        def search_(node, x):
            while node is not None:
                if x == node.data:
                    return True
                elif x < node.data:
                    node = node.left
                else:
                    node = node.right
            return False

        return search_(self.root, x)

    def insert(self, x):
        def insert_(node, x):
            if node is None:
                return Node(x)
            elif x == node.data:
                return node
            elif x < node.data:
                node.left = insert_(node.left, x)
                if node.priority > node.left.priority:
                    node = rotate_right(node)
            else:
                node.right = insert_(node.right, x)
                if node.priority > node.right.priority:
                    node = rotate_left(node)
            return node

        self.root = insert_(self.root, x)

    def delete(self, x):
        def delete_(node, x):
            if node is not None:
                if x == node.data:
                    if node.left is None:
                        return node.right
                    elif node.right is None:
                        return node.left
                    else:
                        node.data = search_min(node.right)
                        node.right = delete_(node.right, node.data)
                elif x < node.data:
                    node.left = delete_(node.left, x)
                else:
                    node.right = delete_(node.right, x)
            return node

        self.root = delete_(self.root, x)

    def traverse(self):

        for x in traverse_(self.root):
            yield x

    def lower_bound(self, x):
        def lower_bound_(node, x):
            while node is not None:
                if node.right and node.left:
                    if node.right.data < x:
                        return lower_bound_(node.right, x)
                    elif node.data < x:
                        return min(node.right.data, lower_bound_(node.right, x))
                    else:
                        return min(node.data, lower_bound_(node.left, x))
                elif node.right:
                    if node.right.data < x:
                        return lower_bound_(node.right, x)
                    elif node.data < x:
                        return min(node.right.data, lower_bound_(node.right, x))
                    else:
                        return node.data  # 怪しい！！
                elif node.left:
                    if node.data < x:
                        return INF
                    elif node.left.data < x:
                        return min(node.data, lower_bound_(node.left, x))
                    else:
                        return lower_bound_(node.left, x)
                elif x <= node.data:
                    return node.data
                else:
                    return INF

        if self.root:
            return lower_bound_(self.root, x)
        else:
            return INF

    def upper_bound(self, x):
        def upper_bound_(node, x):
            while node is not None:
                if node.right and node.left:
                    if node.left.data > x:
                        return upper_bound_(node.left, x)
                    elif node.data > x:
                        return max(node.left.data, upper_bound_(node.left, x))
                    else:
                        return max(node.data, upper_bound_(node.right, x))
                elif node.left:
                    if node.left.data > x:
                        return upper_bound_(node.left, x)
                    elif node.data > x:
                        return max(node.left.data, upper_bound_(node.left, x))
                    else:
                        return node.data
                elif node.right:
                    if node.data > x:
                        return -INF
                    elif node.right.data > x:
                        return max(node.data, upper_bound_(node.right, x))
                    else:
                        return upper_bound_(node.right, x)
                elif x >= node.data:
                    return node.data
                else:
                    return -INF

        if self.root:
            return upper_bound_(self.root, x)
        else:
            return -INF

    def __str__(self):
        if self.root is None:
            return "Treap()"
        buff = "Treap("
        for x in traverse_(self.root):
            buff += "%s, " % x
        buff = buff.rstrip(", ")
        buff += ")"
        return buff


N = int(input())
S = input()
Q = int(input())
strings = [Treap() for _ in range(26)]
alphabets = string.ascii_lowercase
check = {}
check2 = {}
for i in range(26):
    check[alphabets[i]] = i
for i in range(N):
    strings[check[S[i]]].insert(i)
for _ in range(Q):
    Query, a, b = map(str, input().split())
    if Query == "1":
        a = int(a)
        if a-1 not in check2:
            strings[check[S[a - 1]]].delete(a - 1)
            strings[check[b]].insert(a - 1)
            check2[a-1] = b
        else:
            strings[check[check2[a-1]]].delete(a - 1)
            strings[check[b]].insert(a - 1)
            check2[a-1] = b
    else:
        a, b = map(int, (a, b))
        ans = 0
        for i in range(26):
            if strings[i].lower_bound(a - 1) <= b - 1:
                ans += 1
        print(ans)