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:
def segfunc(x,y):
  return x|y

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): #これで[l,r)から取り出す。
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)


N = int(input())
S = str(input());Q = int(input())
A = []
for i in range(N):
  temp = S[i]
  num = ord(temp) - 97
  A.append(pow(2,num))
Tree = SegmentTree(A, segfunc, 0)
for i in range(Q):
  query = list(map(str,input().split()))
  if query[0] == "1":
    loc = int(query[1])-1 #0index
    num = ord(query[2])-97
    Tree.update(loc,pow(2,num))
  else:
    left = int(query[1])-1
    right = int(query[2])-1
    ret = Tree.sum(left,right+1)
    ans = 0
    for j in range(26):
      if (ret>>j)&1 == 1:
        ans += 1
    print(ans)

Submission status: Accepted

Solution code:

class Bit:
    """ used for only int(>=0) 
        1-indexed (ignore 0-index)
    """
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length()
 
    def sum(self, i):
        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

    def lower_bound(self, x):
        """ 累積和がx以上になる最小のindexと、その直前までの累積和 """
        sum_ = 0
        pos = 0
        for i in range(self.depth, -1, -1):
            k = pos + (1 << i)
            if k <= self.size and sum_ + self.tree[k] < x:
                sum_ += self.tree[k]
                pos += 1 << i
        return pos + 1, sum_

    def get_less_than_x_cnt(self, x):
        """ 累積和がx未満 の個数 """
        lb_pos, lb_sum = self.lower_bound(x)
        return lb_pos-1

    def get_less_than_and_x_cnt(self, x):
        """ 累積和がx以下 の個数 """
        lb_pos, lb_sum = self.lower_bound(x+1)
        return lb_pos-1
    
    def get_more_than_x_cnt(self, x):
        """ 累積和がxより大きい 個数 """
        return self.size - self.get_less_than_and_x_cnt(x)


def main():
    n = int(input())
    s = list(input())
    q = int(input())
    ql = []
    for _ in range(q): 
        num,a,b = map(str, input().split())
        ql.append((num,a,b))
    alp_d = {chr(ord('a') + i): Bit(n) for i in range(26)}

    for i, si in enumerate(s):
        alp_d[si].add(i+1,1)

    for query in ql:
        a,b,c = query
        if a == '1':
            b = int(b)
            before = s[b-1]
            alp_d[before].add(b, -1)
            alp_d[c].add(b,1)
            s[b-1] = c
        else:
            l,r = int(b),int(c)
            cnt = 0
            for v in alp_d.values():
                if v.sum(r)-v.sum(l-1) > 0:
                    cnt += 1
            print(cnt) 


if __name__ == "__main__":
    main()

Submission status: Accepted

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

class Bit:
    # Binary Indexed Tree
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def __iter__(self):
        psum = 0
        for i in range(self.size):
            csum = self.sum(i + 1)
            yield csum - psum
            psum = csum
        raise StopIteration()

    def __str__(self):  # O(nlogn)
        return str(list(self))

    def sum(self, i):
        # [0, i) の要素の総和を返す
        if not (0 <= i <= self.size): raise ValueError("error!")
        s = 0
        while i>0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        if not (0 <= i < self.size): raise ValueError("error!")
        i += 1
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

    def __getitem__(self, key):
        if not (0 <= key < self.size): raise IndexError("error!")
        return self.sum(key+1) - self.sum(key)

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

(n,), (s,), _, *q = map(str.split, open(0))
*s, = s
BIT = [Bit(int(n)) for _ in [0] * 26]
for e, t in enumerate(s):
    BIT[ord(t) - 97].add(e, 1)
for a, b, c in q:
    if a == "1":
        i = int(b)
        BIT[ord(s[i - 1]) - 97].add(i - 1, -1)
        s[i - 1] = c
        BIT[ord(c) - 97].add(i - 1, 1)
    else:
        l, r = int(b), int(c)
        print(sum(BIT[i].sum(r) - BIT[i].sum(l - 1) > 0 for i in range(26)))

Submission status: Accepted

Solution code:
N = int(input())
S = input()
Q = int(input())
QUERY = [input().split() for _ in range(Q)]
# N = 4
# S = "abcd"
# QUERY = [s.split() for s in [
#     "2 1 4", # 4
#     "2 1 3", # 3
#     "2 3 4", # 2
#     "2 4 4", # 1
#     "1 2 a", # aacd
#     "2 1 2", # 1
#     "2 1 3", # 2
# ]]
# Q = len(QUERY)

