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: Wrong Answer

Solution code:

import bisect

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

# 現時点でどこに何があるか
cS = [""] * N
# ある文字の位置
char_idxs = [[]for _  in range(26)]

# i番目は文字s、を保存
for i,s in enumerate(S):
    cS[i] = s
    char_idxs[ord(s) - 97].append(i)

query = [tuple(map(str, input().split())) for _ in range(Q)]




for q,a,b in query:
    
    # q == 1の時、a番目の文字をbに置き換え
    if q == "1":
        # 現時点の文字と置き換え後が同じなら何もしない
        if cS[int(a) - 1] == b:
            continue
        else:
            #print("---", char_idxs[ord(cS[]) - 97], int(a)-1, bisect.bisect_right(char_idxs[ord(b) - 97], int(a)-1))
            # a番目の文字を書き換える
            char_idxs[ord(cS[int(a)-1]) - 97].remove(int(a)-1)
            """
            idx = bisect.bisect_right(char_idxs[ord(cS[int(a)-1]) - 97], int(a)-1)
            # idxの左の値がa番目であれば、それを消す
            if char_idxs[ord(cS[int(a)-1]) - 97][idx-1] == int(a)-1:
                # delの方が早いか？
                char_idxs[ord(cS[int(a)-1]) - 97][idx-1:idx] = []
            """
            
            # bの文字がa番目にあるよ、を保存
            bisect.insort_right(char_idxs[ord(b) - 97], int(a) - 1)

            # 置き換え
            cS[int(a) - 1] = b
    # q == 2の時、範囲の文字種の個数を調べる
    else:
        cnt = 0
        for i in range(26):
            # そもそもその文字が文字列全体になければ考えない
            if len(char_idxs[i]) == 0: continue
            # a <= X <= b を満たす値があれば、l〜rに文字chr(i+97)が含まれると言える
            l = bisect.bisect_left(char_idxs[i], int(a)-1)
            r = bisect.bisect_right(char_idxs[i], int(b)-1)

            if l < len(char_idxs[i]) and r > 0 and int(a)-1 <= char_idxs[i][l] and  int(b)-1 >= char_idxs[i][r-1]:
                cnt += 1

        print(cnt)

Submission status: Wrong Answer

Solution code:

import bisect

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

# 現時点でどこに何があるか
cS = [""] * N
# ある文字の位置
char_idxs = [[]for _  in range(26)]

for i,s in enumerate(S):
    cS[i] = s
    char_idxs[ord(s) - 97].append(i)

query = [tuple(map(str, input().split())) for _ in range(Q)]




for q,a,b in query:

    # q == 1の時、a番目の文字をbに置き換え
    if q == "1":
        # 現時点の文字と置き換え後が同じなら何もしない
        if cS[int(a) - 1] == b:
            continue
        else:
            #print("---", char_idxs[ord(cS[]) - 97], int(a)-1, bisect.bisect_right(char_idxs[ord(b) - 97], int(a)-1))
            idx = bisect.bisect_right(char_idxs[ord(cS[int(a)-1]) - 97], int(a)-1)
            # idxの左の値がa番目であれば、それを消す
            if char_idxs[ord(cS[int(a)-1]) - 97][idx-1] == int(a)-1:
                # delの方が早いか？
                char_idxs[ord(cS[int(a)-1]) - 97][idx-1:idx] = []
            
            # bの文字がa番目にあるよ、を保存
            bisect.insort_right(char_idxs[ord(b) - 97], int(a) - 1)

            # 置き換え
            cS[int(a) - 1] = b
    # q == 2の時、範囲の文字種の個数を調べる
    else:
        cnt = 0
        for i in range(26):
            # そもそもその文字が文字列全体になければ考えない
            if len(char_idxs[i]) == 0: continue
            # a <= X <= b を満たす値があれば、l〜rに文字chr(i+97)が含まれると言える
            l = bisect.bisect_left(char_idxs[i], int(a)-1)
            r = bisect.bisect_right(char_idxs[i], int(b)-1)

            if l < len(char_idxs[i]) and r > 0 and int(a)-1 <= char_idxs[i][l] and  int(b)-1 >= char_idxs[i][r-1]:
                cnt += 1

        print(cnt)

Submission status: Wrong Answer

