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:
from functools import reduce
import sys
input = sys.stdin.readline


class SegmentTrees:
    def __init__(self, target, no_effect):
        size = len(target)
        length = 1
        while length < size:
            length *= 2
        self.tree_size = length * 2 - 1
        self.tree = [no_effect] * self.tree_size
        self.areas = [[0, 0] for _ in range(self.tree_size)]
        self.set_areas()
        self.initialize_tree_by_target(target, no_effect)
        self.target = target

    def set_areas(self):
        def decide_children_areas(node):
            left, right = self.areas[node]
            center = (left+right)//2
            child1 = node * 2 + 1
            child2 = node * 2 + 2
            self.areas[child1] = [left, center]
            self.areas[child2] = [center+1, right]

        self.areas[0] = [0, self.tree_size//2]
        for parent in range(self.tree_size//2):
            decide_children_areas(parent)

    @classmethod
    def initialize_func(cls, value):
        return 1 << (ord(value) - ord('a'))

    @classmethod
    def merge_func(cls, a, b):
        return a | b

    def merge_child_data(self, node):
        child1 = node * 2 + 1
        child2 = node * 2 + 2
        merged = self.merge_func(self.tree[child1], self.tree[child2])
        return merged

    def initialize_tree_by_target(self, target: list, no_effect=0):
        def calc_leafs():
            initial_leaf = self.tree_size//2
            leafs = range(initial_leaf, initial_leaf+len(target))
            for value, leaf in zip(target, leafs):
                self.tree[leaf] = self.initialize_func(value)

            residue = range(initial_leaf+len(target), self.tree_size)
            for residual_leaf in residue:
                self.tree[residual_leaf] = no_effect

        calc_leafs()
        for parent in range(self.tree_size//2-1, -1, -1):
            self.tree[parent] = self.merge_child_data(parent)

    def update(self, new_data, position):
        leaf = self.tree_size//2 + position
        new = self.initialize_func(new_data)
        if self.tree[leaf] == new:
            return
        self.tree[leaf] = new
        parent = (leaf-1) // 2
        while parent >= 0:
            new = self.merge_child_data(parent)
            if self.tree[parent] == new:
                break
            self.tree[parent] = new
            parent = (parent-1) // 2

    def get_query(self, _from, to):
        def get_tree_data(node):
            left, right = self.areas[node]
            if _from <= left and right <= to:
                result.append(self.tree[node])
                return
            if to < left or right < _from:
                return

            child1 = node * 2 + 1
            child2 = node * 2 + 2
            get_tree_data(child1)
            get_tree_data(child2)

        result = []
        get_tree_data(0)
        ans = reduce(self.merge_func, result)
        ans = bin(ans).count('1')
        return ans


n = int(input())
S = input().replace('\n', '')
seg_tree = SegmentTrees(target=S, no_effect=0)

Q = int(input())
for _ in range(Q):
    query = input().split()
    if query[0] == '1':
        position, new = int(query[1])-1, query[2]
        seg_tree.update(new, position)

    elif query[0] == '2':
        _from, to = int(query[1])-1, int(query[2])-1
        print(seg_tree.get_query(_from, to))

Submission status: Accepted

Solution code:

def s_in():
    return input()

def n_in():
    return int(input())

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

class SegmentTree():
    def __init__(self, n, init_val, segfunc, unifunc):
        self.n = n
        self.size = 2**(n-1).bit_length()
        self.segfunc = segfunc
        self.unifunc = unifunc

        self.seg = [unifunc() for _ in range(2*self.size)]

        for i in range(self.n):
            self.seg[i+self.size-1] = init_val[i]

        for i in range(self.size-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])


    def update(self, k, x):
        k += self.size-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, q)
        if q <= p:
            return self.unifunc()
        p += self.size-1
        q += self.size-2
        res = self.unifunc()

        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

n = n_in()
S = s_in()
Q = n_in()


dic={i:j for i,j in zip('abcdefghijklmnopqrstuvwxyz',[2**i for i in range(26)])}

T = SegmentTree(n,
    [dic[s] for s in S],
    lambda x,y: x|y,
    lambda: 0
    )

for _ in range(Q):
    n, i, j = input().split()
    if int(n) == 1:
        T.update(int(i)-1, dic[j])
    else:
        print(bin(T.query(int(i)-1, int(j))).count('1'))

Submission status: Accepted

Solution code:
import sys
from operator import or_
sys.setrecursionlimit(10 ** 7)

# AC
# Python3 (3.4.3) 696 ms
# PyPy3 (2.4.0) 1572 ms


class SegmentTree:
    """
    引数：
        N: 処理する区間の長さ
        operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
        UNIT: 単位元
        a: 長さNの配列 a で初期化（a を与えない場合、単位元で初期化）
    注意: 内部的には 1-indexed
    """

    def __init__(self, N, operator, unit, a=None):
        self.op = operator
        self.UNIT = unit

        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.UNIT]*(2*self.N0)
        if a != None:
            self.tree[self.N0:self.N0+N] = a[:]
            for k in range(self.N0-1, 0, -1):
                self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])

    # a_k の値を x に更新
    def update(self, k, x):
        k += self.N0
        self.tree[k] = x
        k //= 2
        while k:
            self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
            k //= 2

    # 区間[l,r)をopでまとめる
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = self.UNIT
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(self.tree[R], s)
            if L & 1:
                s = self.op(s, self.tree[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get(self, k):  # k番目の値を取得。query[k,k]と同じ
        return self.tree[k + self.N0]

    def all(self):
        return self.tree[1]


N = int(input())
S = input()
S = [1 << (ord(x) - 97) for x in S]

seg = SegmentTree(N, or_, 0, S)

Q = int(input())

ans = []
for _ in range(Q):
    q, a, b = input().split()

    if q == '1':
        b = 1 << (ord(b) - 97)
        seg.update(int(a) - 1, b)
    else:
        r = seg.query(int(a) - 1, int(b))
        cnt = 0

        for i in range(26):
            if r & (1 << i):
                cnt += 1

        ans.append(str(cnt))


print("\n".join(ans))

Submission status: Accepted

Solution code:
import sys
from operator import or_
sys.setrecursionlimit(10 ** 7)

# AC
# Python3 (3.4.3) TLE
# PyPy3 (2.4.0) 1572 ms


class SegmentTree:
    """
    引数：
        N: 処理する区間の長さ
        operator: モノイド演算 (max, min, __add__,ラムダ式,関数定義など)
        UNIT: 単位元
        a: 長さNの配列 a で初期化（a を与えない場合、単位元で初期化）
    注意: 内部的には 1-indexed
    """

    def __init__(self, N, operator, unit, a=None):
        self.op = operator
        self.UNIT = unit

        self.N0 = 2**(N-1).bit_length()
        self.tree = [self.UNIT]*(2*self.N0)
        if a != None:
            self.tree[self.N0:self.N0+N] = a[:]
            for k in range(self.N0-1, 0, -1):
                self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])

    # a_k の値を x に更新
    def update(self, k, x):
        k += self.N0
        self.tree[k] = x
        k //= 2
        while k:
            self.tree[k] = self.op(self.tree[2*k], self.tree[2*k+1])
            k //= 2

    # 区間[l,r)をopでまとめる
    def query(self, l, r):
        L = l + self.N0
        R = r + self.N0
        s = self.UNIT
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(self.tree[R], s)
            if L & 1:
                s = self.op(s, self.tree[L])
                L += 1
            L >>= 1
            R >>= 1
        return s

    def get(self, k):  # k番目の値を取得。query[k,k]と同じ
        return self.tree[k + self.N0]

    def all(self):
        return self.tree[1]


