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:
# 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 l<r:  # 右から寄りながら結果を結合していくイメージ
            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: Accepted

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

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

    T = [0]*N + [smap[ord(S[i])-c0] for i in range(N)]

    for i in range(N-1, 0, -1):
        i2 = i << 1
        T[i] = T[i2] | T[i2|1]

    ans = []
    #print(T)
    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
            i0 = N + i
            T[i0] = smap[ord(j)-c0]
            while i0 > 1:
                i0 = i0 >> 1
                T[i0] = T[i0+i0] | T[i0-~i0]
        elif cmd == "2":
            i += N
            j = int(j) + N

            d1 = 0
            while i < j:
                if i & 1:
                    d1 |= T[i]
                    i += 1
                if j & 1:
                    j -= 1
                    d1 |= T[j]

                i >>= 1; j >>=1

            ans.append(popcnt2(d1))

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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
            #for ti in T:
            #    print(len(ti), ti)
        elif cmd == "2":
            j = int(j) - 1

            d1 = 0
            for i1 in range(ln):
                ti = T[i1]
                if not i < j :
                    if 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: Accepted

Solution code:
class SegmentTree:
    def __init__(self, n, init_value, ide_ele):
        self.num = 2 ** (n - 1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [ide_ele] * 2 * self.num
        
        for i in range(n):
            self.seg[i + self.num - 1] = init_value[i]
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = self.segfunc(self.seg[2 * i + 1], self.seg[2 * i + 2])
    
    def update(self, _k, x):
        k = _k + self.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])
    
    def query(self, _p, _q):
        p = _p
        q = _q
        if q <= p:
            return self.ide_ele
        
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        while 1 < q - p:
            if p & 1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q & 1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p // 2
            q = (q - 1) // 2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res
    
    @staticmethod
    def segfunc(a, b):
        return a | b


def popcount(x):
    x = x - ((x >> 1) & 0x5555555555555555)
    
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    
    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f
    x = x + (x >> 8)
    x = x + (x >> 16)
    x = x + (x >> 32)
    return x & 0x0000007f


def solve():
    N = int(input())
    S = input()
    Q = int(input())
    
    init_val = [1 << ord(S[i]) - ord('a') for i in range(N)]
    seg_tree = SegmentTree(N, init_val, 0)
    
    for _ in range(Q):
        cmd, *query = input().split()
        cmd = int(cmd)
        if cmd == 1:
            i = int(query[0]) - 1
            c = query[1]
            seg_tree.update(i, 1 << ord(c) - ord('a'))
        else:
            l = int(query[0]) - 1
            r = int(query[1])
            kind = seg_tree.query(l, r)
            print(popcount(kind))


if __name__ == '__main__':
    solve()

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(100000000)
input = lambda: sys.stdin.readline().rstrip()


class Node:
    def __init__(self, begin, end):
        self.begin = begin
        self.end = end
        self.left = self.right = self.parent = None
        self.val = 0


class SegmentTree:
    INF = 2 ** 60

    def __init__(self, size):
        self.root = Node(0, size)
        self.leaves = [None] * size

        queue = deque()
        queue.append(self.root)

        while len(queue) > 0:
            node = queue.popleft()

            if node.end - node.begin == 1:
                self.leaves[node.begin] = node
            else:
                mid = (node.begin + node.end) // 2
                node.left = Node(node.begin, mid)
                node.right = Node(mid, node.end)
                node.left.parent = node.right.parent = node
                queue.append(node.left)
                queue.append(node.right)

    def update(self, index, val):
        node = self.leaves[index]
        node.val = val
        while node.parent is not None:
            node = node.parent
            node.val = node.left.val | node.right.val

    def val(self, begin, end, node=None):
        if node is None:
            return self.val(begin, end, self.root)
        if begin <= node.begin and node.end <= end:
            return node.val
        if node.end <= begin or end <= node.begin:
            return 0
        return self.val(begin, end, node.left) | self.val(begin, end, node.right)


N = int(input())
S = list(input())
Q = int(input())
tree = SegmentTree(N)
for i, c in enumerate(S):
    tree.update(i, 1 << (ord(c) - ord('a')))
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        i, c = query[1:]
        i = int(i) - 1
        tree.update(i, 1 << (ord(c) - ord('a')))
    else:
        l, r = map(int, query[1:])
        print(bin(tree.val(l - 1, r)).count('1'))