def or_more_pow_two(n):
    if (n & (n-1)) == 0:
        return n
    return 1<<(len(bin(n))-2)

class SegmentTree:
    def __init__(self, n, l):
        self.n = or_more_pow_two(n)*2
        self.tree = [0]*self.n
        for i, l_i in enumerate(l):
            self.tree[self.n//2+i] = l_i
        for i in reversed(range(1, self.n//2)):
            self.node_update(i)
            # print(self.tree[i])

    # 1-indexed: [l, r)
    def find(self, l, r, fl=1, fr="self.n//2+1", node=1):
        if fr == "self.n//2+1":
            fr = self.n//2+1
        # print(f"find: ({l}, {r}), ({fl}, {fr}), {node}")
        if l <= fl and fr <= r:
            # print("in", bin(self.tree[node])[2:])
            return self.tree[node]
        elif fr <= l or r <= fl:
            # print("out")
            return 0
        else:
            # print("overlap")
            mid = (fl+fr)//2
            a = self.find(l, r, fl=fl, fr=mid, node=2*node)
            b = self.find(l, r, fl=mid, fr=fr, node=2*node+1)
            return a | b

    def update(self, index, v):
        # print("update:", index, v)
        x = self.n//2+index-1
        self.tree[x] = v
        while x > 0:
            x >>= 1
            self.node_update(x)

    def node_update(self, index):
        # print(index, [2*index, 2*index+1], list(map(bin, [self.tree[2*index], self.tree[2*index+1], self.tree[2*index] | self.tree[2*index+1]])))
        self.tree[index] = self.tree[2*index] | self.tree[2*index+1]

def char_to_bit(c):
    i = ord(c) - 97
    return (1 << i)
def bit_to_type_count(b):
    # print(bin(b)[2:])
    r = bin(b)[2:].count("1")
    # print(r)
    return r
# def bit_to_char(b):
#     for i in range(26):


segtree = SegmentTree(N, map(char_to_bit, S))

for t, *query in QUERY:
    t = int(t)
    if t == 1:
        i, c = query
        i, c = int(i), c
        segtree.update(i, char_to_bit(c))
    elif t == 2:
        l, r = map(int, query)
        l, r = l, r+1
        r = segtree.find(l, r)
        r = bit_to_type_count(r)
        print(r)
    # print(list(map(bin, segtree.tree)))

Submission status: Accepted

Solution code:
class Binary_Indexed_Tree:
    def __init__(self, n):
        """
        :param n: 最大の要素数
        """
        self.n = n
        self.tree = [0] * (n + 1)
        self.depth = n.bit_length() - 1

    def sum(self, i):
        """ 区間[0,i) の総和を求める """
        s = 0
        i -= 1
        while i >= 0:
            s += self.tree[i]
            i = (i & (i + 1)) - 1
        return s

    def built(self, array):
        """ array を初期値とするBITを構築 """
        for i, a in enumerate(array):
            self.add(i, a)

    def add(self, i, x):
        """ i 番目の要素に x を足す """
        while i < self.n:
            self.tree[i] += x
            i |= i + 1

    def get(self, i, j):
        """ 部分区間和 [i, j) """
        if i == 0:
            return self.sum(j)
        return self.sum(j) - self.sum(i)

    def lower_bound(self, x, equal=False):
        """ (a0+a1+...+ai < x となる最大の i, その時の a0+a1+...+ai )
             a0+a1+...+ai <= x としたい場合は equal = True
             二分探索であるため、ai>=0 を満たす必要がある"""
        sum_ = 0
        pos = -1    # 1-indexed の時は pos = 0
        if not equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] < x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        if equal:
            for i in range(self.depth, -1, -1):
                k = pos + (1 << i)
                if k < self.n and sum_ + self.tree[k] <= x:  # 1-indexed の時は k <= self.n
                    sum_ += self.tree[k]
                    pos += 1 << i
        return pos, sum_

    def __getitem__(self, i):
        """ [a0, a1, a2, ...] """
        return self.get(i, i + 1)

    def __iter__(self):
        """ [a0, a1, a2, ...] """
        for i in range(self.n):
            yield self.get(i, i + 1)

    def __str__(self):
        text1 = " ".join(["element:            "] + list(map(str, self)))
        text2 = " ".join(["cumsum(1-indexed):  "] + list(str(self.sum(i)) for i in range(1, self.n + 1)))
        return "\n".join((text1, text2))


def str2int(s):
    return ord(s) - ord("a")


n = int(input())
s = [str2int(i) for i in input()]
B = [Binary_Indexed_Tree(n) for i in range(26)]

for i in range(n):
    B[s[i]].add(i, 1)

for _ in range(int(input())):
    t, a, b = input().split()
    if t == "1":
        a = int(a) - 1
        b = str2int(b)
        B[s[a]].add(a, -1)
        B[b].add(a, 1)
        s[a] = b
    else:
        a, b = int(a) - 1, int(b)
        ans = 0
        for v in B:
            ans += v.get(a, b) > 0
        print(ans)

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
from copy import deepcopy
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return S().split()
def S(): return sys.stdin.readline().strip()
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)]
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)


