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
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
import bisect

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()


class Node:
    def __init__(self, x):
        self.data = x
        self.priority = random.random()
        self.left = None
        self.right = None


def rotate_right(node):
    l_node = node.left
    node.left = l_node.right
    l_node.right = node
    return l_node


def rotate_left(node):
    r_node = node.right
    node.right = r_node.left
    r_node.left = node
    return r_node


def search_min(node):
    while node.left is not None:
        node = node.left
    return node.data


def traverse_(node):
    if node is not None:
        for x in traverse_(node.left):
            yield x
        yield node.data
        for x in traverse_(node.right):
            yield x


class Treap:
    """
    動的ランダム二分探索木の中の一つ。構築:O(nlogn), 他の操作:期待値O(logn)
    """

    def __init__(self):
        self.root = None

    def search(self, x):
        def search_(node, x):
            while node is not None:
                if x == node.data:
                    return True
                elif x < node.data:
                    node = node.left
                else:
                    node = node.right
            return False

        return search_(self.root, x)

    def insert(self, x):
        def insert_(node, x):
            if node is None:
                return Node(x)
            elif x == node.data:
                return node
            elif x < node.data:
                node.left = insert_(node.left, x)
                if node.priority > node.left.priority:
                    node = rotate_right(node)
            else:
                node.right = insert_(node.right, x)
                if node.priority > node.right.priority:
                    node = rotate_left(node)
            return node

        self.root = insert_(self.root, x)

    def delete(self, x):
        def delete_(node, x):
            if node is not None:
                if x == node.data:
                    if node.left is None:
                        return node.right
                    elif node.right is None:
                        return node.left
                    else:
                        node.data = search_min(node.right)
                        node.right = delete_(node.right, node.data)
                elif x < node.data:
                    node.left = delete_(node.left, x)
                else:
                    node.right = delete_(node.right, x)
            return node

        self.root = delete_(self.root, x)

    def traverse(self):

        for x in traverse_(self.root):
            yield x

    def lower_bound(self, x):
        def lower_bound_(node, x):
            while node is not None:
                if node.right and node.left:
                    if node.right.data < x:
                        return lower_bound_(node.right, x)
                    elif node.data < x:
                        return min(node.right.data, lower_bound_(node.right, x))
                    else:
                        return min(node.data, lower_bound_(node.left, x))
                elif node.right:
                    if node.right.data < x:
                        return lower_bound_(node.right, x)
                    elif node.data < x:
                        return min(node.right.data, lower_bound_(node.right, x))
                    else:
                        return node.data  # 怪しい！！
                elif node.left:
                    if node.data < x:
                        return INF
                    elif node.left.data < x:
                        return min(node.data, lower_bound_(node.left, x))
                    else:
                        return lower_bound_(node.left, x)
                elif x <= node.data:
                    return node.data
                else:
                    return INF

        return lower_bound_(self.root, x)

    def upper_bound(self, x):
        def upper_bound_(node, x):
            while node is not None:
                if node.right and node.left:
                    if node.left.data > x:
                        return upper_bound_(node.left, x)
                    elif node.data > x:
                        return max(node.left.data, upper_bound_(node.left, x))
                    else:
                        return max(node.data, upper_bound_(node.right, x))
                elif node.left:
                    if node.left.data > x:
                        return upper_bound_(node.left, x)
                    elif node.data > x:
                        return max(node.left.data, upper_bound_(node.left, x))
                    else:
                        return node.data  # 怪しい！！
                elif node.right:
                    if node.data > x:
                        return 0
                    elif node.right.data > x:
                        return max(node.data, upper_bound_(node.right, x))
                    else:
                        return upper_bound_(node.right, x)
                elif x >= node.data:
                    return node.data
                else:
                    return 0

        return upper_bound_(self.root, x)

    def __str__(self):
        if self.root is None:
            return "Treap()"
        buff = "Treap("
        for x in traverse_(self.root):
            buff += "%s, " % x
        buff = buff.rstrip(", ")
        buff += ")"
        return buff


