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:

class SegmentTree:
    def __init__(self, base_array,n , default_value = 0, segfunc = lambda a, b: a + b): #元配列、大きさ、デフォルト値
        self._num = 2 ** (n - 1).bit_length()
        self._seg = [default_value] * 2 * self._num
        self._segfunc = segfunc
        self._ide_ele = default_value
        for i in range(n):
            self._seg[i + self._num - 1] = base_array[i]
        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:
            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

def main():
    N = int(input())
    S = [c for c in input()]
    M = int(input())

    A = [0 for i in range(N)]

    for i, c in enumerate(S):
        A[i] = 1 << ord(c) - ord('a')

    st = SegmentTree(A, N, 0, lambda a, b: a | b)

    for i in range(M):
        p, a, b = input().split()
        a  = int(a) - 1
        b = int(b) - 1 if p == '2' else b
        if p == '1':
            st.update(a, 1 << ord(b) - ord('a'))

        if p == '2':
            s = st.query(a, b + 1)
            print(bin(s).count('1'))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class my_segment_tree:
    def __init__(self, base_array, size, f=lambda a, b: a + b, default_value = 0):
        self.f = f
        self._seg_size = 2 ** (size.bit_length() + 1) - 1
        self._default_value = default_value
        self._array = [default_value] * (self._seg_size)
        k = 2 ** size.bit_length() - 1  # 一番下の最初のindex

        for i in range(size):
            self._array[k + i] = base_array[i]

        while k > 0:
            for i in range((k + 1) // 2):
                self._array[(k + 2 * i) // 2] = f(self._array[k + 2 * i], self._array[k + 2 * i + 1])
            k //= 2
    def update(self, i, v):
        i += (self._seg_size // 2)
        self._array[i] = v
        while i > 0:
            i = (i - 1) >> 1
            self._array[i] = self.f(self._array[2 * i + 1], self._array[2 * i + 2])

    def get(self, left, right):
        return self._get(left, right, 0, self._seg_size // 2, 0) #どちらも閉空間

    def _get(self, left, right, l, r, i):
        if left <= l and r <= right:
            return self._array[i]

        a = 0
        if left <= (l + r) // 2:
            a = self._get(left, min(right, (l + r) // 2), l, (l + r) // 2, 2 * i + 1)
        b = 0
        if (l + r) // 2 + 1 <= right:
            b= self._get(max(left, (l + r) // 2 + 1), right, (l + r) // 2 + 1, r, 2 * i + 2)

        return self.f(a, b)

def main():
    N = int(input())
    S = input()
    M = int(input())
    A = [0 for i in range(N)]

    for i, c in enumerate(S):
        A[i] = 1 << ord(c) - ord('a')

    st = my_segment_tree(A, N, lambda a, b: a | b)

    for i in range(M):
        p, a, b = input().split()
        a  = int(a) - 1
        if p == '1':
            st.update(a, 1 << (ord(b) - ord('a')))

        if p == '2':
            s = st.get(a, int(b) - 1)
            print(bin(s).count('1'))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from bisect import bisect_left, insort
def main():
    n = int(input())
    s = list(input().rstrip())
    q = int(input())
    ans = []
    al = [[] for _ in range(26)]
    for i, c in enumerate(s):
        al[ord(c) - ord("a")].append(i)
    for _ in range(q):
        x, y, z = map(str, input().rstrip().split())
        if x == "1":
            y = int(y) - 1
            if s[y] == z:
                continue
            p = bisect_left(al[ord(s[y])-ord("a")],y)
            al[ord(s[y])-ord("a")].pop(p)
            insort(al[ord(z)-ord("a")],y)
            s[y] = z
        else:
            y = int(y) - 1
            z = int(z)
            cnt = 0
            for i in range(26):
                index = bisect_left(al[i], y)
                if index < len(al[i]) and al[i][index] < z:
                    cnt += 1
            ans.append(cnt)
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# E - Simple String Queries
from operator import or_


class SegmentTree:
    __slots__ = ["_default_value", "_seg_func", "_modifying_func", "_size", "_tree"]

    def __init__(self, initial_values: "Sequence", default_value: "Union[int, str]", seg_func: "Callable",
                 modifying_func: "Optional[Callable]" = None) -> None:
        self._default_value = default_value
        self._seg_func = seg_func
        self._modifying_func = modifying_func
        self._size = 1 << (len(initial_values) - 1).bit_length()
        self._tree = self._build(initial_values)

    def _build(self, initial_values: "Sequence") -> "List":
        """Build a segment tree with initial values."""
        tree = [self._default_value] * (2 * self._size)

        if self._modifying_func:
            initial_values = map(self._modifying_func, initial_values)

        for idx, val in enumerate(initial_values):  # set a tree
            tree[idx + self._size - 1] = val

        for idx in range(self._size - 2, -1, -1):  # build
            tree[idx] = self._seg_func(tree[2 * idx + 1], tree[2 * idx + 2])

        return tree

    def update(self, index: int, value: int) -> None:
        """Update index to value."""
        index += self._size - 1
        if self._modifying_func:
            value = self._modifying_func(value)
        self._tree[index] = value
        while index:
            index = (index - 1) // 2
            self._tree[index] = self._seg_func(self._tree[2 * index + 1], self._tree[2 * index + 2])

    def query(self, left: int, right: int) -> "Union[int, str]":
        """Respond to query in [left, right]."""
        left += self._size
        right += self._size
        result = self._default_value
        while left < right:
            if left & 1:
                result = self._seg_func(result, self._tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                result = self._seg_func(result, self._tree[right - 1])
            left >>= 1
            right >>= 1
        return result


def main():
    _, S, _, *queries = open(0).read().split()
    tree = SegmentTree(S, 0, or_, lambda c: 1 << (ord(c) - 97))
    ans = []
    popcount = lambda x: bin(x).count("1")
    for com, a, b in zip(*[iter(queries)] * 3):
        if com == "1":
            tree.update(int(a) - 1, b)
        else:
            ans.append(popcount(tree.query(int(a) - 1, int(b))))
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# E - Simple String Queries
from operator import or_


class SegmentTree:
    __slots__ = ["_default_value", "_seg_func", "_modifying_func", "_size", "_tree"]

    def __init__(self, initial_values: "Sequence", default_value: "Union[int, str]", seg_func: "Callable",
                 modifying_func: "Optional[Callable]" = None) -> None:
        self._default_value = default_value
        self._seg_func = seg_func
        self._modifying_func = modifying_func
        self._size = 1 << (len(initial_values) - 1).bit_length()
        self._tree = self._build(initial_values)

    def _build(self, initial_values: "Sequence") -> "List":
        """Build a segment tree with initial values."""
        tree = [self._default_value] * (2 * self._size)

        if self._modifying_func:
            initial_values = map(self._modifying_func, initial_values)

        for idx, val in enumerate(initial_values):  # set a tree
            tree[idx + self._size - 1] = val

        for idx in range(self._size - 2, -1, -1):  # build
            tree[idx] = self._seg_func(tree[2 * idx + 1], tree[2 * idx + 2])

        return tree

    def update(self, index: int, value: int) -> None:
        """Update index to value."""
        index += self._size - 1
        if self._modifying_func:
            value = self._modifying_func(value)
        self._tree[index] = value
        while index:
            index = (index - 1) // 2
            self._tree[index] = self._seg_func(self._tree[2 * index + 1], self._tree[2 * index + 2])

    def query(self, left: int, right: int) -> "Union[int, str]":
        """Respond to query in [left, right]."""
        left += self._size
        right += self._size
        result = self._default_value
        while left < right:
            if left & 1:
                result = self._seg_func(result, self._tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                result = self._seg_func(result, self._tree[right - 1])
            left >>= 1
            right >>= 1
        return result


def main():
    _, S, _, *queries = open(0).read().split()
    tree = SegmentTree(tuple(S), 0, or_, lambda c: 1 << (ord(c) - 97))
    ans = []
    popcount = lambda x: bin(x).count("1")
    for com, a, b in zip(*[iter(queries)] * 3):
        if com == "1":
            tree.update(int(a) - 1, b)
        else:
            ans.append(popcount(tree.query(int(a) - 1, int(b))))
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# E - Simple String Queries
from operator import or_


class SegmentTree:
    __slots__ = ["_default_value", "_seg_func", "_modifying_func", "_size", "_tree"]

    def __init__(self, initial_values: "Sequence", default_value: "Union[int, str]", seg_func: "Callable",
                 modifying_func: "Optional[Callable]" = None) -> None:
        self._default_value = default_value
        self._seg_func = seg_func
        self._modifying_func = modifying_func
        self._size = 1 << (len(initial_values) - 1).bit_length()
        self._tree = self._build(initial_values)

    def _build(self, initial_values: "Sequence") -> "List":
        """Build a segment tree with initial values."""
        tree = [self._default_value] * (2 * self._size)

        if self._modifying_func:
            initial_values = map(self._modifying_func, initial_values)

        for idx, val in enumerate(initial_values):  # set a tree
            tree[idx + self._size - 1] = val

        for idx in range(self._size - 2, -1, -1):  # build
            tree[idx] = self._seg_func(tree[2 * idx + 1], tree[2 * idx + 2])

        return tree

    def update(self, index: int, value: int) -> None:
        """Update index to value."""
        index += self._size - 1
        if self._modifying_func:
            value = self._modifying_func(value)
        self._tree[index] = value
        while index:
            index = (index - 1) // 2
            self._tree[index] = self._seg_func(self._tree[2 * index + 1], self._tree[2 * index + 2])

    def query(self, left: int, right: int) -> "Union[int, str]":
        """Respond to query in [left, right]."""
        left += self._size
        right += self._size
        result = self._default_value
        while left < right:
            if left & 1:
                result = self._seg_func(result, self._tree[left - 1])
                left += 1
            if right & 1:
                right -= 1
                result = self._seg_func(result, self._tree[right - 1])
            left >>= 1
            right >>= 1
        return result


def main():
    _, S, _, *queries = open(0).read().split()
    tree = SegmentTree(list(S), 0, or_, lambda c: 1 << (ord(c) - 97))
    ans = []
    popcount = lambda x: bin(x).count("1")
    for com, a, b in zip(*[iter(queries)] * 3):
        if com == "1":
            tree.update(int(a) - 1, b)
        else:
            ans.append(popcount(tree.query(int(a) - 1, int(b))))
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect
 

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

pos = [[] for _ in range(26)]
for x,s in enumerate(S):
    num = ord(s)-ord("a")
    pos[num].append(x)

q = int(input())
for _ in range(q):
    m,a,b = map(str,input().split())
    if m == "1":
        a = int(a)-1
        if S[a] == b:
            continue
        else:
            popind = bisect.bisect_left(pos[ord(S[a])-ord("a")],a)
            pos[ord(S[a])-ord("a")].pop(popind)
            bisect.insort(pos[ord(b)-ord("a")],a)
            S[a] = b
    else:
        a,b = int(a)-1,int(b)-1
        count = 0
        for i in range(26):
            l = bisect.bisect_left(pos[i],a)
            if l >= len(pos[i]):
                continue
            if pos[i][l] <= b:
                count += 1
        print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
#####segfunc######
def segfunc(x,y):
    return x | y

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

#####単位元######
n = int(input())
s = list(input())[:-1]
ide_ele = 0
num =2**(n-1).bit_length()
seg=[ide_ele]*(2*num - 1)
s = [2 ** (ord(i) - ord('a')) for i in s]
init(s)
q = int(input())
for i in range(q):
    tmp = input()
    a,b,c = tmp[:-1].split()
    if a == "1":
        update(int(b)-1, 2 ** (ord(c) - ord('a')))
    else:
        if b == c:
            print(1)
        else:
            tmp = query(int(b)-1, int(c))
            tmp = format(tmp, 'b')
            print(tmp.count('1'))

Submission status: Accepted

Solution code:
class BIT:
    """
    https://tjkendev.github.io/procon-library/python/range_query/bit.html
    Binary index treeの実装
    配列[a1, a2,...,an]に対して以下のクエリをO(logn)で行う:
        1. aiにxを加える
        2. 区間和 ai + a(i+1) + ... + aj の和を求める
    """
    def __init__(self, n):
        """
        添字は1スタート
        """
        self.n = n
        self.data = [0] * (n + 1)
        self.el = [0] * (n + 1)

    def add(self, i, x):
        """
        i>0に対してaiにxを加算(x < 0でもOK)
        """
        if i <= 0 or self.n < i:
            print("i should be within 1 to n")
        else:
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

    def sum(self, i):
        """
        添字1からiまでの累積和を求める
        """
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s

    def get(self, i, j=None):
        """
        添字iからjまでの累積和を求める
        j=Noneの場合はaiの値を返す
        """
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i - 1)


"""
ここから本問の解答
各アルファベットごとにBITを作成する
"""

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

# ここを Alphabet = [BIT(N)] * 26とすると、
# どうもすべてのAlphabet[i]が連動するらしい
Alphabet = [None] * 26
for i in range(26):
    Alphabet[i] = BIT(N)

# Sの初期値からBITを初期化
for i, s in enumerate(S):
    num = ord(s) - 97
    Alphabet[num].add(i + 1, 1)

"""
各クエリごとに行う操作を関数にまとめておく
"""
def change(i, c):
    if S[i - 1] != c:
        pre = ord(S[i - 1]) - 97
        Alphabet[pre].add(i, -1)
        post = ord(c) - 97
        Alphabet[post].add(i, 1)
        S[i - 1] = c

def appear(l, r):
    char = 0
    for i in range(26):
        if Alphabet[i].get(l, r) >= 1:
            char += 1
    return char

"""
クエリ処理
"""

for _ in range(Q):
    flag, x, y = input().split()
    if flag == "1":
        i, c = int(x), y
        change(i, c)
    elif flag == "2":
        l, r = int(x), int(y)
        print(appear(l, r))

Submission status: Accepted

Solution code:
from sys import stdin
import sys
#import numpy as np
import collections
from functools import cmp_to_key
import heapq

##  input functions for me
def rsa(sep = ''):
    if sep == '' :
        return input().split() 
    else: return input().split(sep)
def rip(sep = ''):
    if sep == '' :
        return map(int, input().split()) 
    else: return map(int, input().split(sep))
def ria(sep = ''): 
    return list(rip(sep))
def ri(): return int(input())
def rd(): return float(input())
def rs(): return input()
##

class fenwick_tree:
    def __init__(self, n):
        self.N = n
        self.n = 1 # pow of 2
        while(self.n < self.N):
            self.n *= 2
        self.data = [0] * (self.n + 1)

    def add(self, idx, x):
        while idx <= self.n:
            self.data[idx] += x
            idx += (idx & -idx)

    def cumulate(self, idx):
        s = 0
        while idx > 0:
            s += self.data[idx]
            idx -= (idx & -idx)
        return s

def main():
    N = ri()
    S = rs()
    Q = ri()
    ans = []

    bit = [fenwick_tree(N) for i in range(26)]
    for i in range(N):
        d = ord(S[i]) - ord('a')
        bit[d].add(i + 1, 1)

    ca = [c for c in S]
    for _ in range(Q):
        ss = rsa()
        if ss[0] == '1':
            pos = int(ss[1]) - 1
            c = ss[2][0]
            bit[ord(ca[pos]) - ord('a')].add(pos + 1, -1)
            ca[pos] = c
            bit[ord(ca[pos]) - ord('a')].add(pos + 1, +1)
        else:
            l = int(ss[1]) - 1
            r = int(ss[2]) - 1
            cnt = 0
            for i in range(26):
                su = bit[i].cumulate(r + 1) - bit[i].cumulate(l)
                if su > 0: cnt += 1
            ans.append(cnt)
    
    print("\n".join([str(n) for n in ans]))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N = int(input())
S = input().strip()
Q = int(input())
n = 1
while n < N:
    n *= 2
T = [0] * (2 * n)

def update(k, a):
    k += n-1
    T[k] = 1 << ord(a) - 97
    while k > 0:
        k = (k - 1) // 2
        T[k] = T[k*2+1] | T[k*2+2]

def query(a, b, k, l, r):
    # print(a, b, k, l, r)
    if r <= a or b <= l:
        # print('  ', set())
        return 0
    if a <= l and r <= b:
        # print('  ', T[k])
        return T[k]
    else:
        vl = query(a, b, k*2+1, l, (l+r)//2)
        vr = query(a, b, k*2+2, (l+r)//2, r)
        return vl | vr

for i in range(N):
    update(i, S[i])

for q in range(Q):
    f, i, c = [x for x in input().strip().split()]
    if f == '1':
        # print(T,T[int(i)-1])
        update(int(i)-1, c)
    elif f == '2':
        # print(int(i)-1, int(c)-1)
        tmp = query(int(i)-1, int(c), 0, 0, n)
        ans = 0
        for i in range(26):
            ans += tmp >> i & 1
         
        print(ans)

Submission status: Accepted

Solution code:
# coding: UTF-8
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    class SegmentTree:
        def __init__(self,n,ide_ele,segfunc):
            self.ide_ele=ide_ele
            self.segfunc=segfunc
            self.num=2**(n-1).bit_length()
            self.dat=[ide_ele]*2*self.num
        
        def init(self,iter):
            for i in range(n):
                self.dat[i+self.num]=iter[i]
            for i in range(self.num-1,0,-1):
                self.dat[i]=self.segfunc(self.dat[i*2],self.dat[i*2+1])
        
        def update(self,k,x):
            k+=self.num
            self.dat[k]=x
            while k:
                k//=2
                self.dat[k]=self.segfunc(self.dat[k*2],self.dat[k*2+1])
        
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p+=self.num
            q+=self.num-1
            res=self.ide_ele
            while q-p>1:
                if p&1==1:
                    res=self.segfunc(res,self.dat[p])
                if q&1==0:
                    res=self.segfunc(res,self.dat[q])
                    q-=1
                p=(p+1)//2
                q=q//2
            if p==q:
                res=self.segfunc(res,self.dat[p])
            else:
                res=self.segfunc(self.segfunc(res,self.dat[p]),self.dat[q])
            return res
    
    N=int(input())
    S=list(input())
    Q=int(input())
    seg=[SegmentTree(N,0,lambda x,y:x+y) for _ in range(26)]
    
    S2=[0]*N
    
    for i in range(N):
        S2[i]=ord(S[i])-ord('a')
    
    for i,x in enumerate(S2):
        p=seg[x].query(i,i+1)
        seg[x].update(i,p+1)
    
    for _ in range(Q):
        a,b,c=input().split()
        if a=='1':
            b=int(b)-1
            c=ord(c)-ord('a')
            p=seg[c].query(b,b+1)
            seg[c].update(b,p+1)
            q=seg[S2[b]].query(b,b+1)
            seg[S2[b]].update(b,q-1)
            S2[b]=c
        else:
            b=int(b)-1
            c=int(c)-1
            ans=0
            for i in range(26):
                ans+=bool(seg[i].query(b,c+1))
            print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from bisect import bisect_left,bisect_right,insort
#input = sys.stdin.readline

def main():
    n=int(input())
    s=list(str(input()))
    p=[[] for _ in range(26)]
    for i,S in enumerate(s):
        p[ord(S)-ord('a')].append(i)
    q=int(input())
    for i in range(q):
        a,b,c=map(str,input().split())
        if a=='1':
            b=int(b)-1
            if s[b]==c:
                continue
            else:
                insl=bisect_left(p[ord(s[b])-ord('a')],b)
                p[ord(s[b])-ord('a')].pop(insl)
                insort(p[ord(c)-ord('a')],b)
                s[b]=c
        else:
            b,c=int(b)-1,int(c)-1
            cnt=0
            for i in range(26):
                insl=bisect_left(p[i],b)
                if insl>=len(p[i]):
                    continue
                elif p[i][insl]<=c:
                    cnt+=1
            print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)

INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

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

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1) if i else self.sum(j - 1)

def main():
    N = I()
    s = list(S())
    Q = I()
    D = defaultdict(lambda : BIT(N))
    for i in range(N):
        D[s[i]].add(i,1)
    for j in range(Q):
        qi,i,c = LS()
        if qi == "1":
            i = int(i) - 1
            D[s[i]].add(i,-1)
            D[c].add(i,1)
            s[i] = c
        else:
            l,r = int(i)-1, int(c)
            result = 0
            for k in range(97,123):
                if D[chr(k)].interval_sum(l,r):
                    result += 1
            print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n = int(input())
s = input()
q = int(input())
commands = []
for _ in range(q):
    com, x, y = input().split()
    commands.append((com, int(x), y))

size = 1
while size < n:
    size *= 2

# initialize
segment_tree = [0 for _ in range(2 * size - 1)]


def alphabet2bit(string):
    return 1 << (ord(string) - ord('a'))

def update(i, x, segment_tree):
    i += size - 1
    segment_tree[i] = alphabet2bit(x)
    while i > 0:
        i = (i - 1) // 2
        left = segment_tree[i * 2 + 1]
        right = segment_tree[i * 2 + 2]
        segment_tree[i] = left | right

def getSum(s, t, k, l, r, segment_tree):
    if r <= s or t <= l:
        return 0
    if s <= l and r <= t:
        return segment_tree[k]
    else:
        ask_left = getSum(s, t, k * 2 + 1, l, (l + r) // 2, segment_tree)
        ask_right = getSum(s, t, k * 2 + 2, (l + r) // 2, r, segment_tree)
        return ask_left | ask_right

for i in range(n):
    update(i, s[i], segment_tree)

for com, x, y in commands:
    if com == '1':
        update(x - 1, y, segment_tree)
    else:
        result = getSum(x - 1, int(y), 0, 0, size, segment_tree)
        print(bin(result).count('1'))

Submission status: Accepted

Solution code:



# 点更新，区間クエリ
class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return max(x,y)

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

alphalist = [[0]*N for _ in range(26)]
atmp = ord('a')
for i,s in enumerate(S):
    alphalist[ord(s)-atmp][i] = 1

seglist = [None]*26
for i in range(26):
    seglist[i] = SegTree(N,alphalist[i],segfunc,0)

ans = []
for i in range(Q):
    t,l,r = map(str,input().split())
    if t=='1':
        i = int(l)-1
        c = r
        
        org_idx = ord(S[i])-atmp
        seglist[org_idx].update(i,0)
        S[i] = c
        upt_idx = ord(c) - atmp
        seglist[upt_idx].update(i,1)
                
        
    else:
        l,r = int(l)-1,int(r)
        cnt = 0
        for i in range(26):
            cnt += seglist[i].query(l,r)
        ans.append(cnt)

for a in ans:
    print(a)