n = I()
s = list(S())
q = I()
D = defaultdict(lambda:BIT(n))
for j in range(n):
    D[s[j]].add(j, 1)

for _ 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)
        ret = 0
        for k in range(97, 123):
            if D[chr(k)].interval_sum(l, r):
                ret += 1
        print(ret)

Submission status: Accepted

Solution code:
from collections import deque

class SegmentTree():
    def __init__(self,n,ide_ele,merge_func,init_val):
        self.n=n
        self.ide_ele=ide_ele
        self.merge_func=merge_func
        self.val=[0 for i in range(1<<n)]
        self.merge=[0 for i in range(1<<n)]
        self.parent=[-1 for i in range(1<<n)]
        deq=deque([1<<(n-1)])
        res=[]
        while deq:
            v=deq.popleft()
            res.append(v)
            if not v&1:
                gap=(v&-v)//2
                self.parent[v-gap]=v
                deq.append(v-gap)
                self.parent[v+gap]=v
                deq.append(v+gap)
        for v in res[::-1]:
            if v-1<len(init_val):
                self.val[v-1]=init_val[v-1]
            self.merge[v-1]=self.val[v-1]
            if not v&1:
                gap=(v&-v)//2
                self.merge[v-1]=self.merge_func(self.merge[v-1],self.merge[v-gap-1],self.merge[v+gap-1])

    def update(self,id,x):
        self.val[id]=x
        pos=id+1
        while pos!=-1:
            if pos&1:
                self.merge[pos-1]=self.val[pos-1]
            else:
                gap=(pos&-pos)//2
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos+gap-1],self.merge[pos-gap-1])
            pos=self.parent[pos]

    def lower_kth_merge(self,nd,k):
        if k==-1:
            return self.ide_ele
        mini=nd-(nd&-nd)+1+k
        id=nd
        stack=[]
        while True:
            gap=(id&-id)//2
            if id>mini:
                id-=gap
            elif id==mini:
                stack.append(self.val[id-1])
                stack.append(self.merge[id-gap-1])
                return self.merge_func(*stack)
            else:
                stack.append(self.val[id-1])
                stack.append(self.merge[id-gap-1])
                id+=gap

    def upper_kth_merge(self,nd,k):
        if k==-1:
            return self.ide_ele
        maxi=nd+(nd&-nd)-1-k
        id=nd
        stack=[]
        while True:
            gap=(id&-id)//2
            if id>maxi:
                stack.append(self.val[id-1])
                stack.append(self.merge[id+gap-1])
                id-=gap
            elif id==maxi:
                stack.append(self.val[id-1])
                stack.append(self.merge[id+gap-1])
                return self.merge_func(*stack)
            else:
                id+=gap

    def query(self,l,r):
        id=1<<(self.n-1)
        while True:
            if id-1<l:
                id+=((id)&(-id))//2
            elif id-1>r:
                id-=((id)&(-id))//2
            else:
                res=self.val[id-1]
                if id%2:
                    return res
                gap=((id)&(-id))//2
                L,R=id-gap,id+gap
                #print(l,r,id,L,R)
                left=self.upper_kth_merge(L,id-1-l-1)
                right=self.lower_kth_merge(R,r-id)
                return self.merge_func(res,left,right)

ide_ele=0

def seg_func(*args):
    res=ide_ele
    for val in args:
        res|=val
    return res

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

