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 SegmentTree: 
    def __init__(self,list,a,f=lambda x,y:x+y,inf=0):
        self.height=(len(list)-1).bit_length()+1 
        self.id=inf 
        self.tree=[self.id]*(2**self.height) 
        self.f=f
        for i in range(len(list)):
            if list[i]==a:
                self.tree[2**(self.height-1)+i]=1
        for i in range(2**(self.height-1)-1,0,-1):
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
        
    def update(self,i,x): 
        i+=2**(self.height-1)
        self.tree[i]=x
        while i>1:
            i//=2
            self.tree[i]=self.f(self.tree[2*i],self.tree[2*i+1])
    
    def query(self,l,r): 
        l+=2**(self.height-1)
        r+=2**(self.height-1)
        lf,rf=self.id,self.id
        while l<r:
            if l&1:
                lf=self.f(lf,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rf=self.f(self.tree[r],rf)
            l//=2
            r//=2
        return self.f(lf,rf)
n=int(input())
s=list(input())
q=int(input())
l=[]
for i in range(26):
    l.append(SegmentTree(s,chr(97+i),f=lambda x,y:x or y))
for _ in range(q):
    a,b,c=input().split()
    if a=="1":
        b=int(b)-1
        l[ord(s[b])-97].update(b,0)
        l[ord(c)-97].update(b,1)
        s[b]=c
    else:
        b,c=int(b)-1,int(c)
        count=0
        for i in range(26):
            if l[i].query(b,c):
                count+=1
        print(count)

Solution (Python):
def segfunc(x,y):
  return set(x)|set(y)
ide_ele=set()
class SegTree():
  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+=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):
    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
n=int(input())
s=input()
q=int(input())
st=SegTree(s,segfunc,ide_ele)
for _ in range(q):
  q,c,r=input().split()
  if q=='1':st.update(int(c)-1,r)
  else:print(len(st.query(int(c)-1,int(r))))

Solution (Python):
"""
セグメント木で行きたいところだけど、集合の管理が必要になるため、時間がかかりすぎてしまう。
と思いきや、文字の種類は26種類しかないので、問題ない。
"""
def main():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    class BIT:
        def __init__(self,n):
            self.size = n
            self.tree = [Counter([]) for _ in range(n+1)]
        
        def change(self,i,x,y):
            while i <= self.size:
                if x in self.tree[i]:
                    self.tree[i][x] -= 1
                if y not in self.tree[i]:
                    self.tree[i][y] = 1
                else:
                    self.tree[i][y] += 1
                i += i&-i
    
        def sum(self,i):
            s = Counter([])
            while i > 0:
                s += self.tree[i]
                i -= i&-i
            cnt = 0
            return s


    N = int(input())
    S = list(input())
    Q = int(input())
    bit = BIT(N)
    for i in range(N):
        bit.change(i+1," ",S[i])

    for _ in range(Q):
        q,a,b = input().split()
        if q == "1":
            x = S[int(a)-1]
            S[int(a)-1] = b
            bit.change(int(a),x,b)
        else:
            a = int(a)
            b = int(b)
            count = bit.sum(b) - bit.sum(a-1)
            ans = 0
            for v in count.values():
                if v > 0:
                    ans += 1
            print(ans)
main()

Solution (Python):
N = int(input())
S = list(input())
Q = int(input())
alphabet = "abcdefghijklmnopqrstuvwxyz"
num = dict()
for i, var in enumerate(alphabet):
  num[var] = i

class Bit():
  def __init__(self, N):
    self.__N = N
    self.__arr = [[0] * 26 for _ in range(1 + N)]
    
  def add_(self, x, a, i):
    while(x < self.__N + 1):
      self.__arr[x][i] += a
      x += x & -x
      
  def sum_(self, x, i):
    res = 0
    while(x > 0):
      res += self.__arr[x][i]
      x -= x & -x
    return res
  
  def sub_sum_(self, x, y, i):
    return self.sum_(y, i) - self.sum_(x, i)

Bit = Bit(N)
for i, var in enumerate(S):
  Bit.add_(i+1, 1, num[var])

for i in range(Q):
  q, l, r = input().split()
  l = int(l)
  if q == "1" and r != S[l-1]:
    temp = S[l-1]
    S[l-1] = r
    Bit.add_(l, -1, num[temp])
    Bit.add_(l, 1, num[r])
  elif q == "2":
    r = int(r)
    res = 0
    for j in range(26):
      res += min(1, Bit.sub_sum_(l-1, r, j))
    print(res)