N = int(input())
S = input()
S = [1 << (ord(x) - 97) for x in S]

seg = SegmentTree(N, or_, 0, S)

Q = int(input())

ans = []
for _ in range(Q):
    q, a, b = input().split()

    if q == '1':
        b = 1 << (ord(b) - 97)
        seg.update(int(a) - 1, b)
    else:
        r = seg.query(int(a) - 1, int(b))
        cnt = 0

        for i in range(26):
            if r & (1 << i):
                cnt += 1

        ans.append(str(cnt))


print("\n".join(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

class SegTree:
    """
    セグメント木
    1.update:  i番目の値をxに更新する
    2.query: 区間[l, r)の値を得る
    """

    def __init__(self, n, func, intv, A=[]):
        """
        :param n: 要素数(0-indexed)
        :param func: 値の操作に使う関数(min, max, add, gcdなど)
        :param intv: 要素の初期値(単位元)
        :param A: 初期化に使うリスト(オプション)
        """
        self.n = n
        self.func = func
        self.intv = intv
        # nより大きい2の冪数
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [self.intv] * (n2 << 1)
        # 初期化の値が決まっている場合
        if A:
            # 1段目(最下段)の初期化
            for i in range(n):
                self.tree[n2+i] = A[i]
            # 2段目以降の初期化
            for i in range(n2-1, -1, -1):
                self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def update(self, i, x):
        """
        i番目の値をxに更新
        :param i: index(0-indexed)
        :param x: update value
        """
        i += self.n2
        self.tree[i] = x
        while i > 0:
            i >>= 1
            self.tree[i] = self.func(self.tree[i*2], self.tree[i*2+1])

    def query(self, a, b):
        """
        [a, b)の値を得る
        :param a: index(0-indexed)
        :param b: index(0-indexed)
        """
        l = a + self.n2
        r = b + self.n2
        s = self.intv
        while l < r:
            if r & 1:
                r -= 1
                s = self.func(s, self.tree[r])
            if l & 1:
                s = self.func(s, self.tree[l])
                l += 1
            l >>= 1
            r >>= 1
        return s

    def get(self, i):
        """ 一点取得 """
        return self.tree[i+self.n2]

    def all(self):
        """ 全区間[0, n)の取得 """
        return self.tree[1]

    def print(self):
        for i in range(self.n):
            print(self.get(i), end=' ')
        print()

def popcount(i):
    i = i - ((i >> 1) & 0x55555555)
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333)
    i = (i + (i >> 4)) & 0x0f0f0f0f
    i = i + (i >> 8)
    i = i + (i >> 16)
    return i & 0x3f

N = INT()
S = [ord(c)-97 for c in input()]
st = SegTree(N, lambda a, b: a | b, 0, [1<<s for s in S])

Q = INT()
for _ in range(Q):
    q = list(input().split())
    if q[0] == '1':
        _, i, c = q
        i = int(i) - 1
        c = ord(c) - 97
        if S[i] != c:
            prev = S[i]
            S[i] = c
            st.update(i, (st.get(i) | 1<<c) ^ 1<<prev)
    else:
        _, l, r = q
        l, r = int(l) - 1, int(r) - 1
        ans = popcount(st.query(l, r+1))
        print(ans)

Submission status: Accepted

Solution code:

# # # # class Segtree # # # #

#      0
#   1     2
# 3   4  5  6
#       :
# leaf i - n-1+i
# parent   - (i-1)//2
# children - 2*i+1, 2*i+2

class Segtree:
    # modify UNIT and oper depending on the reduce operation

    UNIT = 0  # sum:0 min:BIG max:-BIG gcd:1 lcm:0 ..

    @classmethod
    def oper(c,x,y):
        return x|y  # sum:+ min/max/gcd/lcm:(same)

    def __init__(s,l):
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [Segtree.UNIT for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = Segtree.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = Segtree.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        return s.querycore(x,y,0,0,s.n)

    # x,y: from query  k: suffix at focus l,r: range for k
    # right ends (y,r) not included

    def querycore(s,x,y,k,l,r):
        if r<=x or y<=l:
            return Segtree.UNIT
        if x<=l and r<=y:
            return s.ary[k]
        vl = s.querycore(x,y,2*k+1,l,(l+r)//2)
        vr = s.querycore(x,y,2*k+2,(l+r)//2,r)
        return Segtree.oper(vl, vr)

# # # # class Segtree end # # # #

inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()

n = inn()
sgt = Segtree(n)
ss = ins()
s = []
for i in range(n):
    sgt.set(i, 1<<(ord(ss[i])-ord('a')))

#ddprint("tree")
#for c in alpha:
#    ddprint(c)
#    ddprint(tr[c])

q = inn()
for qq in range(q):
    x,y,z = input().split()
    #ddprint(f"x {x} y {y} z {z}")
    if x == '1':
        i = int(y)-1
        c = z
        sgt.set(i, 1<<(ord(c)-ord('a')))
    else:
        l = int(y)
        r = int(z)
        sm = 0
        v = sgt.query(l-1,r)
        for i in range(26):
            if (v>>i)%2==1:
                sm += 1
        print(sm)

Submission status: Accepted

Solution code:
class SegmentTree():

    def __init__(self,init_val,n,func): #init_valは長さnの配列 O(2*n)
        self.unit=0
        self.size=pow(2,n-1).bit_length() #n以上の最小の2のべき乗
        self.seg=[self.unit]*2*self.size #セグメントツリー本体
        self.f=func #セグ木により異なる関数
        
        for i in range(n):
            self.seg[i+self.size-1]=init_val[i] 
        
        for i in range(self.size-2,-1,-1):
            self.seg[i]=self.f(self.seg[2*i+1],self.seg[2*i+2])
    
    def update(self,k,x): #k番目の要素をxに変更する O(logN)
        k+=self.size-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.f(self.seg[2*k+1],self.seg[2*k+2])
    
    def query(self,p,q): #[p,q)のクエリに答える　半開区間であることに注意 O(logN)
        if q<=p:
            return self.unit

        p+=self.size-1
        q+=self.size-2
        res=self.unit

        while q-p>1:

            if (p&1)==0:
                res=self.f(res,self.seg[p])

            if (q&1)==1:
                res=self.f(res,self.seg[q])
                q-=1
            p//=2
            q=(q-1)//2
        
        if p==q:
            res=self.f(res,self.seg[p])
        else:
            res=self.f(self.f(res,self.seg[p]),self.seg[q])
        
        return bin(res).count('1')

def main():
    n=int(input())
    s=input()

    dic={i:j for i,j in zip('abcdefghijklmnopqrstuvwxyz',[2**i for i in range(26)])}
    l=[0]*n

    for i in range(n):
        l[i]=dic[s[i]]
    
    def f(x,y):
        return x|y

    st=SegmentTree(l,n,f)
    
    q=int(input())
    for _ in range(q):
        a=list(map(str,input().split()))
        a[0]=int(a[0])

        if a[0]==1:
            a[1]=int(a[1])
            st.update(a[1]-1,dic[a[2]])
        
        else:
            a[1]=int(a[1])-1
            a[2]=int(a[2])
            print(st.query(a[1],a[2]))
            
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
class SegmentTree():

    def __init__(self,init_val,n,func): #init_valは長さnの配列 O(2*n)
        self.ide_ele=0
        self.num=pow(2,n-1).bit_length() #n以上の最小の2のべき乗
        self.seg=[self.ide_ele]*2*self.num #セグメントツリー本体
        self.f=func

        for i in range(n):
            self.seg[i+self.num-1]=init_val[i] 
        
        for i in range(self.num-2,-1,-1):
            self.seg[i]=(self.seg[2*i+1])|(self.seg[2*i+2])        
        
      
    def update(self,k,x): #k番目の要素をxに変更する O(logN)
        k+=self.num-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=self.f(self.seg[2*k+1],self.seg[2*k+2])
    
    def query(self,p,q): #[p,q)のクエリに答える O(logN)
        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.f(res,self.seg[p])

            if (q&1)==1:
                res=self.f(res,self.seg[q])
                q-=1
            p//=2
            q=(q-1)//2
        
        if p==q:
            res=self.f(res,self.seg[p])
        else:
            res=self.f(self.f(res,self.seg[p]),self.seg[q])
        
        return bin(res).count('1')

def main():
    n=int(input())
    s=input()

    dic={i:j for i,j in zip('abcdefghijklmnopqrstuvwxyz',[2**i for i in range(26)])}
    l=[0]*n

    for i in range(n):
        l[i]=dic[s[i]]
    
    def f(x,y):
        return x|y

    st=SegmentTree(l,n,f)
    
    q=int(input())
    for _ in range(q):
        a=list(map(str,input().split()))
        a[0]=int(a[0])

        if a[0]==1:
            a[1]=int(a[1])
            st.update(a[1]-1,dic[a[2]])
        
        else:
            a[1]=int(a[1])-1
            a[2]=int(a[2])
            print(st.query(a[1],a[2]))
            
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
Q = int(input())
query = [input().split() for _ in range(Q)]

bit = [[0 for _ in range(26)] for _ in range(N + 1)]

def bit_add(i, s, x):
    j = ord(s) - ord("a")
    while i <= N:
        bit[i][j] += x
        i += i & - i
        
def bit_sum(i):
    s = [0] * 26
    while i:
        for j in range(26):
            s[j] += bit[i][j]
        i -= i & -i
    return s
  
for i in range(1, N + 1):
    s = S[i - 1]
    bit_add(i, s, 1)

for x, y, z in query:
    if x == "1":
        y = int(y)
        bit_add(y, S[y - 1], -1)
        bit_add(y, z, 1)
        S[y - 1] = z
    if x == "2":
        answer = 0
        y, z = int(y) - 1, int(z)
        sum_y = bit_sum(y)
        sum_z = bit_sum(z)
        for i in range(26):
            if sum_z[i] - sum_y[i] > 0:
                answer += 1
        print(answer)

Submission status: Accepted

Solution code:
class SegmentTree():

    def __init__(self,init_val,n): #init_valは長さnの配列 O(2*n)
        self.n=n
        self.ide_ele=0
        self.num=pow(2,n-1).bit_length() #n以上の最小の2のべき乗
        self.seg=[self.ide_ele]*2*self.num #セグメントツリー本体
        
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i] 
        
        for i in range(self.num-2,-1,-1):
            self.seg[i]=(self.seg[2*i+1])|(self.seg[2*i+2])        
        
      
    def update(self,k,x): #k番目の要素をxに変更する O(logN)
        k+=self.num-1
        self.seg[k]=x
        while k:
            k=(k-1)//2
            self.seg[k]=(self.seg[2*k+1])|(self.seg[2*k+2])
    
    def query(self,p,q): #[p,q)のクエリに答える O(logN)
        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.seg[p]

            if (q&1)==1:
                res|=self.seg[q]
                q-=1
            p//=2
            q=(q-1)//2
        
        if p==q:
            res|=self.seg[p]
        else:
            res=(res|self.seg[p])|self.seg[q]
        
        return bin(res).count('1')

def main():
    n=int(input())
    s=input()

    dic={i:j for i,j in zip('abcdefghijklmnopqrstuvwxyz',[2**i for i in range(26)])}
    l=[0]*n

    for i in range(n):
        l[i]=dic[s[i]]

    st=SegmentTree(l,n)
    
    q=int(input())
    for _ in range(q):
        a=list(map(str,input().split()))
        a[0]=int(a[0])

        if a[0]==1:
            a[1]=int(a[1])
            st.update(a[1]-1,dic[a[2]])
        
        else:
            a[1]=int(a[1])-1
            a[2]=int(a[2])
            print(st.query(a[1],a[2]))
            
if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
class OR_seg:
    def __init__(self,n,init_val,ide_ele = 0):
        # set_val
        self.ide_ele = ide_ele
        self.n = n
        self.num = 2 ** (self.n - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]
            # built
        for i in range(self.num - 2, -1, -1):
            self.seg[i] = 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.seg[2 * k + 1] | self.seg[2 * k + 2]

    def add(self,k, x):
        k += self.num - 1
        self.seg[k] += x
        while k + 1:
            k = (k - 1) // 2
            self.seg[k] = self.seg[2 * k + 1] | self.seg[2 * k + 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.seg[p]

            if q & 1 == 1:
                res |= self.seg[q]
                q -= 1
            p = p // 2
            q = (q - 1) // 2

        res = res | self.seg[p]|self.seg[q]

        return res
def bit_count(x): #立ってるビットの本数を出力
    n = 0
    while x:
        n += 1
        x &= x-1

    return n

alpha_small_dict = {chr(i):i-97 for i in range(97, 97+26)} #辞書ver
n = int(input())
S = input()
init = [2**alpha_small_dict[x] for x in S]
#print(init)
seg = OR_seg(n,init)
q = int(input())
for i in range(q):
    x,y,z = input().split()
    x,y = int(x),int(y)
    #print(x,y,z)
    if x == 1:
        num = alpha_small_dict[z]
        seg.update(y-1,2**num)
    else:
        z = int(z)
        ans = seg.query(y-1,z)
        print(bit_count(ans))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

class BinaryIndexedTree:
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size
 
    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return
 
    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res
 
    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i
 
    def __len__(self):
        return self.size

n = I()
s = list(input())

lst = [BinaryIndexedTree(n+1) for _ in range(26)]
S = [ord(i) - ord("a") for i in s]

for i in range(n):
    lst[S[i]].add(i+1,1)

q = I()
for _ in range(q):
    query = input().split()
    if query[0] == '1':
        i,c = query[1:]
        i = int(i)-1
        lst[S[i]].add(i+1,-1)
        lst[ord(c) - ord("a")].add(i+1,1)
        S[i] = ord(c) - ord("a")
    else:
        l,r = query[1:]
        l = int(l)-1
        r = int(r)-1
        cnt = 0
        for i in range(26):
            if lst[i].sum(r+1) - lst[i].sum(l) > 0:
                cnt += 1
        print(cnt)

Submission status: Accepted

Solution code:
from collections import *
from itertools import *
from bisect import *
from heapq import *
import copy
import math


#N,K=map(int,input().split())
N=int(input())
S=input()
Q=int(input())
Query=[input().split() for i in range(Q)]

def segfunc(x,y):
    return (x|y)

def init(init_val):
    #set_val
    for i in range(n):
        seg[i+num-1]=init_val[i]
    #built
    for i in range(num-2,-1,-1) :
        seg[i]=seg[2*i+1]|seg[2*i+2]

def update(k,b):
    k += num-1
    if seg[k]=={b}:
        return ()
    seg[k] = {b}
    while k:
        k = (k-1)>>1
        seg[k] = 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=set()
    while q-p>1:
        if p&1 == 0:
            res = res|seg[p]
        if q&1 == 1:
            res = res|seg[q]
            q -= 1
        p = p>>1
        q = (q-1)>>1
    if p == q:
        res = res|seg[p]
    else:
        res = res|seg[p]|seg[q]
    return res

#num:n以上の最小の2のべき乗
n=N
num =2**(n-1).bit_length()
seg=[set()] * (2*num)

for i in range(N):
    seg[i+num-1]={ord(S[i])}
for k in range(num-2,-1,-1):
    seg[k] = seg[k*2+1]|seg[k*2+2]
for type, i, c in Query:
    if type=="1":
        update(int(i)-1,ord(c))
    else:
        print(len(query(int(i)-1,int(c))))
    #print(seg)

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

class SegTree:
    def __init__(self,aa):
        n=1<<(len(aa)-1).bit_length()
        tree=[0]*(2*n-1)
        tree[n-1:n-1+len(aa)]=aa
        for i in range(n-2,-1,-1):tree[i]=tree[2*i+1]|tree[2*i+2]
        self.tree=tree
        self.n=n

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

    def SegOr(self,l,r,i=0,segl=0,segr=-1):
        if segr==-1:segr=self.n
        if r<=segl or segr<=l:return 0
        if l<=segl and segr<=r:return self.tree[i]
        m=(segl+segr)//2
        return self.SegOr(l,r,2*i+1,segl,m)|self.SegOr(l,r,2*i+2,m,segr)

def main():
    code=lambda c:ord(c)-ord("a")
    popcnt=lambda x:bin(x).count("1")
    n=II()
    s=SI()
    aa=[1<<code(c) for c in s]
    st=SegTree(aa)
    q=II()
    for _ in range(q):
        op,x,y=SI().split()
        if op=="1":
            i=int(x)-1
            st.update(i,1<<code(y))
        else:
            l,r=int(x)-1,int(y)
            print(popcnt(st.SegOr(l,r)))

main()