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: Accepted

Solution code:
#coding:utf-8
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 = random()
            # self.count_partial = 1
            # self.sum_partial = value
class Treap:
    
    #Node [left, right, key, value, priority]
    def __init__(self):
        self.root = None

    # def update(self, node):
    #     if node.left is None:
    #         left_count = 0
    #         left_sum = 0
    #     else:
    #         left_count = node.left.count_partial
    #         left_sum = node.left.sum_partial
    #     if node.right is None:
    #         right_count = 0
    #         right_sum = 0
    #     else:
    #         right_count = node.right.count_partial
    #         right_sum = node.right.sum_partial

    #     node.count_partial = left_count + right_count + 1
    #     node.sum_partial = left_sum + right_sum + node.value
    #     return node

    def merge(self, left_tree, right_tree):
        if left_tree is None or right_tree is None:
            return left_tree if right_tree is None else right_tree

        # priority
        if left_tree[4] > right_tree[4]:
            left_tree[1] = self.merge(left_tree[1], right_tree)
            # return self.update(left)
            return left_tree
        else:
            right_tree[0] = self.merge(left_tree,right_tree[0])
            # return self.update(right)
            return right_tree


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

    #指定された場所のノードは右の木に含まれる

    # def split(self, node:Node, key:int, level=0):
    #     if node is None:
    #         return (None,None)

    #     if key <= self.node_size(node.left):
    #         left,right = self.split(node.left, key,level+1)
    #         node.left = right
    #         return left, self.update(node)
    #     else:
    #         left,right = self.split(node.right, key - self.node_size(node.left) - 1,level+1)
    #         node.right = left
    #         return self.update(node),right 
    def split(self, node:None, value):
        if node is None:
            return None,None

        if value <= node[3]:
            left_tree,right_tree = self.split(node[0], value)
            node[0] = right_tree
            return left_tree, node
        else:
            left_tree,right_tree = self.split(node[1], value)
            node[1] = left_tree
            return node, right_tree

    
    def insert(self, key:int,value:int =-1):
        value = value if value > 0 else key
        left_tree, right_tree = self.split(self.root, key)
        new_node = [None,None,key,value,random()]
        self.root = self.merge(self.merge(left_tree,new_node),right_tree)
    
    def erase(self, pos:int):
        middle_tree,right_tree = self.split(self.root, pos+1)
        left_tree,middle_tree = self.split(middle_tree, pos)
        self.root = self.merge(left_tree,right_tree)

        

    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):
    #     #return self.search_recursively(pos,self.root)
    #     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[3]:
                return value

            elif value < v[3]:
                upper = v[3]
                v = v[0]
            else:
                v = v[1]
        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()

Submission status: Accepted

Solution code:
#coding:utf-8
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 = random()
            # self.count_partial = 1
            # self.sum_partial = value
class Treap:
    
    #Node [left, right, key, value, priority]
    def __init__(self):
        self.root = None

    # def update(self, node):
    #     if node.left is None:
    #         left_count = 0
    #         left_sum = 0
    #     else:
    #         left_count = node.left.count_partial
    #         left_sum = node.left.sum_partial
    #     if node.right is None:
    #         right_count = 0
    #         right_sum = 0
    #     else:
    #         right_count = node.right.count_partial
    #         right_sum = node.right.sum_partial

    #     node.count_partial = left_count + right_count + 1
    #     node.sum_partial = left_sum + right_sum + node.value
    #     return node

    def merge(self, left_tree, right_tree):
        if left_tree is None or right_tree is None:
            return left_tree if right_tree is None else right_tree

        # priority
        if left_tree[4] > right_tree[4]:
            left_tree[1] = self.merge(left_tree[1], right_tree)
            # return self.update(left)
            return left_tree
        else:
            right_tree[0] = self.merge(left_tree,right_tree[0])
            # return self.update(right)
            return right_tree


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

    #指定された場所のノードは右の木に含まれる

    # def split(self, node:Node, key:int, level=0):
    #     if node is None:
    #         return (None,None)

    #     if key <= self.node_size(node.left):
    #         left,right = self.split(node.left, key,level+1)
    #         node.left = right
    #         return left, self.update(node)
    #     else:
    #         left,right = self.split(node.right, key - self.node_size(node.left) - 1,level+1)
    #         node.right = left
    #         return self.update(node),right 
    def split(self, node:None, value):
        if node is None:
            return None,None

        if value <= node[3]:
            left_tree,right_tree = self.split(node[0], value)
            node[0] = right_tree
            return left_tree, node
        else:
            left_tree,right_tree = self.split(node[1], value)
            node[1] = left_tree
            return node, right_tree

    
    def insert(self, key:int,value:int =-1):
        value = value if value > 0 else key
        left_tree, right_tree = self.split(self.root, key)
        new_node = [None,None,key,value,int(random()*10**7)]
        self.root = self.merge(self.merge(left_tree,new_node),right_tree)
    
    def erase(self, pos:int):
        middle_tree,right_tree = self.split(self.root, pos+1)
        left_tree,middle_tree = self.split(middle_tree, pos)
        self.root = self.merge(left_tree,right_tree)

        

    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):
    #     #return self.search_recursively(pos,self.root)
    #     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[3]:
                return value

            elif value < v[3]:
                upper = v[3]
                v = v[0]
            else:
                v = v[1]
        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()