Solution (Python):


class FenwickTree():
    
    
    
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    
    
    def summation(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    
    
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.summation(j) - self.summation(i-1)

N = int(input())
S_raw = input()
S = [0]*(N+1)
trees = [FenwickTree(N) for _ in range(26)]
for i in range(1,N+1):
    s = S_raw[i-1]
    S[i] = s
    k = ord(s)-ord('a')
    trees[k].add(i, 1)

Q = int(input())
for _ in range(Q):
    q,x,y = input().split()
    if q=='1':
        i,c = int(x),y
        s = S[i]
        k = ord(s)-ord('a')
        trees[k].add(i, -1)
        S[i] = c
        k = ord(c)-ord('a')
        trees[k].add(i, 1)
    else:
        l,r = int(x),int(y)
        ans = 0
        for k in range(26):
            ans = ans+1 if trees[k].get(l,r)>0 else ans
        print(ans)

Solution (Python):


import bisect
from collections import defaultdict

N = int(input())

S = list(input())
Q = int(input())



dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)

    if a == 1:
        b = int(b) - 1
        
        if S[b] == c:
            continue
        else:
            
            
            
            dict[S[b]].remove(b)
            idx = bisect.bisect(dict[c], b)
            dict[c].insert(idx, b)
            
            S[b] = c

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        
        char_cnt = 0
        for key, value in dict.items():
            
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_cnt += 1
        ans.append(char_cnt)

for i in ans:
    print(i)

Solution (Python):


import bisect
from collections import defaultdict

N = int(input())

S = list(input())
Q = int(input())



dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)

ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)

    if a == 1:
        b = int(b) - 1
        
        if S[b] == c:
            continue
        else:
            
            
            
            dict[S[b]].remove(b)
            idx = bisect.bisect(dict[c], b)
            dict[c].insert(idx, b)
            
            S[b] = c

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        
        char_cnt = 0
        for key, value in dict.items():
            
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_cnt += 1
        ans.append(char_cnt)

for i in ans:
    print(i)

Solution (Python):
import bisect
from collections import defaultdict

N = int(input())

S = list(input())
Q = int(input())

dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)


ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)

    if a == 1:
        b = int(b) - 1
        if S[b] == c:
            continue
        else:
            dict[S[b]].remove(b)
            idx = bisect.bisect_left(dict[c], b)
            dict[c].insert(idx, b)
            S[b] = c

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            x1 = bisect.bisect_left(value, b)
            x2 = bisect.bisect_right(value, c)
            if x2 - x1 > 0:
                char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)

Solution (Python):
import bisect
from collections import defaultdict
N = int(input())
S = list(input())
Q = int(input())

dict = defaultdict(list)
for i in range(N):
    dict[S[i]].append(i)


ans = []

for _ in range(Q):
    a, b, c = input().split()
    a = int(a)

    if a == 1:
        b = int(b) - 1
        if S[b] == c:
            continue
        else:
            dict[S[b]].remove(b)
            idx = bisect.bisect_left(dict[c], b)
            dict[c].insert(idx, b)
            S[b] = c

    elif a == 2:
        b = int(b) - 1
        c = int(c) - 1
        char_n = 0
        for key, value in dict.items():
            if len(value)>0:
                x1 = bisect.bisect_left(value, b)
                x2 = bisect.bisect_right(value, c)
                if x2 - x1 > 0:
                    char_n += 1
        ans.append(char_n)

for i in ans:
    print(i)

Solution (Python):


from bisect import bisect_left, bisect_right

N = int(input())

S = list(input())

Q = int(input())


dict = {chr(ord('a') + i): [] for i in range(26)}


for i in range(N):
    dict[S[i]].append(i)

ans = []

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1])-1, query[2]
        now = S[i]
        if now == x:
            continue
        dict[now].remove(i)
        next_i = bisect_left(dict[x], i)
        dict[x].insert(next_i, i)
        S[i] = x
    else:
        start, end = int(query[1])-1, int(query[2])-1
        tmp_cout = 0
        for alf_array in dict.values():
            if len(alf_array) == 0:
                continue
            ss = bisect_left(alf_array, start)
            gg = bisect_right(alf_array, end)
            if gg- ss > 0:
                tmp_cout += 1
        ans.append(tmp_cout)

