Problem:


Score : 500 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters.

Process Q queries of the following two types:

Type 1: change the i_q-th character of S to c_q. (Do nothing if the i_q-th character is already c_q.)

Type 2: answer the number of different characters occurring in the substring of S between the l_q-th and r_q-th characters (inclusive).

Constraints

N, Q, i_q, l_q, and r_q are integers.

S is a string consisting of lowercase English letters.

c_q is a lowercase English letter.

1 \leq N \leq 500000

1 \leq Q \leq 20000

|S| = N

1 \leq i_q \leq N

1 \leq l_q \leq r_q \leq N

There is at least one query of type 2 in each testcase.

Input

Input is given from Standard Input in the following format:

N
S
Q
Query_1
\vdots
Query_Q

Here, Query_i in the 4-th through (Q+3)-th lines is one of the following:

1 i_q c_q

2 l_q r_q

Output

For each query of type 2, print a line containing the answer.

Sample Input 1

7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7

Sample Output 1

3
1
5

In the first query, cdbb contains three kinds of letters: b , c , and d, so we print 3.

In the second query, S is modified to abcdzbd.

In the third query, a contains one kind of letter: a, so we print 1.

In the fourth query, S is modified to abcazbd.

In the fifth query, S does not change and is still abcazbd.

In the sixth query, abcazbd contains five kinds of letters: a, b, c, d, and z, so we print 5.



Sample input:
7
abcdbbd
6
2 3 6
1 5 z
2 1 1
1 4 a
1 7 d
2 1 7


Sample output:
3
1
5

Submission status: Wrong Answer

Solution code:
import 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 = 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)
        else:
            # 文字の種類を出力
            ans = 0
            # 各アルファベットに対して、以下の処理を実施。
            for i in range(26):
                to_int = int(query[2])
                from_int = int(query[1])
                # 対象範囲(末尾)の時点で、文字が何個使用されているか。
                all_cnt = seg_s[i].query(0, to_int)
                # 対象範囲(先頭)の直前で、文字が何個使用されているか。
                if from_int > 1:
                    remove_cnt = seg_s[i].query(0, from_int - 1)
                else:
                    remove_cnt = 0
                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)

    # 自作テストパターンのひな形(利用時は「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: Wrong Answer

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

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


class SegTree:
    """
    【セグメントツリー利用方法】
    　　１：segfuncに「区間に対して行いたい操作」を入力
    　　　　例：最小値を求めるなら「return min(x, y)」
    　　２：ide_eleに単位元を設定。(=初期化に使います。演算に影響を与えないものです。)
    　　　　例：最小値を求めるなら無限大を設定します。
    【関数の概要】
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        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):
        """
        「l」番目(0始まり)から「R」番目(1始まり) の区間の値を得る。
        例
        　query(0,1) -> 0番目から0番目(1-1=0)の区間の値を得る。
        　query(2,4) -> 2番目から3番目(4-1=3)の区間の値を得る。
        """
        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

    # 区間の最小値を保持する場合
    # 定義と利用例
    seg = SegTree([1, 2, 3, 4, 5], segfunc=min, ide_ele=float('inf'))
    # seg.query(0, 1) = {int}1     <-添字[0] ～添字[0](1-1=0)　の値を検索。
    # seg.query(1, 2) = {int}2     <-添字[1] ～添字[1](2-1=1)　の値を検索。
    # seg.query(2, 4) = {int}3     <-添字[2] ～添字[3](4-3=0)　の値を検索。
    # seg.query(0, 0) = {float}inf <- fromとtoが等しいなら正しく動かない。
    # seg.query(2, 6) = {int}3
    # seg.query(6, 8) = {float}inf <- ツリーの範囲外に探索をかけると初期値が帰ってくる(まあ、当然か)

    # 区間の最大値を保持する場合
    # 定義と利用例
    seg = SegTree([1, 2, 3, 4, 5], segfunc=max, ide_ele=-999)

    # seg.query(0, 1) = {int}1   <-添字[0] ～添字[0](1-1=0)　の値を検索。
    # seg.query(1, 2) = {int}2   <-添字[1] ～添字[1](2-1=1)　の値を検索。
    # seg.query(2, 4) = {int}4   <-添字[2] ～添字[3](4-3=0)　の値を検索。
    # seg.query(0, 0) = {int}999 <- fromとtoが等しいなら正しく動かない。
    # seg.query(2, 6) = {int}5
    # seg.query(6, 8) = {int}999 <- ツリーの範囲外に探索をかけると初期値が帰ってくる(まあ、当然か)

    # 独自の処理を乗せる場合、こんな感じで関数をインジェクションする。
    # def segfunc(x, y):
    #     return sum(x, y)<=これはエラーになる。
    #     return x + y    <=こうする。
    # seg = SegTree([1,2,3], segfunc=segfunc, ide_ele=0)
    # ※注意点：ide_eleの値は注意する。例えば累積和を求めるのにide_eleを-1にすると、-1減算されまくってまともな値にならない。

    # その他、区間積、区間和、最大公約数の設定は以下を参照する。
    # https://qiita.com/takayg1/items/c811bd07c21923d7ec69#%E3%81%9D%E3%81%AE%E4%BB%96%E3%81%AE%E6%93%8D%E4%BD%9C%E6%9C%80%E5%B0%8F%E5%80%A4%E4%BB%A5%E5%A4%96

    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 = s
    for query in query_s:
        if query[0] == "1":
            # 文字を変換
            target = int(query[1]) - 1  # 変換される文字の添え字
            # まず、変換される文字の利用回数を-1
            target_tree = alpha2int(s_list[target])  # 操作するツリー
            # 元々の値から-1減算。
            seg_s[target_tree].update(target, seg_s[target_tree].query(target, target + 1) - 1)
            # 次に、変換後の文字の利用回数を+1
            target_tree = alpha2int(query[2])
            # 元々の値に1を加算。
            seg_s[target_tree].update(target, seg_s[target_tree].query(target, target + 1) + 1)

        else:
            # 文字の種類を出力
            ans = 0
            # 各アルファベットに対して、以下の処理を実施。
            for i in range(26):
                to_int = int(query[2])
                from_int = int(query[1])
                # 対象範囲(末尾)の時点で、文字が何個使用されているか。
                all_cnt = seg_s[i].query(0, to_int)
                # 対象範囲(先頭)の直前で、文字が何個使用されているか。
                if from_int > 1:
                    remove_cnt = seg_s[i].query(0, from_int - 1)
                else:
                    remove_cnt = 0
                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
7
2 1 1
2 1 2
2 1 3
2 1 4
2 2 2
2 2 3
2 2 4
"""
        output = """1
2
2
2
1
2
2
"""
        self.assertIO(test_input, output)

    def test_input_4(self):
        test_input = """4
abab
1
2 2 3
"""
        output = """2"""
        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: Wrong Answer

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


