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:
def main():
  n=int(input())
  s=list(input())
  q_=int(input())
  q=[input().split() for _ in range(q_)]
  #n= 500000
  #s=list('abcdfghijk'*(n//10))
  #q_=2000
  #q=[]
  #for i in range(q_):
  #  q.append([str(i%2+1),str(i//2),str(i)])
  from collections import defaultdict
  d=defaultdict(lambda:set())
  for i,si in enumerate(s):
    d[si].add(i+1)
  patch=[0]*(n+1)
  for qi in q:
    if qi[0]=='1':
      patch[int(qi[1])]=qi[2]
    else:
      l,r=int(qi[1]),int(qi[2])
      patchs={p for p in patch[l:r+1] if p!=0}
      ans=len(patchs)
      for k,v in d.items():
        if k in patchs:
          continue
        if len({vi for vi in v if l<=vi and vi<=r})>0:
          ans+=1
      print(ans)

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())

Submission status: Wrong Answer

Solution code:
import bisect

N=int(input())
S=input()
S=[None]+[S[i] for i in range(N)]
Q=int(input())
alphabet='abcdefghijklmnopqrstuvwxyz'
nums={}
for a in alphabet:
  nums[a]=[]
  
for i in range(1, N):
  s=S[i]
  tmp=nums[s]
  if len(tmp)==0:
    nums[s]=[i]
  else:
    p=bisect.bisect_left(tmp, i)
    if p<len(tmp):
      nums[s]=tmp[:p]+[i]+tmp[p:]
    else:
      nums[s]=tmp+[i]
ans=[]
for _ in range(Q):
  x, y, z=input().split()
  if x=='1':
    y=int(y)
    tmp=nums[S[y]]
    p=bisect.bisect_left(tmp, y)
    if p==len(tmp):
      nums[S[y]]=tmp[:-1]
    else:
      nums[S[y]]=tmp[:p]+tmp[p+1:]
      
    tmp=nums[z]
    p=bisect.bisect_left(tmp, y)
    if p==len(tmp)-1:
      nums[z]=tmp+[y]
    else:
      nums[z]=tmp[:p]+[y]+tmp[p:]
      
    S[y]=z
    
  else:
    l=int(y)
    r=int(z)
    out=0
    for a in alphabet:
      tmp=nums[a]
      if len(tmp)==0:
        continue
        
      if l<=tmp[0]<=r or l<=tmp[-1]<=r:
        out+=1
      elif tmp[-1]<l or r<tmp[0]:
        pass
      else:
        p=bisect.bisect_right(tmp, l-1)
        if p<len(tmp) and l<=tmp[p]<=r:
          out+=1
    ans.append(out)
    
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().split()
def LST2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)

class Node:
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None
        self.height = 0 #ノードの高さ