for i in ans:
    print(i)

Solution (Python):


from bisect import bisect_left, bisect_right

N = int(input())

S = list(input())

Q = int(input())

memo = {chr(ord('a') + i): [] for i in range(26)}

for key,val in enumerate(S):
    memo[val].append(key)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1])-1, query[2]
        now = S[i]
        if now == x:
            continue
        memo[now].remove(i)
        next_i = bisect_left(memo[x], i)
        memo[x].insert(next_i, i)
        S[i] = x
    else:
        start, end = int(query[1])-1, int(query[2])-1
        tmp_cout = 0
        for alf_array in memo.values():
            if len(alf_array) == 0:
                continue
            ss = bisect_left(alf_array, start)
            gg = bisect_right(alf_array, end)
            if gg- ss > 0:
                tmp_cout += 1
        print(tmp_cout)

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

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

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N = int(readline())
    S = readline().strip()
    Q = int(readline())

    S = list(S)
    base = ord('a')

    tree = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        tree[ord(c) - base].add(i)

    ans = []
    for _ in range(Q):
        n, a, b = readline().split()
        if n == '1':
            i = int(a) - 1
            if S[i] != b:
                tree[ord(S[i]) - base].add(i, -1)
                tree[ord(b) - base].add(i, 1)
                S[i] = b
        else:
            l, r = int(a) - 1, int(b)
            tmp = 0
            for i in range(26):
                if tree[i].get_sum_range(l, r) > 0:
                    tmp += 1
            ans.append(tmp)

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


if __name__ == '__main__':
    main()

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


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

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

    def get_sum(self, i):
        i += 1
        x = 0
        while i > 0:
            x += self.data[i]
            i -= i & -i
        return x

    
    def get_sum_range(self, l, r):
        return self.get_sum(r - 1) - self.get_sum(l - 1)


def main():
    N = int(readline())
    S = readline().strip()
    Q = int(readline())

    S = list(S)

    tree = [BIT(N) for _ in range(26)]
    for i, c in enumerate(S):
        tree[ord(c) - ord('a')].add(i)

    ans = []
    for _ in range(Q):
        A = readline().split()
        if A[0] == '1':
            i, c = int(A[1]) - 1, A[2]
            if S[i] != c:
                tree[ord(S[i]) - ord('a')].add(i, -1)
                tree[ord(A[2]) - ord('a')].add(i, 1)
                S[i] = c
        else:
            l, r = int(A[1]) - 1, int(A[2]) - 1
            tmp = 0
            for i in range(26):
                if tree[i].get_sum_range(l, r + 1) > 0:
                    tmp += 1
            ans.append(tmp)

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


if __name__ == '__main__':
    main()

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
input = sys.stdin.readline
N = int(input())
S = list(map(lambda x: ord(x) - ord("a"), list(input())[: -1]))

class BIT:
  def __init__(self, n):
    self.n = n
    self.data = [0] * (n + 1)
    self.el = [0] * (n + 1)
  def sum(self, i):
    s = 0
    while i > 0:
      s += self.data[i]
      i -= i & -i
    return s
  def add(self, i, x):
    self.el[i] += x
    while i <= self.n:
      self.data[i] += x
      i += i & -i
  def get(self, i, j = None):
    if j is None:
      return self.el[i]
    return self.sum(j) - self.sum(i)
  def lowerbound(self, s):
    x = 0
    y = 0
    for i in range(self.n.bit_length(), -1, -1):
      k = x + (1 << i)
      if k <= self.n and (y + self.data[k] < s):
        y += self.data[k]
        x += 1 << i
    return x + 1

fwk = [BIT(N) for _ in range(26)]
for i in range(N): fwk[S[i]].add(i + 1, 1)
for _ in range(int(input())):
  q, x, y = input().split()
  if q == "1":
    x = int(x)
    y = ord(y) - ord("a")
    fwk[S[x - 1]].add(x, -1)
    fwk[y].add(x, 1)
    S[x - 1] = y
  else:
    x = int(x)
    y = int(y)
    res = 0
    for i in range(26): res += fwk[i].get(x - 1, y) > 0
    print(res)

Solution (Python):

import sys
sys.setrecursionlimit(10**6)