N = int(input())
S = input()
Q = int(input())
strings = [Treap() for _ in range(26)]
alphabets = string.ascii_lowercase
check = {}
for i in range(26):
    check[alphabets[i]] = i
for i in range(N):
    strings[check[S[i]]].insert(i)
for i in range(26):
    strings[i].insert(INF)
for _ in range(Q):
    Query, a, b = map(str, input().split())
    if Query == "1":
        a = int(a)
        strings[check[S[a - 1]]].delete(a - 1)
        strings[check[b]].insert(a - 1)
    else:
        a, b = map(int, (a, b))
        ans = 0
        for i in range(26):
            if strings[i].lower_bound(a - 1) <= b - 1:
                ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc157/tasks/abc157_e
# セグメント木
# 各文字をビットに対応させる(セグ木を26本持っても良い)
import sys
read = sys.stdin.readline


def read_a_int():
    return int(read())


class SegmentTree:
    def __init__(self, ls: list, segfunc, identity_element):
        '''
        セグ木 (下書き)
        一次元のリストlsを受け取り初期化する。O(len(ls))
        区間のルールはsegfuncによって定義される
        identity elementは単位元。e.g., 最小値を求めたい→inf, 和→0, 積→1, gcd→0
        [単位元](https://ja.wikipedia.org/wiki/%E5%8D%98%E4%BD%8D%E5%85%83)
        '''
        self.ide = identity_element
        self.func = segfunc
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()  # n以上の最小の2のべき乗
        self.tree = [self.ide] * (2 * self.num - 1)  # −1はぴったりに作るためだけど気にしないでいい
        for i, l in enumerate(ls):  # 木の葉に代入
            self.tree[i + self.num - 1] = l
        for i in range(self.num - 2, -1, -1):  # 子を束ねて親を更新
            self.tree[i] = segfunc(self.tree[2 * i + 1], self.tree[2 * i + 2])

    def update(self, i, x):
        '''
        i番目の要素をxに変更する(木の中間ノードも更新する) O(logN)
        '''
        i += self.num - 1
        self.tree[i] = x
        while i:  # 木を更新
            i = (i - 1) // 2
            self.tree[i] = self.func(self.tree[i * 2 + 1],
                                     self.tree[i * 2 + 2])

    def query(self, l, r):
        '''
        区間[l,r)に対するクエリをO(logN)で処理する。例えばその区間の最小値、最大値、gcdなど
        '''
        if r <= l:
            return ValueError('invalid index (l,rがありえないよ)')
        l += self.num
        r += self.num
        res = self.ide
        while r - l > 1:  # 右から寄りながら結果を結合していくイメージ
            if l & 1:
                res = self.func(res, self.tree[l-1])
                l+=1
            if r & 1:
                r -= 1
                res = self.func(res, self.tree[r-1])
            l >>=1
            r >>=1
        return res


def segfunc(x, y):
    # 処理したい内容
    return x | y


def moji_to_bit(a):
    return 1 << (ord(a) - ord('a'))


def bit_to_sum(n):
    return sum([(n >> i) & 1 for i in range(n.bit_length())])


N = read_a_int()
S = read()[:-1]
S_bit = [moji_to_bit(s) for s in S]

# build segment tree
st = SegmentTree(S_bit, segfunc, 0)

Q = read_a_int()
for q in range(Q):
    com, a, b = read().split()
    if int(com) == 1:
        i, c = int(a) - 1, b
        st.update(i, moji_to_bit(c))
    else:
        l, r = int(a) - 1, int(b)
        print(bit_to_sum(st.query(l, r)))

Submission status: Wrong Answer

Solution code:
#!python3

import sys

iim = lambda: map(int, input().rstrip().split())