class SegTree:
    """
    【セグメントツリー利用方法】
    　　１：segfuncに「区間に対して行いたい操作」を入力
    　　　　例：最小値を求めるなら「return min(x, y)」
    　　２：ide_eleに単位元を設定。(=初期化に使います。演算に影響を与えないものです。)
    　　　　例：最小値を求めるなら無限大を設定します。
    【関数の概要】
    init(init_val, ide_ele): 配列init_valで初期化 O(N)
    update(k, x): k番目の値をxに更新 O(logN)
    query(l, r): 区間[l, r)をsegfuncしたものを返す O(logN)
    """

    def __init__(self, init_val, segfunc, ide_ele):
        """
        init_val: 配列の初期値
        segfunc: 区間にしたい操作
        ide_ele: 単位元
        n: 要素数
        num: n以上の最小の2のべき乗
        tree: セグメント木(1-index)
        """
        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):
        """
        「l」番目(0始まり)から「R」番目(1始まり) の区間の値を得る。
        例
        　query(0,1) -> 0番目から0番目(1-1=0)の区間の値を得る。
        　query(2,4) -> 2番目から3番目(4-1=3)の区間の値を得る。
        """
        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

    # 区間の最小値を保持する場合
    # 定義と利用例
    seg = SegTree([1, 2, 3, 4, 5], segfunc=min, ide_ele=float('inf'))
    # seg.query(0, 1) = {int}1     <-添字[0] ～添字[0](1-1=0)　の値を検索。
    # seg.query(1, 2) = {int}2     <-添字[1] ～添字[1](2-1=1)　の値を検索。
    # seg.query(2, 4) = {int}3     <-添字[2] ～添字[3](4-3=0)　の値を検索。
    # seg.query(0, 0) = {float}inf <- fromとtoが等しいなら正しく動かない。
    # seg.query(2, 6) = {int}3
    # seg.query(6, 8) = {float}inf <- ツリーの範囲外に探索をかけると初期値が帰ってくる(まあ、当然か)

    # 区間の最大値を保持する場合
    # 定義と利用例
    seg = SegTree([1, 2, 3, 4, 5], segfunc=max, ide_ele=-999)

    # seg.query(0, 1) = {int}1   <-添字[0] ～添字[0](1-1=0)　の値を検索。
    # seg.query(1, 2) = {int}2   <-添字[1] ～添字[1](2-1=1)　の値を検索。
    # seg.query(2, 4) = {int}4   <-添字[2] ～添字[3](4-3=0)　の値を検索。
    # seg.query(0, 0) = {int}999 <- fromとtoが等しいなら正しく動かない。
    # seg.query(2, 6) = {int}5
    # seg.query(6, 8) = {int}999 <- ツリーの範囲外に探索をかけると初期値が帰ってくる(まあ、当然か)

    # 独自の処理を乗せる場合、こんな感じで関数をインジェクションする。
    # def segfunc(x, y):
    #     return sum(x, y)<=これはエラーになる。
    #     return x + y    <=こうする。
    # seg = SegTree([1,2,3], segfunc=segfunc, ide_ele=0)
    # ※注意点：ide_eleの値は注意する。例えば累積和を求めるのにide_eleを-1にすると、-1減算されまくってまともな値にならない。

    # その他、区間積、区間和、最大公約数の設定は以下を参照する。
    # https://qiita.com/takayg1/items/c811bd07c21923d7ec69#%E3%81%9D%E3%81%AE%E4%BB%96%E3%81%AE%E6%93%8D%E4%BD%9C%E6%9C%80%E5%B0%8F%E5%80%A4%E4%BB%A5%E5%A4%96

    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 = s
    for query in query_s:
        if query[0] == "1":
            # 文字を変換
            target = int(query[1]) - 1  # 変換される文字の添え字
            # まず、変換される文字の利用回数を-1
            target_tree = alpha2int(s_list[target])  # 操作するツリー
            # 元々の値から-1減算。
            seg_s[target_tree].update(target, seg_s[target_tree].query(target, target + 1) - 1)
            # 次に、変換後の文字の利用回数を+1
            target_tree = alpha2int(query[2])
            # 元々の値に1を加算。
            seg_s[target_tree].update(target, seg_s[target_tree].query(target, target + 1) + 1)

        else:
            # 文字の種類を出力
            ans = 0
            # 各アルファベットに対して、以下の処理を実施。
            for i in range(26):
                to_int = int(query[2])
                from_int = int(query[1])
                # 対象範囲(末尾)の時点で、文字が何個使用されているか。
                all_cnt = seg_s[i].query(from_int - 1, to_int)
                # 対象範囲(先頭)の直前で、文字が何個使用されているか。
                if from_int > 1:
                    remove_cnt = seg_s[i].query(from_int - 2, from_int - 1)
                else:
                    remove_cnt = 0
                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)

    # 自作テストパターンのひな形(利用時は「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: Wrong Answer

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

