Problem:


Score : 500 points

Problem Statement

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

Process Q queries of the following two types:

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

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

Constraints

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

S is a string consisting of lowercase English letters.

c_q is a lowercase English letter.

1 \leq N \leq 500000

1 \leq Q \leq 20000

|S| = N

1 \leq i_q \leq N

1 \leq l_q \leq r_q \leq N

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

Input

Input is given from Standard Input in the following format:

N
S
Q
Query_1
\vdots
Query_Q

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

1 i_q c_q

2 l_q r_q

Output

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

Sample Input 1

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

Sample Output 1

3
1
5

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

In the second query, S is modified to abcdzbd.

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

In the fourth query, S is modified to abcazbd.

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

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



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


Sample output:
3
1
5

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, or_

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)



def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
    def __init__(self, array, operator, identity_element):
        _len = len(array)
        self.__op = operator
        self.__size = 1 << (_len - 1).bit_length()
        self.__tree = [identity_element] * self.__size + \
            array + [identity_element] * (self.__size - _len)
        self.__ie = identity_element

        for i in range(self.__size - 1, 0, -1):
            self.__tree[i] = operator(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def update(self, i, v):
        i += self.__size
        self.__tree[i] = v
        while i:
            i //= 2
            self.__tree[i] = self.__op(
                self.__tree[i * 2], self.__tree[i * 2 + 1])

    def query(self, l, r):
        l += self.__size
        r += self.__size
        ret = self.__ie
        while l < r:
            if l & 1:
                ret = self.__op(ret, self.__tree[l])
                l += 1
            if r & 1:
                r -= 1
                ret = self.__op(ret, self.__tree[r])
            l //= 2
            r //= 2
        return ret


@mt
def slv(N, S, Q):
    st = SegmentTree([1 << (ord(c) - ord('a')) for c in S], or_, 0)

    for q in Q:
        if q[0] == '1':
            i = int(q[1]) - 1
            c = q[2]
            st.update(i, 1 << (ord(c) - ord('a')))
        if q[0] == '2':
            i = int(q[1]) - 1
            j = int(q[2]) - 1
            ans = 0
            v = st.query(i, j+1)
            for k in range(26):
                if (1 << k) & v:
                    ans += 1
            print(ans)
    # return ans


def main():
    N = read_int()
    S = read_str()
    Q = [read_str_n() for _ in range(read_int())]
    (slv(N, S, Q))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
NN = 19
X = [0] * ((1<<NN+1)-1)
 
def popcount(x):
    x -= (x >> 1) & 0x55555555
    x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
    x = (x + (x >> 4)) & 0x0f0f0f0f
    x += x >> 8
    x += x >> 16
    return x & 0x3f

def update(a, x):
    i = (1<<NN) - 1 + a
    X[i] = x
    while True:
        i = (i-1) // 2
        X[i] = X[2*i+1] | X[2*i+2]
        if i == 0:
            break

def rangeor(a, b):
    l = a + (1<<NN)
    r = b + (1<<NN)
    x = 0
    while l < r:
        if l%2:
            x |= X[l-1]
            l += 1
        if r%2:
            r -= 1
            x |= X[r-1]
        l >>= 1
        r >>= 1
    return x

N = int(input())
A = [ord(a) - 97 for a in input()]
for i, a in enumerate(A):
    update(i+1, 1<<a)

Q = int(input())
for _ in range(Q):
    a, b, c = input().rstrip().split()
    if a == "1":
        b = int(b)
        c = ord(c) - 97
        update(b, 1<<c)
    else:
        b, c = int(b), int(c)
        print(popcount(rangeor(b, c+1)))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, lst, op, e):
        self.n = len(lst)
        self.N = 1 << ((self.n - 1).bit_length())
        self.op = op # operation
        self.e = e # identity element
        self.v = self._build(lst)
        
    def _build(self, lst):
        # construction of a tree
        # total 2 * self.N - 1 elements
        tree = [self.e] * (self.N - 1) + lst + [self.e] * (self.N - self.n)
        for i in range(self.N - 2, -1, -1):
            tree[i] = self.op(tree[2*i + 1], tree[2*i + 2])
        return tree
    
    def __getitem__(self, i):
        return self.v[i + self.N - 1]
    
    # update a_i to be x 
    def update(self, i, x):
        i += self.N - 1
        self.v[i] = x
        while i > 0:
            i -= 1; i >>= 1
            self.v[i] = self.op(self.v[2*i + 1], self.v[2*i + 2])
    
    # returns answer for the query interval [l, r)
    def query(self, l, r):
        left = l + self.N - 1
        right = r + self.N - 1
        L = self.e; R = self.e
        while left < right:
            if left & 1 == 0: # self.v[left] is the right child
                L = self.op(L, self.v[left])
                left += 1
            if right & 1 == 0: # self.v[right-1] is the left child
                right -= 1
                R = self.op(self.v[right], R)
            left -= 1; left >>= 1
            right >>= 1
        return self.op(L, R)