Submission status: Accepted

Solution code:
#coding:utf-8
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 = random()
            # self.count_partial = 1
            # self.sum_partial = value
class Treap:
    
    #Node [left, right, key, value, priority, num_partial, sum_partial]
    def __init__(self):
        self.root = None

    # def update(self, node):
    #     if node.left is None:
    #         left_count = 0
    #         left_sum = 0
    #     else:
    #         left_count = node.left.count_partial
    #         left_sum = node.left.sum_partial
    #     if node.right is None:
    #         right_count = 0
    #         right_sum = 0
    #     else:
    #         right_count = node.right.count_partial
    #         right_sum = node.right.sum_partial

    #     node.count_partial = left_count + right_count + 1
    #     node.sum_partial = left_sum + right_sum + node.value
    #     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)
            return left
        else:
            right.left = self.merge(left,right.left)
            # return self.update(right)
            return right


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

    #指定された場所のノードは右の木に含まれる

    # def split(self, node:Node, key:int, level=0):
    #     if node is None:
    #         return (None,None)

    #     if key <= self.node_size(node.left):
    #         left,right = self.split(node.left, key,level+1)
    #         node.left = right
    #         return left, self.update(node)
    #     else:
    #         left,right = self.split(node.right, key - self.node_size(node.left) - 1,level+1)
    #         node.right = left
    #         return self.update(node),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):
        #return self.search_recursively(pos,self.root)
        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()

Submission status: Accepted

Solution code:
import sys
from io import StringIO
import unittest
import os


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番目の値をxに更新
        k: index(0-index)
        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):
        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


# 再帰処理上限(dfs作成時に設定するのが面倒なので限度近い値を組み込む)
sys.setrecursionlimit(999999999)


# 実装を行う関数
def resolve(test_def_name=""):
    def segfunc(x, y):
        return x + y

    n = int(input())
    s = input()
    q = int(input())
    query_s = [list(input().split()) for i in range(q)]

    alpha2int = lambda c: ord(c) - 97

    sumcun = [[0 for a in range(n)] for i in range(26)]
    # 数え上げ実施
    for cnt, char in enumerate(list(s)):
        sumcun[alpha2int(char)][cnt] = 1

    # 各アルファベットが区間内で何回利用されているか、を保持するセグメントツリーを作成
    seg_s = [SegTree(sumcun[i], segfunc=segfunc, ide_ele=0) for i in range(26)]

    s_list = list(s)
    for query in query_s:
        if query[0] == "1":
            # 文字を変換
            target = int(query[1]) - 1  # 変換される文字の添え字
            # まず、変換される文字の利用回数。元々の値から-1減算
            target_tree = alpha2int(s_list[target])  # 操作するツリー
            seg_s[target_tree].update(target, 0)
            # 次に、変換後の文字の利用回数。元々の値に1を加算。
            target_tree = alpha2int(query[2])
            seg_s[target_tree].update(target, 1)
            # 文字列リストを置換しておく。(同じ位置の文字を再度書き換えるとき、s_list[添え字]で対象の文字を取得するため)
            s_list[target] = query[2]
        else:
            # 文字の種類を出力
            ans = 0
            # 各アルファベットに対して、以下の処理を実施。
            for i in range(26):
                # 先頭～対象範囲(from)の直前までに、文字が何個使用されているか取得。
                from_int = int(query[1])
                remove_cnt = 0
                if from_int > 1:
                    remove_cnt = seg_s[i].query(0, from_int - 1)
                # 先頭～対象範囲(to)のまでに、文字が何個使用されているか取得。
                to_int = int(query[2])
                all_cnt = seg_s[i].query(0, to_int)
                if all_cnt - remove_cnt > 0:
                    ans += 1
            print(ans)