dic = defaultdict(set)
for i, s in enumerate(S):
    dic[s].add(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].remove(i)
        dic[c].add(i)

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

Submission status: Wrong Answer

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

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

res=0
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))

Submission status: Wrong Answer

Solution code:
import bisect
n = int(input())
s = list(input())
C = [[] for i in range(26)]
lis = [0]*n
for i,x in enumerate(s):
    C[ord(x)-97].append(i+1)
    lis[i] = ord(x)-97
q = int(input())
for i in range(q):
    #print(C)
    s,P,R = map(str,input().split())
    #print(s,P,R)
    if int(s) == 1:
        P = int(P)
        a = bisect.bisect(C[lis[P-1]], P)
        del C[lis[P-1]][a-1]
        lis[P-1] = ord(R)-97
        
        b = bisect.bisect(C[ord(R)-97], P)
        C[ord(R)-97].insert(b, int(P))
        #print(b)
    else:
        P = int(P)
        R = int(R)
        ans = 0
        for j in range(26):
            if len(C[j]) >= 1:
                c = bisect.bisect_left(C[j], R)
                #print(j,c)
                if P <= C[j][c-1] <= R:
                    ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
class SegT():
    def __init__(self, size):
        self.size = 1
        while self.size < size: self.size *= 2
        self.data = [set() for _ in range(self.size * 2 - 1)] 
    
    def update(self, i, x):
        i += (self.size - 1)
        self.data[i].add(x)
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]
        
    def get(self, a, b, node=0, l=0, r=-1):
        if r < 0: r = self.size
        if r <= a or b <= l: return set()
        if a <= l and r <= b: return self.data[node]
        vl = self.get(a, b, node*2+1, l, (l+r)//2)
        vr = self.get(a, b, node*2+2, (l+r)//2, r)
        return vl | vr

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

segt = SegT(N)
for i in range(N):
    segt.update(i, S[i])

for i in range(Q):
    t, l, r = input().split()
    if t == "1":
        segt.update(int(l)-1, r)
    else:
        x = segt.get(int(l)-1,int(r))
        print(len(x))

Submission status: Wrong Answer

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

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()


def II(): return int(input())


def MI(): return map(int,input().split())


def MF(): return map(float,input().split())


def LI(): return list(map(int,input().split()))


def LF(): return list(map(float,input().split()))


def TI(): return tuple(map(int,input().split()))

# rstrip().decode('utf-8')

class BinaryIndexedTree:
	def __init__(self,n,default=0):
		self.s=[default]*(n+1)
		self.n=n
	
	def add(self,val,idx):
		while idx<self.n+1:
			self.s[idx]=self.s[idx]+val
			idx+=idx&(-idx)
		return
	
	def get(self,idx):
		res=0
		while idx>0:
			res=res+self.s[idx]
			idx-=idx&(-idx)
		return res

from collections import defaultdict

def main():
	n=II()
	s=input()
	S=[0]+list(s)
	
	d=defaultdict(lambda:BinaryIndexedTree(n))
	
	for i,si in enumerate(s):
		#print(i,si)
		d[si].add(1,i+1)
	
	q=II()
	for _ in range(q):
		f,a,b=input().split()
		if int(f)==1:
			a=int(a)
			d[S[a]].add(0,a)
			d[b].add(1,a)
			S[a]=b
		else:
			#print(S,a,b)
			a=int(a)
			b=int(b)
			cnt=0
			for bit in d.values():
				if bit.get(b)-bit.get(a-1)>0:
					cnt+=1
			print(cnt)
		
	

if __name__=="__main__":
	main()

Submission status: Wrong Answer

Solution code:

import operator
class SegmentTree:
    def __init__(self, size, fn=operator.add, default=None, initial_values=None):
        """
        :param int size:
        :param callable fn: 区間に適用する関数。引数を 2 つ取る。min, max, operator.xor など
        :param default:
        :param list initial_values:
        """
        default = default or 0

        # size 以上である最小の 2 冪を size とする
        n = 1
        while n < size:
            n *= 2
        self._size = n
        self._fn = fn

        self._tree = [default] * (self._size * 2 - 1)
        if initial_values:
            i = self._size - 1
            for v in initial_values:
                self._tree[i] = v
                i += 1
            i = self._size - 2
            while i >= 0:
                self._tree[i] = self._fn(self._tree[i * 2 + 1], self._tree[i * 2 + 2])
                i -= 1

    def set(self, i, value):
        """
        i 番目に value を設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self._tree[x] = value

        while x > 0:
            x = (x - 1) // 2
            self._tree[x] = self._fn(self._tree[x * 2 + 1], self._tree[x * 2 + 2])

    def add(self, i, value):
        """
        もとの i 番目と value に fn を適用したものを i 番目に設定
        :param int i:
        :param value:
        :return:
        """
        x = self._size - 1 + i
        self.set(i, self._fn(self._tree[x], value))

    def get(self, from_i, to_i=None, k=0, L=None, r=None):
        """
        [from_i, to_i) に fn を適用した結果を返す
        :param int from_i:
        :param int to_i:
        :param int k: self._tree[k] が、[L, r) に fn を適用した結果を持つ
        :param int L:
        :param int r:
        :return:
        """
        if to_i is None:
            return self._tree[self._size - 1 + from_i]

        L = 0 if L is None else L
        r = self._size if r is None else r

        if from_i <= L and r <= to_i:
            return self._tree[k]

        if to_i <= L or r <= from_i:
            return None

        ret_L = self.get(from_i, to_i, k * 2 + 1, L, (L + r) // 2)
        ret_r = self.get(from_i, to_i, k * 2 + 2, (L + r) // 2, r)
        if ret_L is None:
            return ret_r
        if ret_r is None:
            return ret_L
        return self._fn(ret_L, ret_r)

    def __len__(self):
        return self._size

def resolve():
    N = int(input())
    S = input()
    L = [-1] * N
    for i in range(N):
        L[i] = 2 ** (ord(S[i]) - ord('a'))
    Q = int(input())

    seg = SegmentTree(N, fn=operator.or_, initial_values=L)
    for _ in range(Q):
        act, q1, q2 = input().split()
        if act == "1":
            # 文字変更
            idx = int(q1) - 1
            s_bin = 1 << (ord(q2) - ord('a'))
            seg.add(idx, s_bin)
        else:
            # L,R区間の文字種を出力
            l = int(q1)-1
            r = int(q2)
            x = bin(seg.get(l, r))
            print(x.count("1"))


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
slst=[s for s in S]
Q=int(input())

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    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
 
bits=[Bit(N) for _ in range(26)]

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

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

    if t=='1':
        a=int(a)
        pos=a-1
        nextc=ord(b)-ord('a')
        beforec=ord(slst[pos])-ord('a')

        if nextc!=beforec:
            bits[beforec].add(a,-1)
            bits[nextc].add(a,1)
    else:
        l=int(a)
        r=int(b)

        cnt=[0]*26

        for i in range(26):
            cnt[i]+=bits[i].sum(r)
        
        if l-1>0:
            for i in range(26):
                cnt[i]-=bits[i].sum(l-1)
        
        ans=0

        for i in range(26):
            if cnt[i]>0:
                ans+=1
        
        print(ans)