Submission status: Accepted

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:
                update(p-1,0,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: Accepted

Solution code:
#!python3

import sys

from bisect import bisect, insort_left

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

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

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

    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

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i)-1)
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

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

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:

N = int(input())
S = [x for x in input()]
Q = int(input())

#A1 ... AnのBIT(1-indexed)
BIT = [[0] * (N + 1) for _ in range(26)]

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

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

for i, c in enumerate(S):
    BIT_update(BIT[ord(c)-ord('a')], i+1, 1)
  
for _ in range(Q):
    a, b, c = input().rstrip().split()
    if int(a) == 1:
        BIT_update(BIT[ord(S[int(b)-1])-ord('a')], int(b), -1)
        BIT_update(BIT[ord(c)-ord('a')], int(b), 1)
        S[int(b)-1] = c
    else:
        count = 0
        for i in range(26):
            if BIT_query(BIT[i], int(b)-1) != BIT_query(BIT[i], int(c)):
                count += 1
        print(count)

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, a, func):
        self.n = 2**(len(a) - 1).bit_length()
        self.f = func
        self.d = [0] * (2 * self.n - 1)
        self.d[self.n - 1:self.n - 1 + len(a)] = a
        for i in reversed(range(self.n - 1)):
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def update(self, i, v):
        i += self.n - 1
        self.d[i] = v
        while i:
            i = (i - 1) // 2
            self.d[i] = self.f(self.d[2 * i + 1], self.d[2 * i + 2])

    def query(self, l, r):
        assert l <= r
        l += self.n
        r += self.n
        s = self.d[l - 1]
        while l < r:
            if l & 1:
                s = self.f(s, self.d[l - 1])
                l += 1
            if r & 1:
                r -= 1
                s = self.f(s, self.d[r - 1])
            l //= 2
            r //= 2
        return s

def main():
    N = int(input())
    S = [1 << (ord(s) - 97) for s in input()]
    T = SegTree(S, lambda x, y: x | y)

    Q = int(input())
    for _ in range(Q):
        t, a, b = input().split()
        if t == '1':
            T.update(int(a) - 1, 1 << (ord(b) - 97))
        else:
            print(bin(T.query(int(a) - 1, int(b))).count('1'))

main()

Submission status: Accepted

Solution code:
def main():
  import sys
  n,s,_,*t=sys.stdin.buffer.read().split()
  n=int(n)
  d=[0]*n+[1<<c-97for c in s]
  for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
  for q,a,b in zip(*[iter(t)]*3):
    i,s=int(a)+n-1,0
    if q<b'2':
      d[i]=1<<b[0]-97
      while i>1:
        i//=2
        d[i]=d[i+i]|d[i-~i]
      continue
    j=int(b)+n
    while i<j:
      if i&1:
        s|=d[i]
        i+=1
      if j&1:
        j-=1
        s|=d[j]
      i//=2
      j//=2
    print(bin(s).count('1'),flush=False)