# テストクラス
class TestClass(unittest.TestCase):
    def assertIO(self, assert_input, output):
        stdout, sat_in = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(assert_input)
        resolve(sys._getframe().f_back.f_code.co_name)
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, sat_in
        self.assertEqual(out, output)

    def test_input_1(self):
        test_input = """7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7"""
        output = """3
1
5"""
        self.assertIO(test_input, output)

    def test_input_2(self):
        test_input = """4
abcd
4
2 1 4
2 1 1
1 1 b
2 1 2
"""
        output = """4
1
1"""
        self.assertIO(test_input, output)

    def test_input_3(self):
        test_input = """4
abab
10
2 1 1
2 1 2
2 1 3
2 1 4
2 2 2
2 2 3
2 2 4
2 3 3
2 3 4
2 4 4
"""
        output = """1
2
2
2
1
2
2
1
2
1"""
        self.assertIO(test_input, output)

    def test_input_5(self):
        test_input = """78
xcajtlueygwtjfreordfpsmyvirremdzhsfisulnbmmkxkdrrkwtjhsfmltkoieuxtwnvvozgcoabm
16
1 25 e
1 32 m
1 36 f
1 38 r
1 40 w
1 40 e
1 46 o
1 49 l
1 53 e
1 57 t
1 58 j
1 64 z
1 70 a
1 73 t
1 74 j
2 27 78
"""
        output = """20"""
        self.assertIO(test_input, output)

    def test_input_6(self):
        test_input = """78
xcajtlueygwtjfreordfpsmyvirremdzhsfisulnbmmkxkdrrkwtjhsfmltkoieuxtwnvvozgcoabm
21
1 73 t
1 53 e
1 7 t
1 70 a
1 38 r
1 15 p
1 57 t
1 58 j
1 74 j
1 8 x
1 46 o
1 25 e
1 40 w
1 49 l
1 36 f
1 15 w
1 32 m
1 1 k
1 40 e
1 64 z
2 9 19
"""
        output = """10"""
        self.assertIO(test_input, output)

    # 自作テストパターンのひな形(利用時は「tes_t」のアンダーバーを削除すること
    def tes_t_1original_1(self):
        test_input = """データ"""
        output = """データ"""
        self.assertIO(test_input, output)


# 実装orテストの呼び出し
if __name__ == "__main__":

    if os.environ.get("USERNAME") is None:
        # AtCoder提出時の場合
        resolve()

    else:
        # 自PCの場合
        unittest.main()

Submission status: Accepted

Solution code:
#A1 ~ Aiまでの和 O(logN)
def BIT_query(BIT,idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

#Ai += x O(logN)
def BIT_update(BIT,idx,x):
    while idx <= n:
        BIT[idx] += x
        idx += idx&(-idx)
    return


alps = 'abcdefghijklmnopqrstuvwxyz'

n = int(input())
s = list(input())
char_hd_d = {}
for alp in alps:
    char_hd_d[alp] = [0]*(n+1)

for i, si in enumerate(s):
    BIT_update(char_hd_d[si], i+1, 1)

q = int(input())
ansl = []
for _ in range(q):
    command, a, b = input().split()
    if command == '1':
        i = int(a)
        c = b
        i_char = s[i-1]
        BIT_update(char_hd_d[i_char], i, -1)
        BIT_update(char_hd_d[c], i, 1)
        s[i-1] = c 
    else:
        l,r = int(a),int(b)
        cnt = 0
        for alp in alps:
            if BIT_query(char_hd_d[alp], r) - BIT_query(char_hd_d[alp], l-1) > 0:
                cnt += 1
        ansl.append(cnt)

for a in ansl:
    print(a)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

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

N = int(input())
S = list(input()[:-1])
bits = [BIT(N) for _ in range(26)]

for i in range(N):
    j = ord(S[i])-ord('a')
    bits[j].add(i, 1)

Q = int(input())

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

Submission status: Accepted

Solution code:
from collections import defaultdict
from bisect import bisect_left, insort_left
import sys
input = sys.stdin.readline
N = int(input())
S = list(input())

dic = defaultdict(list)
for i, s in enumerate(S):
    dic[s].append(i)

Q = int(input())
for _ in [0]*Q:
    t, *q = input().split()
    if t == '1':
        i, c = q
        i = int(i)-1

        s = S[i]
        if s == c:
            continue
        S[i] = c
        dic[s].pop(bisect_left(dic[s], i))
        insort_left(dic[c], i)

    else:
        l, r = map(int, q)
        l -= 1
        r -= 1
        cnt = 0
        for L in dic.values():
            i = bisect_left(L, l)
            if i != len(L) and L[i] <= r:
                cnt += 1
        print(cnt)

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict, deque, Counter
import math
 
# import copy
from bisect import bisect_left, bisect_right
# import heapq
 
# sys.setrecursionlimit(1000000)
 
# input aliases
input = sys.stdin.readline
 
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]
 
