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:
n = int(input())
s = input().strip()
q = int(input())
query = [tuple(input().split()) for _ in range(q)]
s = list(s)

for t, l, r in query:
    if t == "1":
        l = int(l)
        s[l - 1] = r
    elif t == "2":
        l, r = int(l), int(r)
        print(len(set(s[(l - 1):r])))

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

S = list(input())

Q = int(input())

for i in range(Q):
    q_type, l_i, c_r = input().split()
    if q_type == '1':
        S[int(l_i)-1] = c_r
    else:
        print(len(set(S[int(l_i)-1:int(c_r)])))

Submission status: Time Limit Exceeded

Solution code:
def input_int_list():
    return [int(thing) for thing in input().split(" ")]
N=int(input())
S=[""]+list(input())
Q=int(input())
Query_list=[input().split(" ") for i in range(Q)]
for Type,i,c in Query_list:
    if int(Type)==1:
        S[int(i)]=c
    else:
        the_string=S[int(i):int(c)+1]
        num=len(list(set(the_string)))
        print(num)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
import math
import itertools
import fractions
import heapq
import collections
import bisect
import sys
import copy

sys.setrecursionlimit(10**9)
mod = 10**7+9
inf = 10**20

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()

n = I()
s = list(S())
q = I()

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

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
        self.tree[index] = x
        while index:
            index = (index-1)//2
            self.tree[index] = self.func(self.tree[2*index+1],self.tree[2*index+2])

    def query(self,left,right):
        if right <= left:
            return self.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 = self.func(tmp_l,self.tree[left])
            if right & 1 == 1:
                tmp_r = self.func(self.tree[right],tmp_r)
                right -= 1
            left = left//2
            right = (right-1)//2
        if left == right:
            tmp_l = self.func(tmp_l,self.tree[left])
        else:
            tmp_l = self.func(self.func(tmp_l,self.tree[left]),self.tree[right])
        return self.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 = input()
q = int(input())

for _ in range(q):
  ql = input().split()
  if ql[0] == '1':
    i = int(ql[1])
    if i-1 == n:
      s = s[:i-1] + ql[2]
    else:
      s = s[:i-1] + ql[2] + s[i:]
  else:
    l = int(ql[1])
    r = int(ql[2])
    tmp = s[l-1:r]
    print(len(set(list(tmp))))

Submission status: Time Limit Exceeded

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

for _ in range(q):
    a1, a2, a3 = input().split()

    # a1 = 1の時
    if a1 == "1":
        s[int(a2) - 1] = a3

    # a1 = 2の時
    else:
        print(len(set(s[int(a2) - 1:int(a3)])))

Submission status: Time Limit Exceeded

Solution code:
import collections

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

q=int(input())

for j in range(q):
    k,i,c=input().split()
    if int(k)==1:
        s[int(i)-1]=c
    else:
        print(len(collections.Counter(s[int(i)-1:int(c):])))

Submission status: Time Limit Exceeded

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

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

for i in range(Q):
    q, a, b = map(str, input().split())
    if int(q) == 1:
        a = int(a) - 1
        S[a] = b
    if int(q) == 2:
        a = int(a) - 1
        b = int(b) - 1
        _set = set(S[a: b+1])
        print(len(_set))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

for i in range(Q):
    q, a, b = map(str, input().split())
    if int(q) == 1:
        a = int(a) - 1
        S[a] = b
    if int(q) == 2:
        a = int(a) - 1
        b = int(b) - 1
        _set = set(S[a: b+1])
        print(len(_set))

Submission status: Time Limit Exceeded

Solution code:
import sys

class RMQ(): #range minimum query
    def __init__(self, N, V): #create segment tree with initial value V
        d, k = 1, 0
        while d < N:
            d <<= 1
            k += 1
        self.tree = [V for _ in range(2 * d - 1)]
        self.size = d 
    
    def update(self, i, a): #update cell i by value a
        now = self.size - 1 + i 
        self.tree[now] = {a}
        while now > 0:
            now = (now - 1) // 2
            self.tree[now] = self.tree[2 * now + 1] | self.tree[2 * now + 2]
        #print(self.tree)

    def search(self, lower, higher, lbound, hbound, pos): #search minimum value of [lower, higher) init: lbound = 0, hbound = self.size, pos = 0
        if higher <= lbound or hbound <= lower: return set()
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return left | right