N = int(input())
S = input()
sg = SegmentTree([1 << (ord(s) - ord('a')) for s in S], lambda x, y: x | y, 0)
Q = int(input())
for _ in range(Q):
    t, a, b = input().split()
    t = int(t); a = int(a)
    if t == 1:
        sg.update(a-1, 1 << (ord(b) - ord('a')))
    else:
        b = int(b)
        x = sg.query(a-1, b)
        ans = 0
        for i in range(26):
            if (1 << i) & x: ans += 1
        print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, or_

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)



def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, array, operator, identity_element):
        """ operator and identity_element has to be a monoid.
        """
        self.__N = 2**int(math.ceil(math.log(len(array), 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__op = operator
        self.__ie = identity_element
        for i, v in enumerate(array):
            self.__table[i+self.__N - 1] = v

        for i in range(self.__N - 2, 0, -1):
            pi = i
            li = 2*pi + 1
            ri = 2*pi + 2
            v = self.__op(self.__table[li], self.__table[ri])
            self.__table[pi] = v


    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        t = self.__table
        o = self.__op

        t[i] = x
        while i != 0:
            i = (i - 1) // 2
            t[i] = o(t[2*i + 1], t[2*i + 2])

    def query(self, a, b):
        stack = [(0, 0, self.__N)]
        t = self.__table
        o = self.__op

        ans = self.__ie
        while stack:
            k, l, r = stack.pop()
            cnd = t[k]
            if a <= l and r <= b:
                ans = o(ans, cnd)
            else:
                if (l + r) // 2 > a and b > l:
                    stack.append((2 * k + 1, l, (l + r) // 2))

                if r > a and b > (l + r) // 2:
                    stack.append((2 * k + 2, (l + r) // 2, r))
        return ans

    def print(self):
        print(self.__table)



@mt
def slv(N, S, Q):
    st = SegmentTree([1 << (ord(c) - ord('a')) for c in S], or_, 0)

    for q in Q:
        if q[0] == '1':
            i = int(q[1]) - 1
            c = q[2]
            st.update(i, 1 << (ord(c) - ord('a')))
        if q[0] == '2':
            i = int(q[1]) - 1
            j = int(q[2]) - 1
            ans = 0
            v = st.query(i, j+1)
            for k in range(26):
                if (1 << k) & v:
                    ans += 1
            print(ans)
    # return ans


def main():
    N = read_int()
    S = read_str()
    Q = [read_str_n() for _ in range(read_int())]
    (slv(N, S, Q))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class SegmentTree():
    """一点更新、区間取得クエリをそれぞれO(logN)で答えるデータ構造を構築する。
    built(array)   := arrayを初期値とするセグメント木を構築する O(N)。
    update(i, val) := i番目の要素をvalに変更する。
    get_val(l, r)  := 区間[l, r)に対する二項演算の畳み込みの結果を返す。
    """

    def __init__(self, n, op, e):
        """要素数、二項演算、単位元を引数として渡す
        例) 区間最小値 SegmentTree(n, min, 10 ** 18)
            区間和     SegmentTree(n, lambda a, b : a + b, 0)
        """
        self.n = n
        self.op = op
        self.e = e
        self.size = 2 ** ((n - 1).bit_length())
        self.node = [self.e] * (2 * self.size)

    def built(self, array):
        """arrayを初期値とするセグメント木を構築する"""
        for i in range(self.n):
            self.node[self.size + i] = array[i]
        for i in range(self.size - 1, 0, -1):
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def update(self, i, val):
        """i番目の要素をvalに変更する"""
        i += self.size
        self.node[i] = val
        while i > 1:
            i >>= 1
            self.node[i] = self.op(self.node[i << 1], self.node[(i << 1) + 1])

    def get_val(self, l, r):
        """[l, r)の畳み込みの結果を返す"""
        l, r = l + self.size, r + self.size
        res = self.e
        while l < r:
            if l & 1:
                res = self.op(self.node[l], res)
                l += 1
            if r & 1:
                r -= 1
                res = self.op(self.node[r], res)
            l, r = l >> 1, r >> 1
        return res

import sys
input = sys.stdin.readline


n = int(input())
s = input()
q = int(input())
query = [list(input().split()) for i in range(q)] 
 
alph = "abcdefghijklmnopqrstuvwxyz"
to_int = {char: i for i, char in enumerate(alph)}
st = SegmentTree(n, lambda a, b : a | b, 0)
 
init = [0] * n
for i, char in enumerate(s[0:n]):
    init[i] = 1 << to_int[char]
st.built(init)

for num, l, r in query:
    if num == "1":
        st.update(int(l) - 1, 1 << to_int[r]) 
    else:
        tmp = st.get_val(int(l) - 1, int(r))
        print(bin(tmp).count("1"))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, or_

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)



def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, array, operator, identity_element):
        """ operator and identity_element has to be a monoid.
        """
        self.__N = 2**int(math.ceil(math.log(len(array), 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__op = operator
        self.__ie = identity_element
        for i, v in enumerate(array):
            self.__table[i+self.__N - 1] = v

        for i in range(self.__N - 2, 0, -1):
            pi = i
            li = 2*pi + 1
            ri = 2*pi + 2
            v = self.__op(self.__table[li], self.__table[ri])
            self.__table[pi] = v


    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        t = self.__table
        o = self.__op

        t[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            li = 2*pi + 1
            ri = 2*pi + 2
            v = o(t[li], t[ri])
            t[pi] = v
            i = pi

    def query(self, a, b):
        stack = [(0, 0, self.__N)]
        t = self.__table
        o = self.__op

        ans = self.__ie
        c = 0
        while stack:
            c += 1
            k, l, r = stack.pop()
            cnd = t[k]
            if a <= l and r <= b:
                ans = o(ans, cnd)
            else:
                if (l + r) // 2 > a and b > l:
                    stack.append((2 * k + 1, l, (l + r) // 2))

                if r > a and b > (l + r) // 2:
                    stack.append((2 * k + 2, (l + r) // 2, r))
        return ans

    def print(self):
        print(self.__table)



@mt
def slv(N, S, Q):
    st = SegmentTree([1 << (ord(c) - ord('a')) for c in S], or_, 0)

    for q in Q:
        if q[0] == '1':
            i = int(q[1]) - 1
            c = q[2]
            st.update(i, 1 << (ord(c) - ord('a')))
        if q[0] == '2':
            i = int(q[1]) - 1
            j = int(q[2]) - 1
            ans = 0
            v = st.query(i, j+1)
            for k in range(26):
                if (1 << k) & v:
                    ans += 1
            print(ans)
    # return ans


def main():
    N = read_int()
    S = read_str()
    Q = [read_str_n() for _ in range(read_int())]
    (slv(N, S, Q))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, or_

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)



def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, array, operator, identity_element):
        """ operator and identity_element has to be a monoid.
        """
        self.__N = 2**int(math.ceil(math.log(len(array), 2)))
        self.__table = [identity_element] * (self.__N * 2 - 1)
        self.__op = operator
        self.__ie = identity_element
        for i, v in enumerate(array):
            self.__table[i+self.__N - 1] = v

        for i in range(self.__N - 2, 0, -1):
            pi = i
            li = 2*pi + 1
            ri = 2*pi + 2
            v = self.__op(self.__table[li], self.__table[ri])
            self.__table[pi] = v


    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        t = self.__table
        o = self.__op

        t[i] = x
        while i != 0:
            pi = (i - 1) // 2  # parent
            li = 2*pi + 1
            ri = 2*pi + 2
            v = o(t[li], t[ri])
            if t[pi] != v:
                t[pi] = v
            else:
                break
            i = pi

    def query(self, a, b):
        stack = [(0, 0, self.__N)]
        t = self.__table
        o = self.__op

        ans = self.__ie
        c = 0
        while stack:
            c += 1
            k, l, r = stack.pop()
            cnd = t[k]
            if a <= l and r <= b:
                ans = o(ans, cnd)
            else:
                if (l + r) // 2 > a and b > l:
                    stack.append((2 * k + 1, l, (l + r) // 2))

                if r > a and b > (l + r) // 2:
                    stack.append((2 * k + 2, (l + r) // 2, r))
        return ans

    def print(self):
        print(self.__table)



@mt
def slv(N, S, Q):
    st = SegmentTree([1 << (ord(c) - ord('a')) for c in S], or_, 0)

    for q in Q:
        if q[0] == '1':
            i = int(q[1]) - 1
            c = q[2]
            st.update(i, 1 << (ord(c) - ord('a')))
        if q[0] == '2':
            i = int(q[1]) - 1
            j = int(q[2]) - 1
            ans = 0
            v = st.query(i, j+1)
            for k in range(26):
                if (1 << k) & v:
                    ans += 1
            print(ans)
    # return ans


def main():
    N = read_int()
    S = read_str()
    Q = [read_str_n() for _ in range(read_int())]
    (slv(N, S, Q))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        if i == 0:
            return 0
        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
aas = "abcdefghijklmnopqrstuvwxyz"
N = int(input().strip())
S = [" "]+list(input().strip())
Q = int(input().strip())
cbt = dict()
for c in aas:
    cbt[c] = Bit(N)
    for i, a in enumerate(S):
        if i == 0:
            continue
        if a == c:
            cbt[c].add(i, 1)

for _ in range(Q):
    t, i, c = input().split()
    t = int(t)
    if t == 1:
        i = int(i)
        if S[i] != c:
            cbt[S[i]].add(i, -1)
            cbt[c].add(i, 1)
            S[i] = c
    else:
        l, r = int(i), int(c)
        s = 0
        for a in aas:
            bt = cbt[a]
            s += (bt.sum(r)-bt.sum(l-1)>0)
        print(s)

Submission status: Accepted

Solution code:
N = int(input())
A = [ord(a) - 97 for a in input()]
NN = 19
BIT=[[0]*(2**NN+1) for _ in range(26)]
 
def addbit(t, i, x):
    while i <= 2**NN:
        BIT[t][i] += x
        i += i & (-i)

def getsum(t, i):
    ret = 0
    while i != 0:
        ret += BIT[t][i]
        i -= i&(-i)
    return ret

for i, a in enumerate(A):
    addbit(a, i+2, 1)

Q = int(input())
for _ in range(Q):
    a, b, c = input().rstrip().split()
    if a == "1":
        b = int(b)
        c = ord(c) - 97
        t = A[b-1]
        addbit(t, b+1, -1)
        addbit(c, b+1, 1)
        A[b-1] = c
    else:
        b, c = int(b), int(c)
        s = 0
        for t in range(26):
            s += 1 if getsum(t, c+1) - getsum(t, b) else 0
        print(s)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub, or_

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


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


def read_float():
    return float(input())


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


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)



def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree:
	def __init__(self, orig, func, unit):
		_len = len(orig)
		self.func = func
		self.size = 1 << (_len - 1).bit_length()
		self.tree = [unit] * self.size + orig + [unit] * (self.size - _len)
		self.unit = unit

		for i in range(self.size - 1, 0, -1):
			self.tree[i] = func(self.tree[i * 2], self.tree[i * 2 + 1])

	def update(self, i, v):
		i += self.size
		self.tree[i] = v
		while i:
			i //= 2
			self.tree[i] = self.func(self.tree[i * 2], self.tree[i * 2 + 1])

	def find(self, l, r):
		l += self.size
		r += self.size
		ret = self.unit
		while l < r:
			if l & 1:
				ret = self.func(ret, self.tree[l])
				l += 1
			if r & 1:
				r -= 1
				ret = self.func(ret, self.tree[r])
			l //= 2
			r //= 2
		return ret

@mt
def slv(N, S, Q):
    st = SegmentTree([1 << (ord(c) - ord('a')) for c in S], or_, 0)

    for q in Q:
        if q[0] == '1':
            i = int(q[1]) - 1
            c = q[2]
            st.update(i, 1 << (ord(c) - ord('a')))
        if q[0] == '2':
            i = int(q[1]) - 1
            j = int(q[2]) - 1
            ans = 0
            v = st.find(i, j+1)
            for k in range(26):
                if (1 << k) & v:
                    ans += 1
            print(ans)
    # return ans


def main():
    N = read_int()
    S = read_str()
    Q = [read_str_n() for _ in range(read_int())]
    (slv(N, S, Q))

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
S=input()
nagasa=len(list(S))
num=2**(nagasa-1).bit_length()
SEG=[0]*2*num
def word_num(a):
    return 1<<(ord(a)-96)
def init(S):
    for i in range(n):
        SEG[i+num-1]=word_num(S[i])
    for i in range(num-2,-1,-1) :
        SEG[i]=SEG[2*i+1]|SEG[2*i+2]
    
def update(k,x):
    k += num-1
    SEG[k] = word_num(x)
    while k:
        k-=1
        k//=2
        SEG[k] = SEG[k*2+1] | SEG[k*2+2]
    
def query(p,q):
    if q<=p:
        return 0
    p += num-1
    q += num-2
    ans=0
    while q-p>1:
        if p&1 == 0:
            ans|= SEG[p]
        if q&1 == 1:
            ans|= SEG[q]
            q -= 1
        p //=2
        q-=1
        q//=2
    if p == q:
        ans |=SEG[p]
    else:
        ans |= SEG[p]
        ans |= SEG[q]
    return ans
init(S)
q=int(input())
for i in range(q):
    a,s,t=input().split()
    if a=='1':
        s=int(s)
        update(s-1,t)
    if a=='2':
        s=int(s)
        t=int(t)
        print(bin(query(s-1,t)).count('1'))

Submission status: Accepted

Solution code:
import bisect
import sys

input = sys.stdin.readline
num2alpha = lambda c: chr(c + 97)
alpha2num = lambda c: ord(c) - ord("a")


class SegTreeMax:
    def __init__(self, l):
        self.N = 1
        while self.N < l:
            self.N *= 2
        self.L = [0 for _ in range(self.N * 2 - 1)]

    def append(self, k, v):
        k += self.N - 1
        self.L[k] += 2 ** v
        while k > 0:
            k = (k - 1) // 2
            self.L[k] = self.L[k * 2 + 1] | self.L[k * 2 + 2]

    def delete(self, k, v):
        k += self.N - 1
        self.L[k] -= 2 ** v
        while k > 0:
            k = (k - 1) // 2
            self.L[k] = self.L[k * 2 + 1] | self.L[k * 2 + 2]

    def query(self, a, b):
        return self.inquiry(0, self.N, 0, a, b)

    def inquiry(self, l, r, k, a, b):
        if r <= a or l >= b:
            return 0
        if a <= l and b >= r:
            return self.L[k]
        vl = self.inquiry(l, (l + r) // 2, k * 2 + 1, a, b)
        vr = self.inquiry((l + r) // 2, r, k * 2 + 2, a, b)
        return vl | vr


def main():
    N = int(input())
    S = input()
    L = []
    for c in S:
        L.append(c)
    Q = int(input())
    T = SegTreeMax(N)
    for i in range(N):
        T.append(i, alpha2num(L[i]))

    for _ in range(Q):
        a, b, c = input().split()
        if a == "1":
            i = int(b) - 1
            T.delete(i, alpha2num(L[i]))
            L[i] = c
            T.append(i, alpha2num(c))

        else:
            l = int(b) - 1
            r = int(c)
            res = T.query(l, r)
            p = 0
            for i in range(26):
                p += res & 1
                res >>= 1
            print(p)


main()

Submission status: Accepted

Solution code:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21


class Segtree_op():
    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):
        # sum
        return lch + rch

        # update min with holding index
        # if lch[0] <= rch[0]:
        #     return lch
        # else:
        #     return rch

    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 main():
    n = getN()
    s = [c for c in input().strip()]
    q = getN()

    # SegTreeをa-zぶん用意する 3文字目がbならsegs[b]の3番目にフラグ1が立つ
    segs = [Segtree_op(n) for i in range(26)]
    for i, c in enumerate(s):
        segs[ord(c) - ord("a")].update(i, 1)

    for query in range(q):
        operand, a, b = input().split()
        if operand == "1":
            # 0-indexed
            a = int(a) - 1
            segs[ord(s[a]) - ord("a")].update(a, 0)
            segs[ord(b) - ord("a")].update(a, 1)
            s[a] = b

        else:  # operand == "2"
            tmp = 0
            # 0-indexed
            a, b = int(a) - 1, int(b) - 1
            for se in segs:
                # a-zそれぞれのSegTreeについて、区間内にフラグが立っていれば tmp += 1
                # 文字自体ではなくその間にindexが降られているので、右側を+1
                if se.query(a, b+1) > 0:
                    tmp += 1
            print(tmp)

    # print(segs[0].arr)

if __name__ == '__main__':
    main()

"""
7 
aaaabbb
3
1 7 c
2 1 5
2 1 7
>> 2
>> 3


26 
abcdefghijklmnopqrstuvwxyz
7
2 1 26
2 2 26
2 5 5
2 11 20
2 25 26 
1 1 z
2 1 26
>> 26
>> 25
>> 1
>> 10
>> 2
>> 25
"""

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
from string import ascii_lowercase

class BIT(): #1-indexed
    def __init__(self,n): #n: 要素数
        self.size=n
        self.bit=[0]*(n+1)
    def add(self,i,x): #i番目(1-indexed)にxを加算
        while i<=self.size:
            self.bit[i]+=x
            i+=i&-i
    def sum_1_to_i(self,i): #1番目からi番目(含む)までの総和(1-indexed)
        s=0
        while i>0:
            s+=self.bit[i]
            i-=i&-i
        return s
    def sum_i_to_j(self,i,j): #i番目からj番目(含む)までの総和(1-indexed)
        return self.sum_1_to_i(j)-self.sum_1_to_i(i-1)
    def reset(self): #初期化
        self.bit=[0]*(self.size+1)

def main():
    A=ascii_lowercase
    D=dict()
    for i,a in enumerate(A):
        D[a]=i
    n=int(input())
    S=list(input().strip())
    L=[BIT(n) for _ in range(26)]
    for i,s in enumerate(S):
        L[D[s]].add(i+1,1)
    q=int(input())
    for _ in range(q):
        k,a,b=input().split()
        if k=='1':
            i=int(a)-1
            s=S[i]
            L[D[b]].add(i+1,1)
            L[D[s]].add(i+1,-1)
            S[i]=b
        else:
            l=int(a); r=int(b)
            ans=0
            for i in range(26):
                ans+=L[i].sum_i_to_j(l,r)>0
            print(ans)
    
if __name__=='__main__':
    main()