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 .

Solution (Python):
class BalancingTree:
    def __init__(self, n):
        self.N = n
        self.root = self.node(1<<n, 1<<n)

    def append(self, v):
        v += 1
        nd = self.root
        while True:
            if v == nd.value:
                
                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
        nd = self.root
        prev = 0
        if nd.value < v: v = 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 += 1
        nd = self.root
        prev = 0
        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 += 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:
        def __init__(self, v, p):
            self.value = v
            self.pivot = p
            self.left = None
            self.right = None

k = (500000+1).bit_length()
dic = {}
for i in range(97, 123):
    dic[chr(i)] = BalancingTree(k)

n = int(input())
s = input()
lst = []
for i in range(n):
    lst.append(s[i])
    dic[s[i]].append(i)

ans = []
q = int(input())
for _ in range(q):
    que = input()
    if que[0] == '1':
        kind, i, c = que.split()
        i = int(i) - 1
        dic[lst[i]].delete(i)
        dic[c].append(i)
        lst[i] = c
    else:
        kind, l, r = map(int, que.split())
        l -= 2; r -= 1
        temp = 0
        for key in dic.keys():
            if dic[key].find_r(l) <= r:
                temp += 1
        ans.append(temp)

for i in ans:
    print(i)

Solution (Python):

def segfunc(x,y):
  return x|y 

def init(init_val):
  
  for i in range(n):
    seg[i+num-1]=init_val[i]  
  
  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([])


n = int(input())
S = [set([s]) for s in input()]
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

init(S)
q = int(input())
for _ in range(q):
  a,b,c = input().split()
  if a == '1':
    b = int(b)-1
    update(b, set([c]))
  elif a == '2':
    b = int(b)-1
    c = int(c)
    print(len(query(b,c)))

Solution (Python):
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LS(): return list(sys.stdin.readline().rstrip().split())  
def LS2(): return list(sys.stdin.readline().rstrip())  

N = I()
S = [set([a]) for a in LS2()]


def seg_func(x,y):
    return x | y

unit = set([])

class SegTree:  
    def __init__(self,N,seg_func,unit):
        self.N = N
        self.func = seg_func
        self.unit = unit
        self.tree = [self.unit]*(2*self.N)
    def build(self,init_value):  
        for i in range(self.N):
            self.tree[i+self.N] = init_value[i]
        for i in range(self.N-1,0,-1):
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
    def set_val(self,i,x):  
        i += self.N
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.func(self.tree[i << 1],self.tree[i << 1 | 1])
    def fold(self,L,R):  
        L += self.N
        R += self.N
        vL = self.unit
        vR = self.unit
        while L < R:
            if L & 1:
                vL = self.func(vL,self.tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.func(self.tree[R],vR)
            L >>= 1
            R >>= 1
        return self.func(vL,vR)


seg = SegTree(N,seg_func,unit)
seg.build(S)

Q = I()
for i in range(Q):
    a,b,c = LS()
    if a == '1':
        b = int(b)-1
        seg.set_val(b,set([c]))
    else:
        b,c = int(b)-1,int(c)-1
        print(len(seg.fold(b,c+1)))

Solution (Python):
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 1 << ((self.n - 1).bit_length())
        self.op = op 
        self.e = e 
        self.v = self._build(lst) 
        
    def _build(self, lst):
        
        
        tree = [self.e] * (self.N) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 1, 0, -1): tree[i] = self.op(tree[i << 1], tree[(i << 1)|1])
        return tree
    
    def __getitem__(self, i):
        return self.v[i + self.N]
    
    
    def update(self, i, x):
        v, op = self.v, self.op
        i += self.N
        v[i] = x
        while i > 0:
            i >>= 1 
            v[i] = op(v[i << 1], v[(i << 1)|1])
    
    
    def fold(self, l, r):
        N, e, v, op = self.N, self.e, self.v, self.op
        left = l + N; right = r + N
        L = R = e
        while left < right:
            if left & 1: 
                L = op(L, v[left])
                left += 1
            if right & 1: 
                right -= 1
                R = op(v[right], R)
            left >>= 1; right >>= 1
        return op(L, R)