Solution code:
import sys;input=sys.stdin.readline
n=int(input())
s=input()
num=2**(n-1).bit_length()
def segfunc(x,y):return x|y
seg=[0]*(2*num-1)
for i in range(n):seg[i+num-1]=2**(ord(s[i])-97)
for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
def update(i,x):
  i+=num-1;seg[i]=segfunc(x,seg[i])
  while i:i=(i-1)//2;seg[i]=segfunc(seg[i*2+1],seg[i*2+2])
def query(l,r):
  l+=num-1;r+=num-1
  if l==r:return seg[l]
  s=seg[l];l+=1
  while r-l>1:
    if ~l%2:s=segfunc(seg[l],s)
    if r%2:s=segfunc(seg[r],s);r-=1
    l//=2;r=(r-1)//2
  if l==r:return segfunc(s,seg[l])
  return segfunc(s,segfunc(seg[l],seg[r]))
for _ in range(int(input())):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i),2**(ord(c)-97))
  else:
    _,l,r=quer
    print(sum(map(int,bin(query(int(l)-1,int(r)-1))[2:])))

Submission status: Wrong Answer

Solution code:
import sys
import string
import random
from functools import lru_cache

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
            
    @lru_cache(maxsize=1000)
    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
          
    @lru_cache(maxsize=1000)
    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)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
ide_ele=0
n=int(input())
num=2**(n-1).bit_length()
seg=[ide_ele]*(2*num-1)
s=input()
for i in range(n):seg[i+num-1]=2**(ord(s[i])-97)
for i in range(num-2,-1,-1):seg[i]=seg[2*i+1]|seg[2*i+2]
def update(i,x):
  i+=num-1;seg[i]=x
  while i:i//=2;seg[i]=seg[i*2+1]|seg[i*2+2]
def query(l,r):
  l+=num-1;r+=num-1
  if l==r:return seg[l]
  s=seg[l];l+=1
  while r-l>1:
    if ~l%2:s|=seg[l]
    if r%2:s|=seg[r];r-=1
    l//=2;r=(r-1)//2
  return sum(map(int,bin(s|seg[l]|seg[r])[2:]))
q=int(input())
for _ in range(q):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,2**(ord(c)-97))
  else:
    _,l,r=quer
    print(query(int(l)-1,int(r)-1))

Submission status: Wrong Answer

Solution code:
n=int(input())
s=input()
num=2**(n-1).bit_length()
seg=[set()for _ in range(2*num-1)]
for i in range(n):seg[i+num-1].add(s[i])
for i in range(num-2,-1,-1):seg[i]|=seg[2*i+1]|seg[2*i+2]
q=int(input())
for _ in range(q):
  query=input().split()
  if query[0]=="1":
    _,i,c=query
    i=int(i)
    i+=num-1
    seg[i]={c}
    while i:
      i=(i-1)//2
      seg[i]=seg[2*i+1]|seg[2*i+2]
  else:
    _,l,r=map(int,query)
    l+=num-2
    r+=num-2
    if l==r:
      print(len(seg[l]))
      continue
    ans=seg[l]
    l+=1
    for _ in range(10000):
      if r-l<2:break
      if ~l%2:ans|=seg[l]
      if r%2:ans|=seg[r];r-=1
      l//=2
      r=(r-1)//2
    ans|=seg[l]|seg[r]
    print(len(ans))

Submission status: Wrong Answer

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

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.func, self.ide = func, ide
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i //= 2
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l //= 2; r //= 2
        return res
    
    def get(self, i):
        return self.data[self.n + i]

st = [SegmentTree(n, lambda x, y: x+y, 0) for _ in range(26)]
for i, c in enumerate(s): st[ord(c)-97].update(i, 1)

for _ in range(q):
    a, b, c = input().split()
    if a == "1":
        idx = int(b)
        for i in range(26):
            st[i].update(idx, 0)
        st[ord(c)-97].update(idx, 1)
    else:
        l, r = int(b)-1, int(c)
        res = 0
        for i in range(26):
            res += bool(st[i].query(l, r))
        print(res)

Submission status: Wrong Answer

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


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

Submission status: Wrong Answer

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 = {}
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)
        strings[check[S[a - 1]]].delete(a - 1)
        strings[check[b]].insert(a - 1)
    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)