def solve():
    input = sys.stdin.readline
    N = int(input())
    S = list(input().strip("\n"))
    SegTree = RMQ(N, set())
    for i, s in enumerate(S): SegTree.update(i, s)
    Q = int(input())
    for _ in range(Q):
        t, l, r = input().strip("\n").split()
        if t == "1": SegTree.update(int(l) - 1, r)
        elif t == "2": print(len(SegTree.search(int(l) - 1, int(r), 0, SegTree.size, 0)))
    return 0

if __name__ =="__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import sys

class RMQ(): #range minimum query
    def __init__(self, N, V): #create segment tree with initial value V
        d, k = 1, 0
        while d < N:
            d <<= 1
            k += 1
        self.tree = [V for _ in range(2 * d - 1)]
        self.size = d 
    
    def update(self, i, a): #update cell i by value a
        now = self.size - 1 + i 
        self.tree[now] = {a}
        while now > 0:
            now = (now - 1) // 2
            self.tree[now] = self.tree[2 * now + 1] | self.tree[2 * now + 2]
        #print(self.tree)

    def search(self, lower, higher, lbound, hbound, pos): #search minimum value of [lower, higher) init: lbound = 0, hbound = self.size, pos = 0
        if higher <= lbound or hbound <= lower: return set()
        if lower <= lbound and hbound <= higher: return self.tree[pos]
        else:
            left = self.search(lower, higher, lbound, (lbound + hbound) // 2, 2 * pos + 1)
            right = self.search(lower, higher, (lbound + hbound) // 2, hbound, 2 * pos + 2)
            return left | right


def solve():
    input = sys.stdin.readline
    N = int(input())
    S = list(input().strip("\n"))
    SegTree = RMQ(N, set())
    for i, s in enumerate(S): SegTree.update(i, s)
    Q = int(input())
    Ans = []
    for _ in range(Q):
        t, l, r = input().strip("\n").split()
        if t == "1": SegTree.update(int(l) - 1, r)
        elif t == "2": 
            Ans.append(len(SegTree.search(int(l) - 1, int(r), 0, SegTree.size, 0)))
    for a in Ans: print(a)
    

    return 0

if __name__ =="__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
n=int(input())
s=input()
q=int(input())
for _ in range(q):
    q1,q2,q3=input().split()
    if q1=='1':
        s=s[:int(q2)-1]+q3+s[int(q2):]
    else:
        print(len(set(s[int(q2)-1:int(q3)])))

Submission status: Time Limit Exceeded

Solution code:
def update(BIT,index,letter,value):
    while index < len(BIT):
        BIT[index][letter] += value
        index += index&-index

def sumQuery(BIT,index):
    letters = [0]*26
    while index > 0:
        for i in range(26):
            letters[i] += BIT[index][i]

        index -= index&-index

    return letters

def rangeQuery(BIT,l,r,ans):
    right = sumQuery(BIT,r)
    left = sumQuery(BIT,l-1)
    count = 0
    for i in range(26):
        right[i] -= left[i]
        if right[i] > 0:
            count += 1

    ans.append(count)

def main():
    n = int(input())
    s = list(input())
    q = int(input())
    BIT = [[0 for i in range(26)] for j in range(n+1)]
    ans = []

    for i in range(n):
        update(BIT,i+1,ord(s[i])-ord('a'),1)

    for i in range(q):
        query,index,c = map(str,input().split())
        query = int(query)
        if query == 1:
            index = int(index)
            update(BIT,index,ord(s[index-1])-ord('a'),-1)
            s[index-1] = c
            update(BIT,index,ord(s[index-1])-ord('a'),1)
        else:
            l,r = int(index),int(c)
            rangeQuery(BIT,l,r,ans)

    for i in ans:
        print(i)


main()

Submission status: Time Limit Exceeded

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

main()

Submission status: Time Limit Exceeded

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

Submission status: Accepted

Solution code:
from typing import List, Any


def read_int() -> int:
    return int(input().strip())


def read_ints() -> List[int]:
    return list(map(int, input().strip().split(' ')))


class SegmentTree:
    
    def __init__(self, array):
        self.n = len(array)
        self.array = [0 for _ in array]+array
        for i in range(self.n-1, 0, -1):
            self.array[i] = self.array[i<<1]|self.array[i<<1|1]

    def set(self, i, v):
        p = self.n+i
        self.array[p] = v
        while p > 1:
            p >>= 1
            self.array[p] = self.array[p<<1]|self.array[p<<1|1]

    def count(self, l, r):
        l += self.n
        r += self.n
        answer = 0
        while l < r:
            if l&1:
                answer |= self.array[l]
                l += 1
            if r&1:
                r -= 1
                answer |= self.array[r]
            l >>= 1
            r >>= 1
        return answer


def bit_count(a):
    answer = 0
    while a:
        answer += a&1
        a >>= 1
    return answer


def solve():
    ALPHABETS = 'abcdefghijklmnopqrstuvwxyz'
    N = read_int()
    S = input()
    Q = read_int()
    segment_tree = SegmentTree([1<<(ALPHABETS.index(c)) for c in S])
    for _ in range(Q):
        cmd = input().strip().split(' ')
        if cmd[0] == '1':
            n = 1<<(ALPHABETS.index(cmd[2]))
            segment_tree.set(int(cmd[1])-1, n)
        else:
            l, r = int(cmd[1])-1, int(cmd[2])
            print(bit_count(segment_tree.count(l, r)))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
class segtree:

    def __init__(self, n, identity):
        # identityは初期値
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2 ** (len(nb) - 1)
        else:
            self.num_end_leaves = 2 ** (len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity

    def update(self, x, val):
        actual_x = x + self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0:
            actual_x = actual_x // 2
            self.array[actual_x] = self.array[actual_x * 2] | self.array[actual_x * 2 + 1]

    def get(self, q_left, q_right, arr_ind=1, leaf_left=0, depth=0):
        width_of_floor = self.num_end_leaves // (2 ** depth)
        leaf_right = leaf_left + width_of_floor - 1

        if leaf_left > q_right or leaf_right < q_left:
            return self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left, q_right, 2 * arr_ind, leaf_left, depth + 1)
            val_r = self.get(q_left, q_right, 2 * arr_ind + 1, leaf_left + width_of_floor // 2, depth + 1)
            return val_l | val_r

N = int(input())
S = list(input())
Q = int(input())
T = {}
j = 1
for i in range(97, 97+26):
    T[chr(i)] = j
    j *= 2

s_tree = segtree(N+1, 0)

for i in range(N):
    s_tree.update(i+1, T[S[i]])

for i in range(Q):
    A = list(input().split())
    a, b, c = A
    if a == "2":
        K = bin(s_tree.get(int(b), int(c)))[2:]
        d = 0
        for i in K:
            if i == "1":
                d += 1
        print(d)
    else:
        s_tree.update(int(b), T[c])

Submission status: Accepted

Solution code:

class BIT:
    """Binary Indexed Tree (Fenwick Tree)
    Range Sum QueryにO(log N)時間で答える
    1-indexed
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        """a[1]~a[i]の区間和を取得"""
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        """a[i]にxを足す"""
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_
 
def main():
    N = int(input())
    S = list(input())
    Q = int(input())
    alphabets = list("abcdefghijklmnopqrstuvwxyz")
    c2n = {c: i for i, c in enumerate(alphabets)}
    
    Trees = [BIT(N+2) for _ in range(26)]

    for i in range(N):
        Trees[c2n[S[i]]].add(i+1, 1)
    
    for _ in range(Q):
        tmp = list(input().split())
        if tmp[0] == "1":
            _, i, c = tmp
            i = int(i)
            Trees[c2n[S[i-1]]].add(i, -1)
            Trees[c2n[c]].add(i, 1)
            S[i-1] = c
        else:
            ans = 0
            _, l, r = tmp
            l = int(l)
            r = int(r)
            for char in range(26):
                if Trees[char].sum(r) - Trees[char].sum(l-1) > 0:
                    ans += 1
            print(ans)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class BalancingTree:
    """平衡二分木のクラス
    Pivotを使った実装.
    0以上2^n - 2以下の整数を扱う
    """
    def __init__(self, n):
        """
        2の指数nで初期化
        """
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def debug(self):
        """デバッグ用の関数"""
        def debug_info(nd_):
            return (nd_.value - 1, nd_.pivot - 1, nd_.left.value - 1 if nd_.left else -1, nd_.right.value - 1 if nd_.right else -1)

        def debug_node(nd):
            re = []
            if nd.left:
                re += debug_node(nd.left)
            if nd.value: re.append(debug_info(nd))
            if nd.right:
                re += debug_node(nd.right)
            return re
        print("Debug - root =", self.root.value - 1, debug_node(self.root)[:50])

    def append(self, v):
        """
        v を追加（その時点で v はない前提）
        """
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                # v がすでに存在する場合に何か処理が必要ならここに書く
                return 0
            else:
                mi, ma = min(v, nd.value), max(v, nd.value)
                if mi < nd.pivot:
                    nd.value = ma
                    if nd.left:
                        nd = nd.left
                        v = mi
                    else:
                        p = nd.pivot
                        nd.left = self.node(mi, p - (p&-p)//2)
                        break
                else:
                    nd.value = mi
                    if nd.right:
                        nd = nd.right
                        v = ma
                    else:
                        p = nd.pivot
                        nd.right = self.node(ma, p + (p&-p)//2)
                        break

    def leftmost(self, nd):
        if nd.left: return self.leftmost(nd.left)
        return nd

    def rightmost(self, nd):
        if nd.right: return self.rightmost(nd.right)
        return nd

    def find_l(self, v):
        """
        vより真に小さいやつの中での最大値（なければ-1）
        """
        v += 1
        nd = self.root
        prev = 0
        if nd.value < v: prev = nd.value
        while True:
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                prev = nd.value
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    def find_r(self, v):
        """
        vより真に大きいやつの中での最小値（なければRoot）
        """
        v += 1
        nd = self.root
        prev = 0
        if nd.value > v: prev = nd.value
        while True:
            if v < nd.value:
                prev = nd.value
                if nd.left:
                    nd = nd.left
                else:
                    return prev - 1
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return prev - 1

    @property
    def max(self):
        """最大値の属性"""
        return self.find_l((1<<self.N)-1)

    @property
    def min(self):
        """最小値の属性"""
        return self.find_r(-1)

    def delete(self, v, nd = None, prev = None):
        """
        値がvのノードがあれば削除（なければ何もしない）
        """
        v += 1
        if not nd: nd = self.root
        if not prev: prev = nd
        while v != nd.value:
            prev = nd
            if v <= nd.value:
                if nd.left:
                    nd = nd.left
                else:
                    return
            else:
                if nd.right:
                    nd = nd.right
                else:
                    return
        if (not nd.left) and (not nd.right):
            if nd.value < prev.value:
                prev.left = None
            else:
                prev.right = None
        elif not nd.left:
            if nd.value < prev.value:
                prev.left = nd.right
            else:
                prev.right = nd.right
        elif not nd.right:
            if nd.value < prev.value:
                prev.left = nd.left
            else:
                prev.right = nd.left
        else:
            nd.value = self.leftmost(nd.right).value
            self.delete(nd.value - 1, nd.right, nd)

    def __contains__(self, v: int) -> bool:
        return self.find_r(v - 1) == v

    class node:
        """ノードをあらわすクラス
        v: 値
        p: ピボット値
        で初期化
        """
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

Trees = [BalancingTree(50) for _ in range(26)]
N = int(input())
S = input()
Q = int(input())
alphabets = list("abcdefghijklmnopqrstuvwxyz")
c2n = {c: i for i, c in enumerate(alphabets)}
for i in range(N):
    Trees[c2n[S[i]]].append(i+1)
S = list(S)
for _ in range(Q):
    tmp = list(input().split())
    if tmp[0] == "1":
        _, i, c = tmp
        i = int(i)
        bef = S[i-1]
        if bef == c:
            continue
        Trees[c2n[bef]].delete(i)
        Trees[c2n[c]].append(i)
        S[i-1] = c
    else:
        _, l, r = tmp
        l = int(l)
        r = int(r)
        ans = 0
        for char in range(26):
            res = Trees[char].find_r(l-1)
            if l <= res <= r:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:


# ===============================================================================================
# importing some useful libraries.
from __future__ import division, print_function
from fractions import Fraction
import sys
import os
from io import BytesIO, IOBase
from itertools import *
import bisect
from heapq import *
from math import *
from copy import *
from collections import deque
from collections import Counter as counter  # Counter(list)  return a dict with {key: count}
from itertools import combinations as comb  # if a = [1,2,3] then print(list(comb(a,2))) -----> [(1, 2), (1, 3), (2, 3)]
from itertools import permutations as permutate
from bisect import bisect_left as bl
# If the element is already present in the list,

# the left most position where element has to be inserted is returned.
from bisect import bisect_right as br
from bisect import bisect

# If the element is already present in the list,
# the right most position where element has to be inserted is returned

# ==============================================================================================
# fast I/O region

BUFSIZE = 8192
from sys import stderr


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


def print(*args, **kwargs):
    """Prints the values to a stream, or to sys.stdout by default."""
    sep, file = kwargs.pop("sep", " "), kwargs.pop("file", sys.stdout)
    at_start = True
    for x in args:
        if not at_start:
            file.write(sep)
        file.write(str(x))
        at_start = False
    file.write(kwargs.pop("end", "\n"))
    if kwargs.pop("flush", False):
        file.flush()


if sys.version_info[0] < 3:
    sys.stdin, sys.stdout = FastIO(sys.stdin), FastIO(sys.stdout)
else:
    sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)

# inp = lambda: sys.stdin.readline().rstrip("\r\n")

# ===============================================================================================
### START ITERATE RECURSION ###
from types import GeneratorType


def iterative(f, stack=[]):
    def wrapped_func(*args, **kwargs):
        if stack: return f(*args, **kwargs)
        to = f(*args, **kwargs)
        while True:
            if type(to) is GeneratorType:
                stack.append(to)
                to = next(to)
                continue
            stack.pop()
            if not stack: break
            to = stack[-1].send(to)
        return to

    return wrapped_func


#### END ITERATE RECURSION ####

# ===============================================================================================
# some shortcuts

mod = 1000000007


def inp(): return sys.stdin.readline().rstrip("\r\n")  # for fast input


def out(var): sys.stdout.write(str(var))  # for fast output, always take string


def lis(): return list(map(int, inp().split()))


def stringlis(): return list(map(str, inp().split()))


def sep(): return map(int, inp().split())


def strsep(): return map(str, inp().split())


def zerolist(n): return [0] * n


def nextline(): out("\n")  # as stdout.write always print sring.


def testcase(t):
    for p in range(t):
        solve()


def printlist(a):
    for p in range(0, len(a)):
        out(str(a[p]) + ' ')

def pow(x, y, p):
    res = 1  # Initialize result
    x = x % p  # Update x if it is more , than or equal to p
    if (x == 0):
        return 0
    while (y > 0):
        if ((y & 1) == 1):  # If y is odd, multiply, x with result
            res = (res * x) % p

        y = y >> 1  # y = y/2
        x = (x * x) % p
    return res

from functools import reduce

def factors(n):
    return set(reduce(list.__add__,
                ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0)))

def gcd(a, b):
    if a == b: return a
    while b > 0: a, b = b, a % b
    return a
# =========================================================================================

from operator import add
def solve():
    def sep():
        return map(int, input().strip().split(" "))

    def lis():
        return list(map(int, input().strip().split(" ")))
    class SegmentTree:
        def __init__(self, data, default=0, func=add):
            """initialize the segment tree with data"""
            self._default = default
            self._func = func
            self._len = len(data)
            self._size = _size = 1 << (self._len - 1).bit_length()

            self.data = [default] * (_size) + data + [default] * (_size - self._len)
            for i in range(_size - 1, -1, -1):
                self.data[i] = func(self.data[2 * i], self.data[2 * i + 1])

        def __delitem__(self, idx):
            self[idx] = self._default

        def __getitem__(self, idx):
            return self.data[idx + self._size]

        def __setitem__(self, idx, value):
            idx += self._size
            self.data[idx] = value
            idx >>= 1
            while idx:
                self.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])
                idx >>= 1


        def __len__(self):
            return self._len



        def query(self, start, stop):
            """func  of data[start, stop)"""
            start += self._size
            stop +=  self._size

            res_left = res_right = self._default
            while start < stop:
                if start & 1:
                    res_left = self._func(res_left, self.data[start])
                    start += 1
                if stop & 1:
                    stop -= 1
                    res_right = self._func(self.data[stop], res_right)
                start >>= 1
                stop >>= 1

            return self._func(res_left, res_right)


    def fun(i1,i2):
        s1=i1
        s2=i2
        k=s1.union(s2)
        return(k)

    n=int(input())
    ar=inp()
    temp=[]
    for i in range(n):
        t=set().copy()
        t.add(ar[i])
        temp.append(t)
    defa=(set().copy())
    seg=SegmentTree(temp,default=defa,func=fun)
    m=int(inp())
    for _ in range(m):
        # print(seg.data)
        a,b,c=(i for i in inp().strip().split(" "))
        if a=="2":
            b=int(b)
            c=int(c)
            print(len(seg.query(b-1,c)))
        else:
            b=int(b)
            t=set().copy()
            t.add(c)
            seg[b-1]=t.copy()













solve()
#testcase(int(inp()))