main()

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, init_val, ide_ele, segfunc):
        self.n = len(init_val)
        self.num =2**(self.n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg = [self.ide_ele]*2*self.num
        self.segfunc = segfunc
        
        #set_val
        for i in range(self.n):
            self.seg[i+self.num-1] = init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = segfunc(self.seg[2*i+1], self.seg[2*i+2]) 
    
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res
    
import sys
input = sys.stdin.readline
N = int(input())
S = input()
L = [-1]*N
for i in range(N):
    L[i] = 2**(ord(S[i]) - ord('a'))
    
def segfunc(a,b):
    return a | b

Seg = SegTree(L,0,segfunc)

Q = int(input())

for _ in range(Q):
    q,a,b = input().split()
    if q == '1':
        i = int(a)-1
        c = 2**(ord(b) - ord('a'))
        Seg.update(i,c)
    elif q=='2':
        l = int(a)-1
        r = int(b)-1
        X = Seg.query(l,r+1)
        tmp = 0
        for j in range(30):
            if X%2==1:
                tmp += 1
            X//=2
        print(tmp)

Submission status: Accepted

Solution code:
import sys
from operator import or_
input=sys.stdin.readline


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


def main():
    N = int(input())
    S = list(input())[:-1]
    trees = {chr(97+i):SegTree(N, e=0, operator_func=or_) for i in range(26)}

    for i, s in enumerate(S):
        trees[s].update(i, 1)

    Q = int(input())
    for _ in range(Q):
        mode, i, v = input().split()
        if mode=="1":
            i = int(i)-1
            trees[S[i]].update(i, 0)
            trees[v].update(i, 1)
            S[i] = v
        else:
            i = int(i)-1
            v = int(v)
            ans = sum(trees[chr(97+j)].get(i, v) for j in range(26))
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from operator import or_
input=sys.stdin.readline


class SegTree():
    def __init__(self, N, e=float("inf"), operator_func=min):
        self.e = e
        self.size = N
        self.node = [self.e] * (2*N)
        self.op = operator_func

    def set_list(self, l):
        for i in range(self.size):
            self.node[i+self.size-1] = l[i]
        for i in range(self.size-1)[::-1]:
            self.node[i] = self.op(self.node[2*i+1], self.node[2*i+2])
    
    def update(self, k, x):
        k += self.size - 1
        self.node[k] = x
        while k >= 0:
            k = (k - 1) // 2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])

    def get(self, l, r):
        x = self.e
        l += self.size; r += self.size
        a, b = [], []

        while l<r:
            if l&1:
                a += [l-1]; l += 1
            if r&1:
                r -= 1; b += [r-1]
            l >>= 1; r >>= 1

        for i in a+(b[::-1]):
            x = self.op(x, self.node[i])
        return x


def main():
    N = int(input())
    S = list(input())[:-1]
    trees = {chr(97+i):SegTree(N, e=False, operator_func=or_) for i in range(26)}

    for i, s in enumerate(S):
        trees[s].update(i, True)

    Q = int(input())
    for _ in range(Q):
        mode, i, v = input().split()
        if mode=="1":
            i = int(i)-1
            trees[S[i]].update(i, False)
            trees[v].update(i, True)
            S[i] = v
        else:
            i = int(i)-1
            v = int(v)
            ans = 0
            for j in range(26):
                ans += trees[chr(97+j)].get(i, v)
            print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
 
def main():
    input = sys.stdin.readline
    N = int(input())
    S = input().rstrip()
    tree = SegmentTree(initial_values=S, f=lambda x,y:x|y, converter=lambda c: 1 << (ord(c)-ord('a')))
    Q = int(input())
    update = tree.update
    query = tree.query
    for _ in range(Q):
        t, a, b = input().rstrip().split()
        if t == '1': update(int(a)-1, b)
        else: print(bin(query(int(a)-1, int(b))).count('1'))    

class SegmentTree:
    def __init__(self, n=None, f=max, zero_factory=int, converter=lambda x:x, initial_values=None):
        assert(n or initial_values)
        self.__f, self.__z, self.__c = f, zero_factory, converter
        size = n if n else len(initial_values)
        self.__n = 1 << ((size - 1).bit_length())
        d = [zero_factory() for _ in range(2 * self.__n + 1)]
        self.__dat = d
        if initial_values:
            for i, v in enumerate(initial_values): d[self.__n + i] = converter(v)
            for i in range(self.__n - 1, 0, -1): d[i] = f(d[i<<1], d[i<<1|1])

    def update(self, index, value):
        i, v, d, f = index + self.__n, self.__c(value), self.__dat, self.__f
        if d[i] == v: return
        d[i] = v
        while i:
            i = i >> 1
            d[i] = f(d[i<<1], d[i<<1|1])

    def query(self, from_inclusive, to_exclusive):
        ans = self.__z()
        if to_exclusive <= from_inclusive: return ans
        l, r, d, f = from_inclusive + self.__n, to_exclusive + self.__n, self.__dat, self.__f
        while l < r:
            if l & 1: ans, l = f(ans, d[l]), l+1
            if r & 1: ans, r = f(ans, d[r-1]), r-1
            l, r = l >> 1, r >> 1
        return ans

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
 
def main():
    input = sys.stdin.readline
    N = int(input())
    S = input().rstrip()
    tree = SegmentTree(initial_values=S, f=lambda x,y:x|y, converter=lambda c: 1 << (ord(c)-ord('a')))
    Q = int(input())
    update = tree.update
    query = tree.query
    for _ in range(Q):
        t, a, b = input().rstrip().split()
        if t == '1': update(int(a)-1, b)
        else: print(bin(query(int(a)-1, int(b))).count('1'))    

class SegmentTree:
    def __init__(self, n=None, f=max, zero_factory=int, converter=lambda x:x, initial_values=None):
        assert(n or initial_values)
        self.__f, self.__z, self.__c = f, zero_factory, converter
        size = n if n else len(initial_values)
        self.__n = 1 << ((size - 1).bit_length())
        d = [zero_factory() for _ in range(2 * self.__n + 1)]
        self.__dat = d
        if initial_values:
            for i, v in enumerate(initial_values): d[self.__n + i] = converter(v)
            for i in range(self.__n - 1, 0, -1): d[i] = f(d[i<<1], d[i<<1|1])

    def update(self, index, value):
        i, v, d = index + self.__n, self.__c(value), self.__dat
        if d[i] == v: return
        d[i] = v
        while i:
            i = i >> 1
            d[i] = self.__f(d[i<<1], d[i<<1|1])

    def query(self, from_inclusive, to_exclusive):
        ans = self.__z()
        if to_exclusive <= from_inclusive: return ans
        l, r = from_inclusive + self.__n, to_exclusive + self.__n
        while l < r:
            if l & 1: ans, l = self.__f(ans, self.__dat[l]), l+1
            if r & 1: ans, r = self.__f(ans, self.__dat[r-1]), r-1
            l, r = l >> 1, r >> 1
        return ans

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    S = input()
    tree = SegmentTree(initial_values=S, f=lambda x,y:x|y, converter=lambda c: 1 << (ord(c)-ord('a')))
    Q = int(input())
    update = tree.update
    query = tree.query
    for _ in range(Q):
        t, a, b = input().split()
        if t == '1': update(int(a)-1, b)
        else: print(bin(query(int(a)-1, int(b))).count('1'))    

class SegmentTree:
    def __init__(self, n=None, f=max, zero_factory=int, converter=lambda x:x, initial_values=None):
        assert(n or initial_values)
        self.__f, self.__z, self.__c = f, zero_factory, converter
        size = n if n else len(initial_values)
        self.__n = 1 << ((size - 1).bit_length())
        d = [zero_factory() for _ in range(2 * self.__n + 1)]
        self.__dat = d
        if initial_values:
            for i, v in enumerate(initial_values): d[self.__n + i] = converter(v)
            for i in range(self.__n - 1, 0, -1): d[i] = f(d[i<<1], d[i<<1|1])

    def update(self, index, value):
        i, v, d = index + self.__n, self.__c(value), self.__dat
        if d[i] == v: return
        d[i] = v
        while i:
            i = i >> 1
            d[i] = self.__f(d[i<<1], d[i<<1|1])

    def query(self, from_inclusive, to_exclusive):
        ans = self.__z()
        if to_exclusive <= from_inclusive: return ans
        l, r = from_inclusive + self.__n, to_exclusive + self.__n
        while l < r:
            if l & 1: ans, l = self.__f(ans, self.__dat[l]), l+1
            if r & 1: ans, r = self.__f(ans, self.__dat[r-1]), r-1
            l, r = l >> 1, r >> 1
        return ans

if __name__ == '__main__':
    main()

Submission status: Accepted

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:
    """
    セグ木は 1-indexed
    """
    def __init__(self, n, initial=0):
        self.offset = 2**(n-1).bit_length()
        self.initial = initial
        self.seg = [self.initial] * (2 * self.offset)


    def build(self, A):
        """
        A: 処理したい配列
        """
        for i, a in enumerate(A, start=self.offset):
            self.seg[i] = string_to_number(a)
        for i in range(self.offset-1,0,-1):
            self.seg[i] = self.seg[i<<1] | self.seg[(i<<1)+1]

            
    def update(self, k, a):
        k += self.offset
        self.seg[k] = string_to_number(a)
        while k:
            k >>= 1
            self.seg[k] = self.seg[k<<1] | self.seg[(k<<1)+1]

            
    def query(self, a, b):
        a += self.offset
        b += self.offset
        res = self.initial
        while a < b:
            if a & 1:
                res |= self.seg[a]
                a += 1
            if b & 1:
                res |= self.seg[b-1]
            a >>= 1
            b >>= 1
        
        return bin(res).count("1")


def main():
    N,s,Q,*q = read().split()
    seg = SegmentTree(int(N))
    seg.build(s)
    #print(seg.seg)

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