class SegmentTree:
    def __init__(self, N):
        self.size = 2 ** (N-1).bit_length()
        self.dat = [0] * (2*self.size)
    
    def update(self,i,x):
        i += self.size
        self.dat[i] = 1 << ord(x)-ord('a')
        while i > 0:
            i >>= 1
            self.dat[i] = self.dat[i*2] | self.dat[i*2+1]

    def fold(self, l, r):
        l += self.size
        r += self.size
        vl = 0
        vr = 0
        while l < r:
            if l & 1:
                vl |= self.dat[l]
                l += 1
            if r & 1:
                r -= 1
                vr |= self.dat[r]
            l >>= 1
            r >>= 1
        
        return bin(vl | vr).count('1')

def main():
    N = int(input())
    S = list(input())
    sg = SegmentTree(N)
    for i in range(N):
        sg.update(i,S[i])
    
    Q = int(input())
    for _ in range(Q):
        Query = input().split()
        if Query[0] == '1':
            sg.update(int(Query[1])-1, Query[2])
        else:
            res = sg.fold(int(Query[1])-1, int(Query[2]))
            print(res)

if __name__ == "__main__":
    main()

Solution (Python):
from bisect import bisect_left, bisect_right

N = int(input())

S = list(input())

Q = int(input())

memo = {chr(ord('a') + i): [] for i in range(26)}

for key,val in enumerate(S):
    memo[val].append(key)

for q in range(Q):
    query = list(input().split())
    if query[0] == '1':
        i, x = int(query[1])-1, query[2]
        now = S[i]
        if now == x:
            continue
        memo[now].remove(i)
        next_i = bisect_left(memo[x], i)
        memo[x].insert(next_i, i)
        S[i] = x
    else:
        start, end = int(query[1])-1, int(query[2])-1
        tmp_cout = 0
        for alf_array in memo.values():
            if len(alf_array) == 0:
                continue
            ss = bisect_left(alf_array, start)
            gg = bisect_right(alf_array, end)
            if gg- ss > 0:
                tmp_cout += 1
        print(tmp_cout)

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

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): 
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)


N = int(input())
S = str(input());Q = int(input())
A = []
for i in range(N):
  temp = S[i]
  num = ord(temp) - 97
  A.append(pow(2,num))
Tree = SegmentTree(A, segfunc, 0)
for i in range(Q):
  query = list(map(str,input().split()))
  if query[0] == "1":
    loc = int(query[1])-1 
    num = ord(query[2])-97
    Tree.update(loc,pow(2,num))
  else:
    left = int(query[1])-1
    right = int(query[2])-1
    ret = Tree.sum(left,right+1)
    ans = 0
    for j in range(26):
      if (ret>>j)&1 == 1:
        ans += 1
    print(ans)

Solution (Python):