import sys

input=sys.stdin.readline

N=int(input())
S=input().rstrip()

init_val=[1<<(ord(S[i])-97) for i in range(N)]
test=SegmentTree(N.bit_length(),ide_ele,seg_func,init_val)

for _ in range(int(input())):
    t,l,r=input().split()
    t,l=int(t),int(l)
    if t==1:
        val=ord(r)-97
        test.update(l-1,1<<val)
    else:
        r=int(r)
        res=test.query(l-1,r-1)
        print(popcount(res))

Submission status: Accepted

Solution code:
from collections import deque

class SegmentTree():
    def __init__(self,n,ide_ele,merge_func,init_val):
        self.n=n
        self.ide_ele=ide_ele
        self.merge_func=merge_func
        self.val=[0 for i in range(1<<n)]
        self.merge=[0 for i in range(1<<n)]
        self.parent=[-1 for i in range(1<<n)]
        deq=deque([1<<(n-1)])
        res=[]
        while deq:
            v=deq.popleft()
            res.append(v)
            if not v&1:
                gap=(v&-v)//2
                self.parent[v-gap]=v
                deq.append(v-gap)
                self.parent[v+gap]=v
                deq.append(v+gap)
        for v in res[::-1]:
            if v-1<len(init_val):
                self.val[v-1]=init_val[v-1]
            self.merge[v-1]=self.val[v-1]
            if not v&1:
                gap=(v&-v)//2
                self.merge[v-1]=self.merge_func(self.merge[v-1],self.merge[v-gap-1],self.merge[v+gap-1])

    def update(self,id,x):
        self.val[id]=x
        pos=id+1
        while pos!=-1:
            if pos&1:
                self.merge[pos-1]=self.val[pos-1]
            else:
                gap=(pos&-pos)//2
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos+gap-1],self.merge[pos-gap-1])
            pos=self.parent[pos]

    def cnt(self,k):
        lsb=(k)&(-k)
        return (lsb<<1)-1

    def lower_kth_merge(self,nd,k):
        res=self.ide_ele
        if k==-1:
            return res
        mini=nd-(nd&-nd)+1+k
        id=nd
        while True:
            gap=(id&-id)//2
            if id>mini:
                id-=gap
            elif id==mini:
                return self.merge_func(res,self.val[id-1],self.merge[id-gap-1])
            else:
                res=self.merge_func(res,self.val[id-1],self.merge[id-gap-1])
                id+=gap

    def upper_kth_merge(self,nd,k):
        res=self.ide_ele
        if k==-1:
            return res
        maxi=nd+(nd&-nd)-1-k
        id=nd
        while True:
            gap=(id&-id)//2
            if id>maxi:
                res=self.merge_func(res,self.val[id-1],self.merge[id+gap-1])
                id-=gap
            elif id==maxi:
                return self.merge_func(res,self.val[id-1],self.merge[id+gap-1])
            else:
                id+=gap

    def query(self,l,r):
        id=1<<(self.n-1)
        while True:
            if id-1<l:
                id+=((id)&(-id))//2
            elif id-1>r:
                id-=((id)&(-id))//2
            else:
                res=self.val[id-1]
                if id%2:
                    return res
                gap=((id)&(-id))//2
                L,R=id-gap,id+gap
                #print(l,r,id,L,R)
                left=self.upper_kth_merge(L,id-1-l-1)
                right=self.lower_kth_merge(R,r-id)
                return self.merge_func(res,left,right)

ide_ele=0

def seg_func(*args):
    res=ide_ele
    for val in args:
        res|=val
    return res

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

import sys

input=sys.stdin.readline

N=int(input())
S=input().rstrip()

init_val=[1<<(ord(S[i])-97) for i in range(N)]
test=SegmentTree(N.bit_length(),ide_ele,seg_func,init_val)

for _ in range(int(input())):
    t,l,r=input().split()
    t,l=int(t),int(l)
    if t==1:
        val=ord(r)-97
        test.update(l-1,1<<val)
    else:
        r=int(r)
        res=test.query(l-1,r-1)
        print(popcount(res))

Submission status: Accepted

Solution code:
from collections import deque