def popcnt2(n):
    a = (
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    )
    ans = 0
    while n:
        ans += a[n&0xff]
        n >>= 8
    return ans

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    ln = N.bit_length() + 1
    c0 = ord('a')
    smap = [1<<(i-c0) for i in range(c0, ord('z')+1)]

    T = [None] * ln

    T[0] = [smap[ord(S[i])-c0] for i in range(N)]
    if N&1:
        T[0].append(0)
        N += 1

    t0, n2 = T[0], N
    for i in range(1, ln):
        n1 = n2 = n2 >> 1
        if n2 & 1:
            n2 += 1
        ti = T[i] = [0] * n2
        for j in range(n1):
            j2 = j << 1
            d1, d2 = t0[j2], t0[j2+1]
            ti[j] = d1 | d2
        t0 = ti

    #for ti in T:
    #    print(len(ti), ti)
    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            S[i] = j

            t0 = T[0]
            t0[i] = smap[ord(j)-c0]
            for i1 in range(1, ln):
                ti = T[i1]
                j1 = i >> 1
                ti[j1] = t0[i] | t0[i^1]
                i, t0 = j1, ti

        elif cmd == "2":
            j = int(j) - 1

            d1 = 0
            for i1 in range(ln):
                ti = T[i1]
                if not i < j :
                    d1 |= ti[i]
                    break
                if i & 1:
                    d1 |= ti[i]
                    i += 1
                if j & 1 == 0:
                    d1 |= ti[j]
                    j -= 1

                i >>= 1; j >>=1

            ans.append(popcnt2(d1))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
#!python3