INF = 10 ** 20
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

class Segtree_op():
     # 単位元及び操作を設定して使うこと
     # queryでは、区間の(l, r)を指定する ex: (0, 5) => [0, 1, 2, 3, 4]
     # 特定の1点は (i, i+1)
     def __init__(self, n):
         self.size = 1
         while(n >= 1):
             self.size = self.size << 1
             n = n//2
 
         self.arr = [self.unit() for i in range(self.size*2)]
 
     def op(self, lch, rch):
         # update min with holding index
         return max(rch, lch)
     def unit(self):
         return 0
 
     def update(self, k, val):
         k += self.size - 1
         self.arr[k] = val
         while(k):
             k = (k - 1) // 2
             self.arr[k] = self.op(self.arr[k*2 + 1], self.arr[k*2 + 2])
 
     def query(self, l, r):
         L = l + self.size
         R = r + self.size
         s = self.unit()
         while L < R:
             if R & 1:
                 R -= 1
                 s = self.op(s, self.arr[R - 1])
 
             if L & 1:
                 s = self.op(s, self.arr[L - 1])
                 L += 1
             L >>= 1
             R >>= 1
         return s
 
 
     def show(self):
         idx = 1
         while(idx <= self.size):
             print(self.arr[idx - 1:idx * 2 - 1])
             idx *= 2
 

def getind(c):
    return ord(c) - ord("a")

def main():
    N = getN()
    S = list(getS())
    Q = getN()
    segs = [Segtree_op(N) for i in range(26)]
    for i, c in enumerate(S):
        segs[getind(c)].update(i, 1)

    for _ in range(Q):
        query = getS().split()
        if query[0] == "1":
            k, i, c = query
            i = int(i) - 1
            segs[getind(S[i])].update(i, 0)
            segs[getind(c)].update(i, 1)
            S[i] = c
        else:
            k, l, r = list(map(int, query))
            ans = 0
            for se in segs:
                if se.query(l-1, r) == 1:
                    ans += 1

            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#import sys
#import numpy as np
import math
#from fractions import Fraction
import itertools
from collections import deque
from collections import Counter
#import heapq
#from fractions  import gcd
#input=sys.stdin.readline
import bisect
n=int(input())
s=input()
q=int(input())

inf = set()
num_min =2**(n-1).bit_length()
dat=[inf]*(2*num_min-1)

#初期化
for i in range(n):
    dat[i+num_min-1]=set(s[i])
for i in range(num_min-2,-1,-1):
    dat[i]=dat[2*i+1].union(dat[2*i+2])

#親のノード(n-1)//2
#子のノード2n+1,2n+2

def segfunc(x,y):
    return x.union(y)

def update(i,x):
    i+=num_min-1
    dat[i]=x
    while i>0:
        i=(i-1)//2
        dat[i]=segfunc(dat[2*i+1],dat[2*i+2])
def query(a,b): #半開区間、[a,b)の最小値
    if b<=a:
        return inf
    res=inf
    a += num_min-1
    b += num_min-2
    while b-a>1:
        if a&1==0:
            res = segfunc(res,dat[a])
        if b&1==1:
            res = segfunc(res,dat[b])
            b-=1
        a=a//2
        b=(b-1)//2
    if a==b:
        res = segfunc(res,dat[a])
    else:
        res=segfunc(segfunc(res,dat[a]),dat[b])
    return res

for i in range(q):
  t,l,r=input().split()
  if t=="1":
    update(int(l)-1,set(r))
  else:
    ans=query(int(l)-1,int(r))
    print(len(ans))