class SegmentTree():
    def __init__(self,n,ide_ele,merge_func,init_val):
        self.n=n
        self.ide_ele=ide_ele
        self.merge_func=merge_func
        self.val=[0 for i in range(1<<n)]
        self.merge=[0 for i in range(1<<n)]
        self.parent=[-1 for i in range(1<<n)]
        deq=deque([1<<(n-1)])
        res=[]
        while deq:
            v=deq.popleft()
            res.append(v)
            if not v&1:
                gap=(v&-v)//2
                self.parent[v-gap]=v
                deq.append(v-gap)
                self.parent[v+gap]=v
                deq.append(v+gap)
        for v in res[::-1]:
            if v-1<len(init_val):
                self.val[v-1]=init_val[v-1]
            self.merge[v-1]=self.val[v-1]
            if not v&1:
                gap=(v&-v)//2
                self.merge[v-1]=self.merge_func(self.merge[v-1],self.merge[v-gap-1],self.merge[v+gap-1])

    def update(self,id,x):
        self.val[id]=x
        pos=id+1
        while pos!=-1:
            if pos&1:
                self.merge[pos-1]=self.val[pos-1]
            else:
                gap=(pos&-pos)//2
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos+gap-1],self.merge[pos-gap-1])
            pos=self.parent[pos]

    def cnt(self,k):
        lsb=(k)&(-k)
        return (lsb<<1)-1

    def lower_kth_merge(self,nd,k):
        res=self.ide_ele
        if k==-1:
            return res
        mini=nd-(nd&-nd)+1+k
        id=nd
        while True:
            gap=(id&-id)//2
            if id>mini:
                id-=gap
            elif id==mini:
                return self.merge_func(res,self.val[id-1],self.merge[id-gap-1])
            else:
                res=self.merge_func(res,self.val[id-1],self.merge[id-gap-1])
                id+=gap

    def upper_kth_merge(self,nd,k):
        res=self.ide_ele
        if k==-1:
            return res
        maxi=nd+(nd&-nd)-1-k
        id=nd
        while True:
            gap=(id&-id)//2
            if id>maxi:
                res=self.merge_func(res,self.val[id-1],self.merge[id+gap-1])
                id-=gap
            elif id==maxi:
                return self.merge_func(res,self.val[id-1],self.merge[id+gap-1])
            else:
                id+=gap

    def query(self,l,r):
        id=1<<(self.n-1)
        while True:
            if id-1<l:
                id+=((id)&(-id))//2
            elif id-1>r:
                id-=((id)&(-id))//2
            else:
                res=self.val[id-1]
                if id%2:
                    return res
                gap=((id)&(-id))//2
                L,R=id-gap,id+gap
                #print(l,r,id,L,R)
                left=self.upper_kth_merge(L,id-1-l-1)
                right=self.lower_kth_merge(R,r-id)
                return self.merge_func(res,left,right)

ide_ele=0

def seg_func(*args):
    res=ide_ele
    for val in args:
        res|=val
    return res

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

import sys

input=sys.stdin.readline

N=int(input())
S=input().rstrip()

init_val=[1<<(ord(S[i])-97) for i in range(N)]
test=SegmentTree(19,ide_ele,seg_func,init_val)

for _ in range(int(input())):
    t,l,r=input().split()
    t,l=int(t),int(l)
    if t==1:
        val=ord(r)-97
        test.update(l-1,1<<val)
    else:
        r=int(r)
        res=test.query(l-1,r-1)
        print(popcount(res))

Submission status: Accepted

Solution code:
class SegTree:
    def __init__(self, init_val, segfunc, ide_ele):
        n = len(init_val)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        self.num = 1 << (n - 1).bit_length()
        self.tree = [ide_ele] * 2 * self.num
        # 配列の値を葉にセット
        for i in range(n):
            self.tree[self.num + i] = init_val[i]
        # 構築していく
        for i in range(self.num - 1, 0, -1):
            self.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])

    def update(self, k, x):
        k += self.num
        self.tree[k] = x
        while k > 1:
            self.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])
            k >>= 1

    def query(self, l, r):
        res = self.ide_ele

        l += self.num
        r += self.num
        while l < r:
            if l & 1:
                res = self.segfunc(res, self.tree[l])
                l += 1
            if r & 1:
                res = self.segfunc(res, self.tree[r - 1])
            l >>= 1
            r >>= 1
        return res

ide_ele=0

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

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

import sys

input=sys.stdin.readline

N=int(input())
S=input().rstrip()