def wa(set1, set2):
    return set1 | set2

n = int(input())
s = input()
lst = []
for i in range(n):
    lst.append(set([s[i]]))

st = SegmentTree(lst, wa, set([]))

ans = []
q = int(input())
for i in range(q):
    que = input()
    if que[0] == '1':
        kind, i, c = que.split()
        i = int(i) - 1
        st.update(i, set([c]))
    else:
        kind, l, r = map(int, que.split())
        l -= 1
        ans.append(len(st.fold(l, r)))

for i in ans:
    print(i)

Solution (Python):
class BIT:

    def __init__(self, N):
        
        self.N = N
        self.data = [0] * (N + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & (- i)
        return s

    def update(self, i, x):
        while i <= self.N:
            self.data[i] += x
            i += i & (- i)


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


def main():
    N = int(input())
    S = input()
    char_list = list(S)
    trees = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        trees[c2n(c)].update(i + 1, 1)
    Q = int(input())
    ans = list()
    for _ in range(Q):
        query = input().split()
        if query[0] == '1':
            _, i, c = query
            i = int(i) - 1
            before_c = char_list[i]
            char_list[i] = c
            trees[c2n(before_c)].update(i + 1, - 1)
            trees[c2n(c)].update(i + 1, 1)
        else:  
            _, left, right = query
            left, right = int(left) - 1, int(right) - 1
            cnt = 0
            for i in range(26):
                n = trees[i].sum(right + 1) - trees[i].sum(left)
                if n > 0:
                    cnt += 1
            ans.append(cnt)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    def update(self, idx, x):
        while idx <= self.n:
            self.bit[idx] += x
            idx += idx & (-idx)

    def query(self, idx):
        res = 0
        while idx > 0:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def sec_sum(self, left, right):
        return self.query(right) - self.query(left)

    def debug(self):
        print(*[self.sec_sum(i - 1, i) for i in range(1, self.n + 1)])


def resolve():
    n = int(input())
    S = list(input().rstrip())
    q = int(input())
    query = [list(input().split()) for _ in range(q)]

    bits = [BIT(S) for _ in range(26)]
    for i in range(n):
        bits[ord(S[i]) - ord("a")].update(i + 1, 1)

    for j in range(q):
        if query[j][0] == "1":
            _, i, c = query[j]
            i = int(i) - 1
            bits[ord(S[i]) - ord("a")].update(i + 1, -1)
            bits[ord(c) - ord("a")].update(i + 1, 1)
            S[i] = c
        else:
            _, l, r = query[j]
            l, r = int(l), int(r)
            res = 0
            for k in range(26):
                if bits[k].sec_sum(l - 1, r):
                    res += 1
            print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):


import sys
input = sys.stdin.readline


class SegmentTree:

    def __init__(self, n, op, e):
        """
        :param n: 要素数
        :param op: 二項演算
        :param e: 単位減
        例) 区間最小値  SegmentTree(n, lambda a, b : a if a < b else b, 10 ** 18)
            区間和     SegmentTree(n, lambda a, b : a + b, 0)
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 1 << (self.n - 1).bit_length()      
        self.tree = [self.e] * (self.size << 1)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築"""
        for i in range(self.n):
            self.tree[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.tree[i] = self.op(self.tree[i << 1], self.tree[(i << 1) + 1])

    def update(self, i, x):
        """i 番目の要素を x に更新"""
        i += self.size
        self.tree[i] = x
        while i > 1:
            i >>= 1
            self.tree[i] = self.op(self.tree[i << 1], self.tree[(i << 1) + 1])

    def get_val(self, l, r):
        """[l, r)の畳み込みの結果を返す"""
        l, r = l + self.size, r + self.size
        res = self.e
        while l < r:
            if l & 1:
                res = self.op(self.tree[l], res)
                l += 1
            if r & 1:
                r -= 1
                res = self.op(self.tree[r], res)
            l, r = l >> 1, r >> 1
        return res




def popcount(x):
    return bin(x).count("1")

N = int(input())
st = SegmentTree(N, lambda a, b: a | b, 0)
S = input().strip()
data = []
for s in S:
    data.append(1 << (ord(s) - ord("a")))
st.built(data)
Q = int(input())
for _ in range(Q):
    q, a, b = input().split()
    if q == "1":
        st.update(int(a)-1, 1 << (ord(b) - ord("a")))
    if q == "2":
        a = int(a) - 1
        b = int(b)
        print(popcount(st.get_val(a, b)))

Solution (Python):
import sys
input = sys.stdin.readline


class Bit:
    def __init__(self, n):
        self.n = n
        self.tree = [0]*(n+1)
        self.el = [0]*(n+1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1) )- 1
        return s

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        self.el[i] += x
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j=None):
        """ 部分区間和 [i, j) """
        if j is None:
            return self.el[i]
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1    
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x: 
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, s):
        """ [a0, a1, a2, ...] """
        return self.el[s]

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for s in self.el[:self.n]:
            yield s

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))