class AVL:
    def __init__(self):
        self.root = None


    def get_height(self, node):
        if not node:
            return -1
        return node.height

    def overwrite_height(self, node):
        return max(self.get_height(node.left),self.get_height(node.right))+1

    def get_balance(self, node):
        '''
        返り値が1以上の時、左がより高いので右回転
        -1以下の時左回転
        '''
        if not node:
            return 0
        return self.get_height(node.left) - self.get_height(node.right)

    def rotate_right(self, node): #nodeが回転の頂点、node.leftが頂点にくる。頂点を返す
        temp_left = node.left
        temp_left_right = temp_left.right
        temp_left.right = node
        node.left = temp_left_right

        node.height = self.overwrite_height(node)
        temp_left.height = self.overwrite_height(temp_left)

        return temp_left

    def rotate_left(self, node): #nodeが回転の頂点、node.leftが頂点にくる
        temp_right = node.right
        temp_right_left = temp_right.left
        temp_right.left = node
        node.right = temp_right_left

        node.height = self.overwrite_height(node)
        temp_right.height = self.overwrite_height(temp_right)

        return temp_right

    def insert(self, data):
        #print('--------------')
        #print('start inserting {}'.format(data))
        self.root = self._insert(data, self.root)
        #print('finish inserting')
        #print('--------------')

    def _insert(self, data, node): #dataをnodeに挿入、回転した上でrootを返す
        if not node:
            return Node(data)

        if data < node.data:
            node.left = self._insert(data,node.left)
        else:
            node.right = self._insert(data, node.right)
        node.height = self.overwrite_height(node)

        return self.settle_unbalance(data, node)

    def settle_unbalance(self, data, node): #回転を行なった上でrootを返す
        balance = self.get_balance(node)
        if balance > 1 and data < node.left.data:
            #print('right')
            return self.rotate_right(node)
        if balance < -1 and data > node.right.data:
            #print('left')
            return self.rotate_left(node)
        if balance > 1 and data > node.left.data:
            #print('left,right')
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        if balance < -1 and data < node.right.data:
            #print('right,left')
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)
        return node

    def remove(self, data):
        if self.root:
                self.root = self._remove(data, self.root)

    def _remove(self, data, node):
        if not node:
            return None
        if data < node.data:
            node.left = self._remove(data, node.left)
        elif data > node.data:
            node.right = self._remove(data, node.right)
        else:
            if not node.right and not node.left:
                del node
                return None
            if not node.right:
                temp = node.left
                del node
                return temp
            if not node.left:
                temp = node.right
                del node
                return temp

            def _get_max_node(node): #左側のsubtreeの最大ノードを代わりのノードとする
                if node.right:
                    return _get_max_node(node.right)
                return node
            temp = _get_max_node(node.left)
            node.data = temp.data
            node.left = self._remove(temp.data, node.left) #この場合もとのノード削除は不要。削除ノードを、新規ノードにおきかえればよい

        if not node:
            return node

        node.height = self.overwrite_height(node)
        balance = self.get_balance(node)
        if balance > 1 and self.get_balance(node.left) >= 0:
            return self.rotate_right(node)
        if balance < -1 and self.get_balance(node.right) <= 0:
            return self.rotate_left(node)
        if balance > 1 and self.get_balance(node.left) < 0:
            node.left = self.rotate_left(node.left)
            return self.rotate_right(node)
        if balance < -1 and self.get_balance(node.right) > 0:
            node.right = self.rotate_right(node.right)
            return self.rotate_left(node)

        return node


    def search(self, search): #インターフェース
        searcher = self._search(search)
        if searcher is None:
            pass
            #print('Search target is not found.')
        elif searcher == True:
            pass
            #print(str(search)+' is found.')
        elif searcher == False:
            pass
            #print(str(search)+' is not found.')

    def _search(self,search):
            n = self.root
            if n is None:
                return None
            else:
                lst = []
                lst.append(n)
                while len(lst) > 0:
                    node = lst.pop()
                    if node.data == search:
                        return True
                    if node.right is not None:
                        lst.append(node.right)
                    if node.left is not None:
                        lst.append(node.left)
                return False

    def search_higher(self, search):
        if self.root:
            return self._search_higher(search, self.root, None)
        else:
            print('木構造がありません')

    def _search_higher(self, search, node, temp_high):
        '''
        nodeを頂点とする部分木から、searchより大きい中でもっとも小さいnodeのデータを返す
        '''
        if node is None:
            return temp_high
        if node.data > search:
            temp_high = node.data
            if node.left is None:
                return temp_high
            else:
                return self._search_higher(search, node.left, temp_high)
        elif node.data < search:
            if node.right is None:
                return temp_high
            else:
                return self._search_higher(search, node.right, temp_high)
        else:  #nodeの値が探索値と一致する時
            if node.right is None:
                return temp_high
            else:
                if temp_high is None:
                    return self.end_lower(node.right)
                else:
                    return min(temp_high, self.end_lower(node.right))

    def end_lower(self, node):
        #あるnodeの下の部分木のうち最小値 nodeにdataあることが前提
        if node.left is None:
            return node.data
        else:
            return self.end_lower(node.left)

    def traverse_inorder(self):
        if self.root:
            self._traverse_inorder(self.root)
            # 改行対策
            print()
        else:
            print('木は空です。')

    def _traverse_inorder(self, node):
        if node.left:
            self._traverse_inorder(node.left)
        sep = '|'*node.height
        print(sep+str(node.data)+sep, end=' ')
        if node.right:
            self._traverse_inorder(node.right)

N = I()
S = ST()
Q = I()
D = {}
for i in range(N):
    letter = S[i]
    D[letter] = D.get(letter,AVL())
    D[letter].insert(i)

for _ in range(Q):
    q = LST()
    if q[0]=='1':
        i = int(q[1])
        c = q[2]
        for letter in D:
            D[letter].remove(i-1)
        D[c] = D.get(c,AVL())
        D[c].insert(i-1)
    else:
        ans = 0
        l = int(q[1])
        r = int(q[2])
        for letter in D:
            next_idx = D[letter].search_higher(l-2)
            if next_idx is not None:
                if r-1 >= next_idx:
                    ans += 1

        print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import math