class Bit:
    """ used for only int(>=0) 
        1-indexed (ignore 0-index)
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    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

    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 get_less_than_x_cnt(self, x):
        """ 累積和がx未満 の個数 """
        lb_pos, lb_sum = self.lower_bound(x)
        return lb_pos-1

    def get_less_than_and_x_cnt(self, x):
        """ 累積和がx以下 の個数 """
        lb_pos, lb_sum = self.lower_bound(x+1)
        return lb_pos-1
    
    def get_more_than_x_cnt(self, x):
        """ 累積和がxより大きい 個数 """
        return self.size - self.get_less_than_and_x_cnt(x)


def main():
    n = int(input())
    s = list(input())
    q = int(input())
    ql = []
    for _ in range(q): 
        num,a,b = map(str, input().split())
        ql.append((num,a,b))
    alp_d = {chr(ord('a') + i): Bit(n) for i in range(26)}

    for i, si in enumerate(s):
        alp_d[si].add(i+1,1)

    for query in ql:
        a,b,c = query
        if a == '1':
            b = int(b)
            before = s[b-1]
            alp_d[before].add(b, -1)
            alp_d[c].add(b,1)
            s[b-1] = c
        else:
            l,r = int(b),int(c)
            cnt = 0
            for v in alp_d.values():
                if v.sum(r)-v.sum(l-1) > 0:
                    cnt += 1
            print(cnt) 


if __name__ == "__main__":
    main()

Solution (Python):


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

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i + 1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  
        return str(list(self))

    def sum(self, i):
        
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

    def __setitem__(self, key, value):
        
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

(n,), (s,), _, *q = map(str.split, open(0))
*s, = s
BIT = [Bit(int(n)) for _ in [0] * 26]
for e, t in enumerate(s):
    BIT[ord(t) - 97].add(e, 1)
for a, b, c in q:
    if a == "1":
        i = int(b)
        BIT[ord(s[i - 1]) - 97].add(i - 1, -1)
        s[i - 1] = c
        BIT[ord(c) - 97].add(i - 1, 1)
    else:
        l, r = int(b), int(c)
        print(sum(BIT[i].sum(r) - BIT[i].sum(l - 1) > 0 for i in range(26)))

Solution (Python):
N = int(input())
S = input()
Q = int(input())
QUERY = [input().split() for _ in range(Q)]













def or_more_pow_two(n):
    if (n & (n-1)) == 0:
        return n
    return 1<<(len(bin(n))-2)

class SegmentTree:
    def __init__(self, n, l):
        self.n = or_more_pow_two(n)*2
        self.tree = [0]*self.n
        for i, l_i in enumerate(l):
            self.tree[self.n//2+i] = l_i
        for i in reversed(range(1, self.n//2)):
            self.node_update(i)
            

    
    def find(self, l, r, fl=1, fr="self.n//2+1", node=1):
        if fr == "self.n//2+1":
            fr = self.n//2+1
        
        if l <= fl and fr <= r:
            
            return self.tree[node]
        elif fr <= l or r <= fl:
            
            return 0
        else:
            
            mid = (fl+fr)//2
            a = self.find(l, r, fl=fl, fr=mid, node=2*node)
            b = self.find(l, r, fl=mid, fr=fr, node=2*node+1)
            return a | b

    def update(self, index, v):
        
        x = self.n//2+index-1
        self.tree[x] = v
        while x > 0:
            x >>= 1
            self.node_update(x)

    def node_update(self, index):
        
        self.tree[index] = self.tree[2*index] | self.tree[2*index+1]

def char_to_bit(c):
    i = ord(c) - 97
    return (1 << i)
def bit_to_type_count(b):
    
    r = bin(b)[2:].count("1")
    
    return r




segtree = SegmentTree(N, map(char_to_bit, S))

for t, *query in QUERY:
    t = int(t)
    if t == 1:
        i, c = query
        i, c = int(i), c
        segtree.update(i, char_to_bit(c))
    elif t == 2:
        l, r = map(int, query)
        l, r = l, r+1
        r = segtree.find(l, r)
        r = bit_to_type_count(r)
        print(r)

Solution (Python):
class Binary_Indexed_Tree:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [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 built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

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

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        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, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i + 1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i + 1)

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


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


n = int(input())
s = [str2int(i) for i in input()]
B = [Binary_Indexed_Tree(n) for i in range(26)]

for i in range(n):
    B[s[i]].add(i, 1)

for _ in range(int(input())):
    t, a, b = input().split()
    if t == "1":
        a = int(a) - 1
        b = str2int(b)
        B[s[a]].add(a, -1)
        B[b].add(a, 1)
        s[a] = b
    else:
        a, b = int(a) - 1, int(b)
        ans = 0
        for v in B:
            ans += v.get(a, b) > 0
        print(ans)

Solution (Python):
import sys
input=sys.stdin.readline
n=int(input())
BIT=[[0]*n for i in range(26)]
w=[ord(x)-ord("a") for x in input()]
for i in range(n):
	k=i+1
	while k<=n:
		BIT[w[i]][k-1]+=1
		k=k+(k&-k)
q=int(input())
for i in range(q):
	a,b,c=input().split()
	if a=="1":
		k=int(b)
		while k<=n:
			BIT[ord(c)-ord("a")][k-1]+=1
			k=k+(k&-k)
		k=int(b)
		while k<=n:
			BIT[w[int(b)-1]][k-1]-=1
			k=k+(k&-k)	
		w[int(b)-1]=ord(c)-ord("a")
	else:
		b=int(b);c=int(c)
		ans=0
		for i in range(26):
			cnt=0
			k=c
			while k!=0:
				cnt+=BIT[i][k-1]
				k=k-(k&-k)
			k=b-1
			while k!=0:
				cnt-=BIT[i][k-1]
				k=k-(k&-k)
			if cnt>0:
				ans+=1
		print(ans)