import string

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

B = [Bit(N) for _ in range(26)]

abc = string.ascii_lowercase                                            
abc2 = dict()
for i, s in enumerate(abc):
    abc2[s] = i

for i, s in enumerate(S):
    B[abc2[s]].add(i,1)

for _ in range(Q):
    q = list(input().split())
    if q[0] == "1":
        a = int(q[1]) - 1
        b = q[2]
        for i in range(26):
            if B[i].el[a] == 1:
                B[i].add(a,-1)
        B[abc2[b]].add(a,1)
    if q[0] == "2":
        a = int(q[1]) - 1
        b = int(q[2]) - 1
        res = 0
        for i in range(26):
            res += (B[i].get(a, b+1) > 0)
        print(res)

Solution (Python):

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

    def add(self, i, value):
        i = i + 1
        while i <= self.n:
            self.bit[i] += value
            i += i & -i

    def _sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def sum(self, l, r):
        return self._sum(r) - self._sum(l)

n = int(input())
S = input()
q = int(input())
Query = [input().split() for _ in range(q)]

bits = [BIT(n) for i in range(26)]
s = []
for i,c in enumerate(S):
    bits[ord(c) - ord("a")].add(i,1)
    s.append(c)

for q_type,fr,to in Query:
    if q_type == "1":
        i = int(fr)-1
        bits[ord(s[i]) - ord("a")].add(i,-1)
        bits[ord(to) - ord("a")].add(i,1)
        s[i] = to
    else:
        l,r = int(fr)-1,int(to)
        tmp = 0
        for i in range(26):
            if bits[i].sum(l,r):
                tmp += 1
        print(tmp)

Solution (Python):
import sys
import math
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]



def segfunc(x, y):
    return x | y


ide_ele = set()


class SegTree:
    """
    init(init_val, segfunc, ide_ele): 配列init_valで初期化、構築
    update(k, x): k番目の値をxに更新
    query(l, r): 区間[l, r)をsegfuncしたものを返す
    """
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n-1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2*i], self.tree[2*i+1])

    def update(self, k, x):
        """
        k番目の値をxに更新
        :param k: index(0-index)
        :param x: update value
        """
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k>>1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        """
        [l, r)のsegfuncしたものを得る
        :param l: 0-index
        :param r: 0-index
        :return:
        """
        res = self.ide_ele
        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r-1])
            l >>= 1
            r >>= 1
        return res


def main():
    N = NI()
    S = SI()
    Q = NI()
    querys = [list(SI().split()) for _ in range(Q)]
    S_sets = []
    for s in S:
        tmp = set()
        tmp.add(s)
        S_sets.append(tmp)

    segtree = SegTree(S_sets, segfunc, ide_ele)

    for query in querys:
        if query[0] == "1":
            segtree.update(int(query[1]) - 1, {query[2]})
        else:
            l, r = int(query[1])-1, int(query[2])
            print(len(segtree.query(l, r)))



if __name__ == "__main__":
    main()

Solution (Python):