from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
from collections import deque
from bisect import bisect_left
from itertools import product
def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
#文字列を一文字ずつ数字に変換、'5678'を[5,6,7,8]とできる
def LSI(): return list(map(int, list(sys.stdin.readline().rstrip())))
def LSI2(N): return [list(map(int, list(sys.stdin.readline().rstrip()))) for i in range(N)]
#文字列として取得
def ST(): return sys.stdin.readline().rstrip()
def LST(): return sys.stdin.readline().split()
def LST2(N): return [sys.stdin.readline().split() for i in range(N)]
def FILL(i,h): return [i for j in range(h)]
def FILL2(i,h,w): return [FILL(i,w) for j in range(h)]
def FILL3(i,h,w,d): return [FILL2(i,w,d) for j in range(h)]
def FILL4(i,h,w,d,d2): return [FILL3(i,w,d,d2) for j in range(h)]
def sisha(num,digit): return Decimal(str(num)).quantize(Decimal(digit),rounding=ROUND_HALF_UP)
#'0.01'や'1E1'などで指定、整数に戻すならintをかます
MOD = 1000000007
INF = float("inf")
sys.setrecursionlimit(10**6+10)


N = I()
S = ST()
Q = I()
D = {}
for i in range(N):
    letter = S[i]
    D[letter] = D.get(letter,set())
    D[letter].add(i)

for _ in range(Q):
    q = LST()
    if q[0]=='1':
        i = int(q[1])
        c = q[2]
        for letter in D:
            if i-1 in D[letter]:
                D[letter].remove(i-1)
        D[c] = D.get(c,set())
        D[c].add(i-1)
    else:
        ans = 0
        l = int(q[1])
        r = int(q[2])
        for letter in D:
            to_l = list(D[letter])
            idx = bisect_left(to_l,l-1)
            if idx >= len(to_l):
                continue
            next_idx = to_l[idx]
            if r-1 >= next_idx:
                ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

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

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
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()
     