init_val=[1<<(ord(S[i])-97) for i in range(N)]
test=SegTree(init_val,segfunc,ide_ele)

for _ in range(int(input())):
    t,l,r=input().split()
    t,l=int(t),int(l)
    if t==1:
        val=ord(r)-97
        test.update(l-1,1<<val)
    else:
        r=int(r)
        res=test.query(l-1,r)
        print(popcount(res))

Submission status: Accepted

Solution code:
from collections import deque

class SegmentTree():
    def __init__(self,n,ide_ele,merge_func,init_val):
        self.n=n
        self.ide_ele=ide_ele
        self.merge_func=merge_func
        self.val=[0 for i in range(1<<n)]
        self.merge=[0 for i in range(1<<n)]
        self.parent=[-1 for i in range(1<<n)]
        deq=deque([1<<(n-1)])
        res=[]
        while deq:
            v=deq.popleft()
            res.append(v)
            if not v&1:
                gap=(v&-v)//2
                self.parent[v-gap]=v
                deq.append(v-gap)
                self.parent[v+gap]=v
                deq.append(v+gap)
        for v in res[::-1]:
            if v-1<len(init_val):
                self.val[v-1]=init_val[v-1]
            self.merge[v-1]=self.val[v-1]
            if not v&1:
                gap=(v&-v)//2
                self.merge[v-1]=self.merge_func(self.merge[v-1],self.merge[v-gap-1],self.merge[v+gap-1])

    def update(self,id,x):
        self.val[id]=x
        pos=id+1
        while pos!=-1:
            if pos&1:
                self.merge[pos-1]=self.val[pos-1]
            else:
                gap=(pos&-pos)//2
                self.merge[pos-1]=self.merge_func(self.val[pos-1],self.merge[pos+gap-1],self.merge[pos-gap-1])
            pos=self.parent[pos]

    def cnt(self,k):
        lsb=(k)&(-k)
        return (lsb<<1)-1

    def lower_kth_merge(self,nd,k):
        res=self.ide_ele
        id=nd
        if k==-1:
            return res
        while True:
            if not id%2:
                gap=((id)&(-id))//2
                l=id-gap
                r=id+gap
                cnt=self.cnt(l)
                if cnt<k:
                    k-=cnt+1
                    res=self.merge_func(res,self.val[id-1],self.merge[l-1])
                    id=r
                elif cnt==k:
                    res=self.merge_func(res,self.val[id-1],self.merge[l-1])
                    return res
                else:
                    id=l
            else:
                res=self.merge_func(res,self.val[id-1])
                return res

    def upper_kth_merge(self,nd,k):
        res=self.ide_ele
        id=nd
        if k==-1:
            return res
        while True:
            if not id%2:
                gap=((id)&(-id))//2
                l=id-gap
                r=id+gap
                cnt=self.cnt(r)
                if cnt<k:
                    k-=cnt+1
                    res=self.merge_func(res,self.val[id-1],self.merge[r-1])
                    id=l
                elif cnt==k:
                    res=self.merge_func(res,self.val[id-1],self.merge[r-1])
                    return res
                else:
                    id=r
            else:
                res=self.merge_func(res,self.val[id-1])
                return res

    def query(self,l,r):
        id=1<<(self.n-1)
        while True:
            if id-1<l:
                id+=((id)&(-id))//2
            elif id-1>r:
                id-=((id)&(-id))//2
            else:
                res=self.val[id-1]
                if id%2:
                    return res
                gap=((id)&(-id))//2
                L,R=id-gap,id+gap
                #print(l,r,id,L,R)
                left=self.upper_kth_merge(L,id-1-l-1)
                right=self.lower_kth_merge(R,r-id)
                return self.merge_func(res,left,right)

ide_ele=0

def seg_func(*args):
    res=ide_ele
    for val in args:
        res|=val
    return res

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

import sys

input=sys.stdin.readline

N=int(input())
S=input().rstrip()

init_val=[1<<(ord(S[i])-97) for i in range(N)]
test=SegmentTree(19,ide_ele,seg_func,init_val)

for _ in range(int(input())):
    t,l,r=input().split()
    t,l=int(t),int(l)
    if t==1:
        val=ord(r)-97
        test.update(l-1,1<<val)
    else:
        r=int(r)
        res=test.query(l-1,r-1)
        print(popcount(res))