class BIT:
    def __init__(self, n):
        
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        res = 0
        while i > 0:
            res += self.tree[i]
            i -= i & -i
        return res

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

trees = [BIT(5 * 10 ** 5 + 2) for _ in range(26)]
for i in range(N):
    trees[ord(S[i]) - ord("a")].add(i + 1, 1)

for _ in range(Q):
    s, *x = input().split()
    if s == "1":
        i = int(x[0])
        c = x[1]
        trees[ord(S[i - 1]) - ord("a")].add(i, -1)
        trees[ord(c) - ord("a")].add(i, 1)
        S[i - 1] = c
    else:
        l, r = map(int, x)
        cnt = 0
        for i in range(26):
            cnt += int(trees[i].sum(r) - trees[i].sum(l - 1) > 0)
        print(cnt)

Solution (Python):

import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
from collections import Counter, deque
from random import random
class Node:
        def __init__(self,value:int=-1):
            self.left = None
            self.right = None
            self.value = value
            self.priority = int(random()*10**7)
            self.count_partial = 1
            self.calc_partial = value
class Treap:
    
    def __init__(self,func=None):
        self.root = None
        self.func = lambda x,y,z:x+y+z if func is None else func

    def size(self, node:Node):
        return 0 if node is None else node.count_partial
    
    def calc_result(self, node):
        return 0 if node is None else node.calc_partial
    
    def node_key(self, node:None):
        return -1 if node is None else node.key

    def update(self, node):
        
        
        
        
        
        
        
        
        
        
        
        

        node.count_partial = self.size(node.left) + self.size(node.right) + 1
        node.calc_partial = self.func(self.calc_result(node.left),node.value,self.calc_result(node.right))
        return node

    def merge(self, left :Node, right:Node):
        if left is None or right is None:
            return left if right is None else right

        if left.priority > right.priority:
            left.right = self.merge(left.right,right)
            
            return self.update(left)
        else:
            right.left = self.merge(left,right.left)
            
            return self.update(right)




    

    
    
    

    
    
    
    
    
    
    
    
    def split(self, node:None, value):
        if node is None:
            return None,None
        if value <= node.value:
            left,right = self.split(node.left, value)
            node.left = right
            return left, self.update(node)
        else:
            left,right = self.split(node.right, value)
            node.right = left
            return self.update(node),right

    
    def insert(self, pos:int,value:int =-1):
        value = value if value > 0 else pos
        left, right = self.split(self.root, pos)
        new_node = Node(value)
        self.root = self.merge(self.merge(left,new_node),right)
    
    def erase(self, pos:int):
        middle,right = self.split(self.root, pos+1)
        left,middle = self.split(middle, pos)
        self.root = self.merge(left,right)

        

    def printTree(self, node=None, level=0):
        node = self.root if node is None else node
        if node is None:
            print('level=',level,'root is None')
            return
        else:
            print('level=',level,'v=',node.value,'c=',node.count_partial, 'p=',node.priority)
        if node.left is not None:
            self.printTree(node.left,level+1)
        
        if node.right is not None:
            self.printTree(node.right,level+1)
        
    

    def search(self, pos):
        
        v = self.root
        while v:
            left_count = self.node_size(v.left)
            if pos < left_count:
                v = v.left
            elif pos == left_count:
                return v.value
            else:
                v = v.right
                pos -= left_count + 1
        return -1

    def search2(self, value):
        v = self.root
        upper = 10**18
        while v:

            if value == v.value:
                return value

            elif value < v.value:
                upper = v.value
                v = v.left
            else:
                v = v.right
        return upper

    def search_recursively(self, pos, node):
        if node is None:
            return -1
        num_left = 0 if node.left is None else node.left.count_partial
        if num_left + 1 == pos:
            return node.value
        if pos <= num_left:
            return self.search_recursively(pos, node.left)
        else:
            return self.search_recursively(pos - num_left - 1, node.right)
        


    
                