class SegmentTree():
    def __init__(self, arr):
        self.arr = arr
        self.size = self.calc_size(arr)
        self.n = (self.size+ 1) // 2 
        self.value = [0 for _ in range(self.size)]

    def calc_size(self, array):
        i = 1
        while i < len(array):
            i = i << 1
        return (i << 1) - 1

    def update(self, i, x):
        # 1 + 2 + ... + N/2 = N-1
        i += self.n - 1
        self.value[i] = x
        while i > 0:
            i = (i - 1)//2
            self.value[i] = max(self.value[2*i+1], self.value[2*i+2])

    def query(self, l, r):
        # find [l, r)
        def _query(l, r, node_i, node_l, node_r):
            # node_i: node = value[node_i]
            # node_l: node.leftChild is in charge of [node_l, m)
            # node_r: node.rightChild is in charge of [m, node_r)

            if node_r <= l or r <= node_l:
                return 0

            if l <= node_l and node_r <= r:
                return self.value[node_i]

            c1 = _query(l, r, 2 * node_i + 1, node_l, (node_l + node_r) // 2)
            c2 = _query(l, r, 2 * node_i + 2, (node_l + node_r) // 2, node_r)
            return max(c1, c2)

        return _query(l, r+1, 0, 0, self.n)

    def __str__(self):
        return ' '.join([str(x) for x in self.value])

    def __repr__(self):
        return ' '.join([str(x) for x in self.value])

def main():
    N = I()
    trees = [SegmentTree([0 for _ in range(N)]) for _ in range(26)]
    s = S()

    for i, c in enumerate(s):
        j = ord(c) - ord('a')
        trees[j].update(i, 1)

    Q = I()
    queries = []
    for _ in range(Q):
        queries.append(LS())

    for query in queries:
        # import pdb
        # pdb.set_trace()
        q, a, b = query
        q = int(q)
        a = int(a) - 1
        if q == 1:
            i = a
            j = ord(s[i]) - ord('a')
            trees[j].update(i, 0)
            j = ord(b) - ord('a')
            trees[j].update(i, 1)
        else:
            b = int(b)
            b -= 1
            kind = 0
            for j in range(26):
                kind += trees[j].query(a, b)
            print(kind)

main()

Submission status: Wrong Answer

Solution code:
import bisect

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

alphabet="abcdefghijklmnopqrstuvwxyz"
bag={l:[] for l in alphabet}
for i in range(N):
    bag[S[i]].append(i+1)
print(bag)

for i in range(Q):
    Type,a,b=input().split()
    if Type=='1':
        a=int(a)
        bag[S[a-1]].remove(a)
        S[a-1]=b
        bisect.insort(bag[b],a)
    else:
        cnt=0
        a,b=int(a),int(b)
        for l in alphabet:
            bl=len(bag[l])
            if bl>0:
                left=bisect.bisect_left(bag[l],a)
                if left!=bl and bag[l][left]<=b:
                    cnt+=1
        print(cnt)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_e

from string import ascii_lowercase
from bisect import bisect_left
from collections import defaultdict

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

store = {c: set({}) for c in ascii_lowercase}
# locs = {c: [] for c in ascii_lowercase}
for i in range(N):
    store[S[i]].add(i)
    # locs[S[i]].append(i)

for _ in range(Q):
    qt, l, r = input().split()
    # print(qt, l, r)
    if qt == '1':
        l = int(l)
        for ch in store:
            if l in store[ch]:
                store[ch].remove(l)
        store[r].add(l)

    else:
        l, r = int(l), int(r)
        count = 0
        for ch in store:
            if any([True for i in store[ch] if l <= i + 1 and i + 1 <= r]):
                count += 1
        print(count)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val=init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length() #Nを超える最小の2のべき乗
        # 0-indexedで管理(N0-1からはじまる)
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res= left | right
        return res

    def update(self,k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])
    
            if L & 1:
                s = self._segfunc(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

def chartobit(c):
    return 1<<(ord(c)-97)
n=inp()
s=[chartobit(i) for i in list(input()) if i!="\n"]
st = SegmentTree(0, n)
for i in range(n):
    st.update(i,s[i])
q = inp()
ans = []
for i in range(q):
    mode, first, second = input().split()
    if mode == "1":
        # if second in st.data[int(first) - 1 + st.N0 - 1]:
        #     continue
        st.update(int(first) - 1, chartobit(second))
    else:
        ans.append((st.query(int(first) - 1, int(second))))
for i in ans:
    print(sum(map(int,bin(i)[2:])))
print(st.data)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val=init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res= left | right
        return res

    def update(self,k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])
    
            if L & 1:
                s = self._segfunc(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n=inp()
s=input()
st = SegmentTree(0,n)
for i in range(n):
    st.update(i,1<<(int.from_bytes(s[i].encode(),'little')-int.from_bytes('a'.encode(),'little')))
q = inp()
ans = []
for i in range(q):
    mode, first, second = input().split()
    if mode == "1":
        st.update(int(first),1<<(int.from_bytes(str(second).encode(),'little')-int.from_bytes('a'.encode(),'little')))
    else:
        ans.append(bin(st.query(int(first) - 1, int(second))).count("1"))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val=init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res= left | right
        return res

    def update(self,k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k > 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])
    
            if L & 1:
                s = self._segfunc(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n=inp()
s=input()
st = SegmentTree(0,n)
for i in range(n):
    st.update(i,1<<(int.from_bytes(s[i].encode(),'big')-int.from_bytes('a'.encode(),'big')))
q = inp()
ans = []
for i in range(q):
    mode, first, second = input().split()
    if mode == "1":
        st.update(int(first),1<<(int.from_bytes(str(second).encode(),'big')-int.from_bytes('a'.encode(),'big')))
    else:
        ans.append(bin(st.query(int(first) - 1, int(second))).count("1"))
for i in ans:
    print(i)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, heapq, collections
from operator import itemgetter
# a.sort(key=itemgetter(i)) # i番目要素でsort
from functools import lru_cache
# @lru_cache(maxsize=None)
sys.setrecursionlimit(10**8)
input = sys.stdin.readline
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp():
    '''
    一つの整数
    '''
    return int(input())
def inpl():
    '''
    一行に複数の整数
    '''
    return list(map(int, input().split()))

class SegmentTree():
    def __init__(self, init_val, N):
        """
        Parameters
        ----------
        init_val:int
            identity element
        N:int
            the number of nodes
        """
        self.init_val=init_val
        # Range Minimum Query
        self.N0 = 2**(N-1).bit_length()
        # 0-indexedで管理
        self.data = [self.init_val] * (2 * self.N0)

    def _segfunc(self, left, right):
        res= left | right
        return res

    def update(self,k, x):
        """
        Parameters
        ----------
        k:int
            target index(0-index)
        x:any
            target value
        """
        k += self.N0-1
        self.data[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.data[k] = self._segfunc(self.data[2*k+1], self.data[2*k+2])

    def query(self, l, r):
        """
        Parameters
        ----------
        l,r:int
            target range [l,r)

        Return
        ----------
        res:any
            val
        """
        L = l + self.N0
        R = r + self.N0
        s = self.init_val
        while L < R:
            if R & 1:
                R -= 1
                s = self._segfunc(s, self.data[R-1])
    
            if L & 1:
                s = self._segfunc(s, self.data[L-1])
                L += 1
            L >>= 1; R >>= 1
        return s

n=inp()
s=input()
st = SegmentTree(0,n)
for i in range(n):
    st.update(i,1<<(int.from_bytes(s[i].encode(),'big')-int.from_bytes('a'.encode(),'big')))
q = inp()
ans = []
for i in range(q):
    mode, first, second = input().split()
    if mode == "1":
        st.update(int(first),1<<(int.from_bytes(str(second).encode(),'big')-int.from_bytes('a'.encode(),'big')))
    else:
        ans.append(bin(st.query(int(first) - 1, int(second))).count("1"))
for i in ans:
    print(i)