import sys

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    ln = N.bit_length() + 1

    T = [None] * ln
    empty = set()

    T[0] = [set(S[i]) for i in range(N)]
    if N&1:
        T[0].append(empty)
        N += 1

    t0, n2 = T[0], N
    for i in range(1, ln):
        n1 = n2 = n2 >> 1
        if n2 & 1:
            n2 += 1
        ti = T[i] = [empty] * n2
        for j in range(n1):
            j2 = j << 1
            d1, d2 = t0[j2], t0[j2+1]
            ti[j] = d1 | d2
        t0 = ti

    #for ti in T:
    #    print(len(ti), ti)
    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            c0 = S[i]
            if c0 == j:
                continue

            S[i] = j

            t0 = T[0]
            t0[i] = set(j)
            for i1 in range(1, ln):
                ti = T[i1]
                j1 = i >> 1
                ti[j1] = t0[i] | t0[i^1]
                i, t0 = j1, ti

        elif cmd == "2":
            j = int(j) - 1

            d1 = set()
            for i1 in range(ln):
                ti = T[i1]
                if not i < j :
                    d1 |= ti[i]
                    break
                if i & 1:
                    d1 |= ti[i]
                    i += 1
                if j & 1 == 0:
                    d1 |= ti[j]
                    j -= 1

                i >>= 1; j >>=1

            ans.append(len(d1))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val,j):
    #set_val
    for i in range(n):
        seg[j][i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[j][i]=segfunc(seg[j][2*i+1],seg[j][2*i+2]) 
    
def update(k,x,j):
    k += num-1
    seg[j][k] = x
    while k:
        k = (k-1)//2
        seg[j][k] = segfunc(seg[j][k*2+1],seg[j][k*2+2])
    
def query(p,q,j):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[j][p])
        if q&1 == 1:
            res = segfunc(res,seg[j][q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[j][p])
    else:
        res = segfunc(segfunc(res,seg[j][p]),seg[j][q])
    return res


n = int(input())
s = list(input())
q = int(input())
al = []
l = [[0 for i in range(n)] for i in range(26)]
for i in range(n):
    l[ord(s[i])-97][i] = 1
seg = [[] for i in range(26)]
for i in range(26):
#####単位元######
    ide_ele = 0
#num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg[i]=[ide_ele]*2*num
    init(l[i],i)
for i in range(q):
    q1 = list(input().split())
    if q1[0] == "1":
        p = int(q1[1])
        r = ord(q1[2]) - 97
        for j in range(26):
            if l[j][p-1] == 1 and j != r:
                update(p-1,0,j)
            elif j == r:
                update(p-1,1,j)
    else:
        a = int(q1[1])
        b = int(q1[2])
        #print(a,b,seg)
        aa = 0
        for j in range(26):
            if query(a-1,b,j) > 0:
                aa += 1
        al.append(aa)
for i in al:
    print(i)

Submission status: Wrong Answer

Solution code:
#!python3

import sys
from functools import reduce
from operator import or_
from collections import defaultdict

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    ln = N.bit_length() + 1

    T = [None] * ln

    T[0] = [defaultdict(int, ((S[i], 1),)) for i in range(N)]

    i =  2
    nn = N
    for i in range(1, ln):
        ti = T[i-1]
        tj = T[i] = [None] * ((nn+1)>>1)
        for j in range(0, nn-1, 2):
            d1, d2 = ti[j], ti[j+1]
            d3 = tj[j>>1] = d1.copy()
            for k,v in d2.items():
                d3[k] += v
        if nn & 1:
            tj[-1] = ti[-1].copy()
            nn += 1
        nn >>= 1

    #for ti in T:
    #    print(len(ti), ti)
    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            c0 = S[i]
            S[i] = j

            d1 = T[0][i]
            del d1[c0]
            d1[j] = 1

            for i1 in range(1, ln):
                i >>= 1
                d2 = T[i1][i]
                if d2[c0] == 1:
                    del d2[c0]
                else:
                    d2[c0] -= 1
                d2[j] += 1
        elif cmd == "2":
            j = int(j) - 1

            d1 = defaultdict(int)
            for i1 in range(ln):
                ti = T[i1]
                if not i < j :
                    d1.update(ti[i])
                    break
                if i & 1:
                    d1.update(ti[i])
                    i += 1
                if j & 1 == 0:
                    d1.update(ti[j])
                    j -= 1

                i >>= 1; j >>=1

            ans.append(len(d1))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
import unittest
import string


class TestE(unittest.TestCase):
    def test_1(self):
        self.assertEqual(
            think(
                'abcdbbd',
                [
                    ['2', '3', '6'],
                    ['1', '5', 'z'],
                    ['2', '1', '1'],
                    ['1', '4', 'a'],
                    ['1', '7', 'd'],
                    ['2', '1', '7']
                ]
            ),
            [3, 1, 5]
        )


def solve():
    s, queries = read()
    result = think(s, queries)
    write(result)


def read():
    n = read_int(1)[0]
    s = read_line(n=n)
    q = read_int(1)[0]
    queries = []
    for _ in range(q):
        queries.append(read_line().split(' ')[:3])
    return s, queries


def read_int(n):
    return read_type(int, n, sep=' ')


def read_float(n):
    return read_type(float, n, sep=' ')


def read_type(t, n, sep):
    return list(map(lambda x: t(x), read_line().split(sep)))[:n]


def read_line(n=0):
    if n == 0:
        return input().rstrip()
    else:
        return input().rstrip()[:n]


def think(s, queries):
    # print(s, queries)
    dict_of_index = prepare_dict_of_index()
    for i, e in enumerate(s):
        dict_of_index[e].append(i + 1)

    result = []
    for q in queries:
        kind = q[0]
        if kind == '1':
            i = int(q[1])
            c = q[2]
            for k in dict_of_index.keys():
                if i in dict_of_index[k]:
                    dict_of_index[k].remove(i)
                    break
            dict_of_index[c].append(i)
        elif kind == '2':
            left, right = int(q[1]), int(q[2])
            count = 0
            for k in dict_of_index.keys():
                dict_of_index[k].sort()
                if exist_elem_in_range(dict_of_index[k], left, right):
                    count += 1
            result.append(count)
    return result


def write(result):
    for r in result:
        print(r)


def prepare_dict_of_index():
    d = {}
    for c in string.ascii_lowercase:
        d[c] = []
    return d


def exist_elem_in_range(sequence, left, right):
    if not sequence:
        return False
    if right < sequence[0]:
        return False
    if sequence[-1] < left:
        return False
    if left <= sequence[0]:
        return True
    index_left = 0
    index_right = len(sequence) - 1
    while index_right - index_left > 1:
        index_mid = (index_left + index_right) // 2
        what = sequence[index_mid]
        if left <= what <= right:
            return True
        if left < what:
            index_left = index_mid
        else:
            index_right = index_mid
    return False


if __name__ == '__main__':
    # unittest.main()
    solve()

Submission status: Wrong Answer

Solution code:
from math import ceil, log
from operator import __or__

N = int(input())
S = list(input())
Q = int(input())
Query = [input().split() for _ in range(Q)]

abc = dict(zip("abcdefghijklmnopqrstuvwxyz", range(26)))


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.init_value = init_value
        self.aggfunc = aggfunc

        self.data = [init_value] * (2 ** (1 + ceil(log(length, 2))) - 1)
        self.origin = len(self.data) // 2

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self.origin + 1)

    def _query(self, start, stop, k, l, r):
        if (start <= l) & (r <= stop):
            return self.data[k]
        elif (r <= start) | (stop <= l):
            return self.init_value
        else:
            return self.aggfunc(
                self._query(start, stop, k * 2 + 1, l, (l + r) // 2),
                self._query(start, stop, k * 2 + 2, (l + r) // 2, r),
            )


segs = [SegmentTree(N, False, __or__) for _ in range(26)]
for i in range(N):
    letter = abc[S[i]]
    segs[letter].update(i, True)

for q1, q2, q3 in Query:
    if q1 == "1":
        ind = int(q2)
        letter = abc[S[i]]
        segs[letter].update(ind, False)
        letter = abc[q3]
        segs[letter].update(ind, True)
        S[i] = q3
    else:
        ans = sum(seg.query(int(q2) - 1, int(q3)) for seg in segs)
        print(ans)

Submission status: Wrong Answer

Solution code:
import math as ma

def conq(s):
    mid = ma.floor((len(s)+1)/2)
    if len(s) < 32:
        return set(s[0:len(s)-1])
    else:
        return conq(s[0:mid]) & conq(s[mid:len(s)-1])

n = int(input())
s = list(input())
q = int(input())

for i in range(q):
    t, i, c = input().split()
    if t == '1':
        s[int(i)-1] = c
    elif t == '2':
        l, r = int(i), int(c)
#         mid = ma.floor((r-l+1)/2)
#         s1 = list(set(s[l-1:mid]))
#         s2 = list(set(s[mid:r]))
        print(len(conq(s[l-1:r])))

Submission status: Wrong Answer

Solution code:
import math as ma
n = int(input())
s = list(input())
q = int(input())
s1, s2 = [], []

for i in range(q):
    t, i, c = input().split()
    if t == '1':
        s[int(i)-1] = c
    elif t == '2':
        l, r = int(i), int(c)
        mid = ma.floor((r-l+1)/2)
        s1 = list(set(s[l-1:mid]))
        s2 = list(set(s[mid:r]))
        print(len(set(s1+s2)))

Submission status: Wrong Answer

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def string_to_number(a):
    return 1 << (ord(a) - 97)

class SegmentTree:
    def __init__(self, A):
        self.n = 2**(len(A)-1).bit_length()
        self.identity = 0
        self.seg = [self.identity] * (2 * self.n)
        
        for i, a in enumerate(A):
            self.seg[self.n-1+i] = string_to_number(a)
        for i in range(self.n-2,-1,-1):
            self.seg[i] = self.seg[2*i+1] | self.seg[2*i+2]

            
    def update(self, k, a):
        k += self.n - 1
        self.seg[k] = string_to_number(a)
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.seg[k*2+1] | self.seg[k*2+2]

            
    def query(self, a, b):
        if b == a:
        	return 1
        a += self.n - 1
        b += self.n - 2
        res = self.identity
        while b - a > 1:
            if not a & 1:
                res |= self.seg[a]
            if b & 1:
                res |= self.seg[b]
                b -= 2
            a >>= 1
            b -= 1
            b >>= 1
        if a == b:
            res |= self.seg[a]
        else:
            res |= (self.seg[a] | self.seg[b])
        
        return bin(res).count("1")


def main():
    N = int(readline())
    s = readline().strip()
    seg = SegmentTree(list(s))
    print(seg.seg)

    Q = int(readline())
    q = map(str, read().split())
    for t, a, b in zip(*[iter(q)]*3):
        if t == "1":
            seg.update(int(a)-1, b)
        else:
            print(seg.query(int(a)-1, int(b)))


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
class SegmentTree(object):  # 1-indexed
    def __init__(self, size, S):
        self.len = 1 << size.bit_length()

        self.array = [0] * (2 * self.len)
        for i, s in enumerate(S):
            self.array[i + self.len] = 1 << (ord(s) - ord('a'))
        for i in range(self.len - 1, 0, -1):
            self.array[i] = self.array[i * 2] | self.array[i * 2 + 1]

    def query1(self, i, x):
        i += self.len
        self.array[i] = 1 << (ord(x) - ord('a'))
        i >>= 1
        while i > 0:
            self.array[i] = self.array[i * 2] | self.array[i * 2 + 1]
            i >>= 1

    def get(self, i):
        return self.array[i + self.len]

    def count_letter(self, l, r, i, a, b):
        if i > 100:
            exit()
        if l == a and r == b:
            return self.array[i]
        center = (a + b) // 2
        if center >= r:
            return self.count_letter(l, r, i * 2, a, center)
        elif center < l:
            return self.count_letter(l, r, i * 2 + 1, center + 1, b)
        else:
            left = self.count_letter(l, center, i * 2, a, center)
            right = self.count_letter(center + 1, r, i * 2 + 1, center + 1, b)
            return left | right

    def query2(self, l, r):
        ans = self.count_letter(l - 1, r - 1, 1, 0, self.len - 1)
        print(bin(ans).count('1'))


N = int(input())
S = input()
tree = SegmentTree(N, S)
Q = int(input())

for _ in range(Q):
    a, b, c = map(str, input().split())
    if a == "1":
        b = int(b)
        tree.query1(b, c)
    else:
        b = int(b)
        c = int(c)
        tree.query2(b, c)

Submission status: Wrong Answer

Solution code:
#1indexed
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

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

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i

n = int(input())
s = input()
q = int(input())

bit = [BIT(n) for i in range(26)]
for i in range(n):
    bit[ord(s[i])-97].add(i+1, 1)


s = list(s)
for _ in range(q):
    query, a, b = input().split()
    if query == "1":
        i = int(a)
        c = ord(b)-97
        if bit[c].bit[i] == 0:
            bit[c].add(i, 1)
            bit[ord(s[i-1])-97].add(i, -1)
            s[i-1] = chr(c+97)
    else:
        ans = 0
        for k in range(26):
            if bit[k].sum(int(b))-bit[k].sum(int(a)-1) >= 1:
                ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
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):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, 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):
        # 足し算と引き算にはaddを使うべき
        if not (0 <= key < self.size): raise IndexError("error!")
        self.add(key, value - self[key])

n = int(input())
s = input()
q = int(input())

bit = [Bit(n+1) for i in range(26)]
for i in range(n):
    bit[ord(s[i])-97].add(i+1, 1)
s = list(s)
for _ in range(q):
    query, i, c = input().split()
    if query == "1":
        i = int(i)
        c = ord(c)-97
        if bit[c].tree[i] == 0:
            bit[c].add(i, 1)
            bit[ord(s[i-1])-97].add(i, -1)
            s[i-1] = chr(c+97)
    else:
        ans = 0
        for k in range(26):
            if bit[k].sum(int(c)+1)-bit[k].sum(int(i)) >= 1:
                ans += 1
        print(ans)