def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    S = list(map(lambda c: ord(c) - ord('a'), list(input())))



    trees = []
    for i in range(26):
        trees.append(Treap())
    

    for i,c in enumerate(S):
        trees[c].insert(i)
    
    Q = int(input())
    out = []
    for _ in range(Q):
        q1,q2,q3 = input().split()
        if int(q1) == 1:
            iq = int(q2)-1
            before = S[iq]
            after = ord(q3)-ord('a')
            S[iq] = after
            trees[before].erase(iq)
            trees[after].insert(iq)

        else:
            l,r = int(q2)-1,int(q3)-1
            count = 0
            for i in range(26):
                if trees[i].search2(l) <= r:
                    count += 1
            out.append(count)
    print('\n'.join(map(str,out)))


if __name__ == '__main__':
    main()

Solution (Python):

import sys,os
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
from collections import Counter, deque
from random import random
class Node:
        def __init__(self,value:int=-1):
            self.left = None
            self.right = None
            self.value = value
            self.priority = int(random()*10**7)
            
            
class Treap:
    
    
    def __init__(self):
        self.root = None

    
    
    
    
    
    
    
    
    
    
    
    
    

    
    
    

    def merge(self, left :Node, right:Node):
        if left is None or right is None:
            return left if right is None else right

        if left.priority > right.priority:
            left.right = self.merge(left.right,right)
            
            return left
        else:
            right.left = self.merge(left,right.left)
            
            return right


    
    
    
    
    

    

    
    
    

    
    
    
    
    
    
    
    
    def split(self, node:None, value):
        if node is None:
            return None,None
        if value <= node.value:
            left,right = self.split(node.left, value)
            node.left = right
            return left, node
        else:
            left,right = self.split(node.right, value)
            node.right = left
            return node,right

    
    def insert(self, pos:int,value:int =-1):
        value = value if value > 0 else pos
        left, right = self.split(self.root, pos)
        new_node = Node(value)
        self.root = self.merge(self.merge(left,new_node),right)
    
    def erase(self, pos:int):
        middle,right = self.split(self.root, pos+1)
        left,middle = self.split(middle, pos)
        self.root = self.merge(left,right)

        

    def printTree(self, node=None, level=0):
        node = self.root if node is None else node
        if node is None:
            print('level=',level,'root is None')
            return
        else:
            print('level=',level,'v=',node.value,'c=',node.count_partial, 'p=',node.priority)
        if node.left is not None:
            self.printTree(node.left,level+1)
        
        if node.right is not None:
            self.printTree(node.right,level+1)
        
    

    def search(self, pos):
        
        v = self.root
        while v:
            left_count = self.node_size(v.left)
            if pos < left_count:
                v = v.left
            elif pos == left_count:
                return v.value
            else:
                v = v.right
                pos -= left_count + 1
        return -1

    def search2(self, value):
        v = self.root
        upper = 10**18
        while v:

            if value == v.value:
                return value

            elif value < v.value:
                upper = v.value
                v = v.left
            else:
                v = v.right
        return upper

    def search_recursively(self, pos, node):
        if node is None:
            return -1
        num_left = 0 if node.left is None else node.left.count_partial
        if num_left + 1 == pos:
            return node.value
        if pos <= num_left:
            return self.search_recursively(pos, node.left)
        else:
            return self.search_recursively(pos - num_left - 1, node.right)
        


    
                










def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    S = list(map(lambda c: ord(c) - ord('a'), list(input())))



    trees = []
    for i in range(26):
        trees.append(Treap())
    

    for i,c in enumerate(S):
        trees[c].insert(i)
    
    Q = int(input())
    out = []
    for _ in range(Q):
        q1,q2,q3 = input().split()
        if int(q1) == 1:
            iq = int(q2)-1
            before = S[iq]
            after = ord(q3)-ord('a')
            S[iq] = after
            trees[before].erase(iq)
            trees[after].insert(iq)

        else:
            l,r = int(q2)-1,int(q3)-1
            count = 0
            for i in range(26):
                if trees[i].search2(l) <= r:
                    count += 1
            out.append(count)
    print('\n'.join(map(str,out)))


if __name__ == '__main__':
    main()