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

class SegmentTree:
    def __init__(self, initial_values, f=max, zero_factory=int, converter=lambda x:x):
        self.__f, self.__z, self.__c = f, zero_factory, converter
        self.__n = 1 << ((len(initial_values) - 1).bit_length())
        self.__dat = [zero_factory() for _ in range(2 * self.__n)]
        zi = self.__get_leaf(0)
        for i, v in enumerate(initial_values): self.__dat[zi + i] = converter(v)
        for i in range(zi-1, -1, -1): self.__dat[i] = f(*self.__get_children(i))

    def update(self, index, value):
        i, v = self.__get_leaf(index), self.__c(value)
        if self.__dat[i] == v: return
        self.__dat[i] = v
        while i:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))

    def query(self, from_inclusive, to_exclusive):
        ans = self.__z()
        if to_exclusive <= from_inclusive: return ans
        l, r = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        while r - l > 1:
            if self.__is_right(l): ans = self.__f(ans, self.__dat[l])
            if self.__is_left(r): ans, r = self.__f(ans, self.__dat[r]), r-1
            l, r = l//2, self.__get_parent(r)
        ans = self.__f(ans, self.__dat[l])
        if l != r: ans = self.__f(ans, self.__dat[r])
        return ans

    def __get_leaf(self, i): return self.__n + i - 1
    def __get_parent(self, i): return (i-1)//2
    def __get_children(self, i): return (self.__dat[2*i+1], self.__dat[2*i+2])
    def __is_left(self, i): return i&1 == 1
    def __is_right(self, i): return i&1 == 0

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class segmentTreeOR():
    initValue = 0
    dat = []
    lenTreeList = -1
    depthTreeList = 0
    lenOriginalList = -1

    def __init__(self):
        pass

    def load(self, l):
        # len(l)個よりも大きい2の二乗を得る
        self.lenOriginalList = len(l)
        self.lenTreeList = 2 ** (len(l) - 1).bit_length()  # len 5 なら 2^3 = 8
        self.depthTreeList = (len(l) - 1).bit_length()  # 木の段数(0 origin)
        self.dat = [self.initValue] * (self.lenTreeList * 2)
        # 値のロード
        for i in range(len(l)):
            self.dat[self.lenTreeList - 1 + i] = l[i]
        self.build()

    def build(self):
        for i in range(self.lenTreeList - 2, -1, -1):
            self.dat[i] = self.dat[2 * i + 1] | self.dat[2 * i + 2]

    def setValue(self, i, a):
        """
        set a to list[i]
        """
        # print("setValue: {0}, {1}".format(i, a))
        nodeId = (self.lenTreeList - 1) + i
        # print(" first nodeId: {0}".format(nodeId))
        self.dat[nodeId] = a
        while nodeId != 0:
            nodeId = (nodeId - 1) // 2
            # print(" next nodeId: {0}".format(nodeId))
            self.dat[nodeId] = self.dat[nodeId * 2 + 1] | self.dat[nodeId * 2 + 2]

    def querySub(self, a, b, nodeId, l, r):
        """
        [a,b) 区間の親クエリに対するノードnodeへ[l, r)の探索をデリゲート
        区間については、dataの添え字は0,1,2,3,4としたときに、
        [0,3)なら0,1,2の結果を返す
        """
        # print("querySub: a={0}, b={1}, nodeId={2}, l={3}, r={4}".format(a, b, nodeId, l, r))
        if (r <= a or b <= l):
            return self.initValue
        if a <= l and r <= b:
            return self.dat[nodeId]
        resLeft = self.querySub(a, b, 2 * nodeId + 1, l, (l + r) // 2)
        resRight = self.querySub(a, b, 2 * nodeId + 2, (l + r) // 2, r)
        return resLeft | resRight

    def query(self, a, b):
        return self.querySub(a, b, 0, 0, self.lenTreeList)

# https://yottagin.com/?p=2808
def count_ones_by_bin(num):
    bin_num = bin(num)[2:]
    count = 0
    for i in bin_num:
        count += int(i)
    return count

n = int(input())
s = input()
sl = list(s)
sl = list(map(lambda x: ord(x) - ord("a"), sl))

l = list(map(lambda x: 1 << x, sl))

st = segmentTreeOR()
st.load(l)

q = int(input())
for _ in range(q):
    ty, x, y = input().split()
    x = int(x)
    if ty == "1":
        nind = ord(y[0]) - ord("a") # 置き換えるindex
        st.setValue(x-1, 1 << nind)
    elif ty == "2":
        x = int(x) - 1
        y = int(y)
        res = 0
        cnt = st.query(x, y)
        print(count_ones_by_bin(cnt))
    else:
        print("error")

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n=int(input())+1
d=[0]*n*2
def update(i,x):
  i+=n
  d[i]=x
  while i//2:
    i//=2
    d[i]=d[i+i]|d[i-~i]
def query(l,r):
  l+=n
  r+=n
  s=0
  while l<r:
    if l&1:
      s|=d[l]
      l+=1
    if r&1:
      r-=1
      s|=d[r]
    l//=2
    r//=2
  return bin(s).count('1')
for i,c in enumerate(input(),n):d[i]=1<<ord(c)-97
for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
for _ in range(int(input())):
  q,a,b=input().split()
  if q>'1':print(query(int(a)-1,int(b)))
  else:update(int(a)-1,1<<ord(b)-97)

Submission status: Accepted

Solution code:


N = [int(i) for i in input().split()][0]
string = list(input())
Q = [int(i) for i in input().split()][0]
queries = [[i for i in input().split()] for _ in range(Q)]

tmp = N 
c = 0
while tmp > 0:
  c += 1
  tmp //= 2
N2 = 2**c
offset = N2 - 1

seg_tree = [0 for _ in range(N2*2 -1)]
for n in range(N):
  ind = ord(string[n]) - ord("a")
  seg_tree[offset + n] = 1 << ind

def set_seg_tree(i, seg_trees):
  if i >= N2 -1:
    return seg_trees[i]
  left = 2*i + 1
  right = 2*i + 2
  l_seg = set_seg_tree(left, seg_trees)
  r_seg = set_seg_tree(right, seg_trees)
  seg_trees[i] = l_seg | r_seg
  return seg_trees[i]
set_seg_tree(0, seg_tree)
    
def update(i, c, seg_trees):
  i += offset
  seg_trees[i] = 1 << c
  while i > 0:
    i = (i - 1)//2
    seg_trees[i] = seg_trees[i * 2 + 1] | seg_trees[i * 2 + 2]

def get_sum(a, b, k, l, r, seg_trees):
  if (b <= l) or (r <= a):
    return 0
  if (a <= l) and (r <= b):
    return seg_trees[k]
  vl = get_sum(a, b, k * 2 + 1, l, (l + r)//2, seg_trees)
  vr = get_sum(a, b, k * 2 + 2, (l + r)//2, r, seg_trees)
  return vl | vr

for query in queries:
  type_, i, q = query
  if type_ == "1":
    i = int(i) - 1
    pos = ord(q) - ord("a")
    update(i, pos, seg_tree)
  else:
    l = int(i) - 1
    r = int(q)
    ret = get_sum(l, r, 0, 0, N2, seg_tree)
    print(bin(ret).count("1"))

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
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 i:
        i = (i-1) // 2
        X[i] = X[2*i+1] | X[2*i+2]

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):
    X[(1<<NN) + i] = 1 << a
for i in range((1<<NN)-1)[::-1]:
    X[i] = X[i*2+1] | X[i*2+2]

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():
    _data = []
    _offset = 0
    _size = 0

    def __init__(self, size):
        _size = size
        t = 1
        while t < size:
            t *= 2
        self._offset = t - 1
        self._data = [0 for _ in range(t * 2 - 1)]

    def update_all(self, iterable):
        self._data[self._offset:self._offset+self._size] = [1 << (ord(c) - ord('a')) for c in iterable]
        for i in range(self._offset - 1, -1, -1):
            self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]

    def update(self, index, value):
        i = self._offset + index
        self._data[i] = 1 << (ord(value) - ord('a'))
        while i >= 1:
            i = (i - 1) // 2
            self._data[i] = self._data[i * 2 + 1] | self._data[i * 2 + 2]

    def query(self, start, stop):
        result = 0
        l = start + self._offset
        r = stop + self._offset
        while l < r:
            if l & 1 == 0:
                result = result | self._data[l]
            if r & 1 == 0:
                result = result | self._data[r - 1]
            l = l // 2
            r = (r - 1) // 2
        return result


N = int(input())
S = input()

st = SegmentTree(N)
st.update_all(S)

Q = int(input())
for _ in range(Q):
    q = input().split()
    if q[0] == '1':
        i, c = q[1:]
        i = int(i) - 1
        st.update(i, c)
    elif q[0] == '2':
        l, r = map(int, q[1:])
        print(bin(st.query(l - 1, r)).count('1'))

Submission status: Accepted

Solution code:
L = list("abcdefghijklmnopqrstuvwxyz")

def num(X):
    return L.index(X)


N = int(input())
S = list(str(input()))
S = [0] + S
Q = int(input())

query = [0] * Q

for i in range(Q):
    query[i] = list(input().split())

#print(query)

###Binary Indexed Tree

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

#print(ABC_BIT)

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

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

#print(L,S,Q)

for i in range(1,N+1):
    BIT_update(num(S[i]),i,1)
    #print(ABC_BIT)

for i in range(Q):
    if query[i][0] == "1":
        y = int(query[i][1])
        z = query[i][2]
        BIT_update(num(S[y]),y,-1)
        BIT_update(num(z),y,1)
        S[y] = z
    else:
        y = int(query[i][1])
        z = int(query[i][2])
        count = 0
        for k in range(26):
            if BIT_query(k,z) - BIT_query(k,y-1) >= 1:
                count += 1
        print(count)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline


class SegmentTree:
    def __init__(self, target, no_effect):
        target_size = len(target)
        leaves_size = 1
        while leaves_size < target_size:
            leaves_size *= 2
        self.tree_size = leaves_size * 2 - 1
        self.tree = [no_effect] * self.tree_size
        self.no_effect = no_effect
        self.initialize_tree(target, no_effect)

    @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(self, target: list, no_effect=0):
        initial_leaf = self.tree_size // 2
        leaves = range(initial_leaf, initial_leaf+len(target))
        for value, leaf in zip(target, leaves):
            self.tree[leaf] = self.initialize_func(value)

        for parent in range(initial_leaf-1, -1, -1):
            self.tree[parent] = self.merge_child_data(parent)

    def update(self, new_value, index):
        leaf = self.tree_size//2 + index
        new_data = self.initialize_func(new_value)
        if self.tree[leaf] == new_data:
            return
        self.tree[leaf] = new_data

        parent = (leaf-1) // 2
        while parent >= 0:
            new_data = self.merge_child_data(parent)
            if self.tree[parent] == new_data:
                break
            self.tree[parent] = new_data
            parent = (parent-1) // 2

    def resolve_query(self, _from, to):
        result = self.no_effect
        left, right = _from + self.tree_size//2, to + self.tree_size//2
        while left <= right:
            result = self.merge_func(result, self.tree[left])
            result = self.merge_func(result, self.tree[right])
            left //= 2
            right = right//2 - 1

        return bin(result).count('1')


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

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

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

Submission status: Accepted

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


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


MAX = 5 * 10 ** 5 + 2
d = dict()

for c in range(ord("a"), ord("z") + 1):
    s = chr(c)
    d[s] = BIT(MAX)
    for i, v in enumerate(S):
        if v == s:
            d[s].add(i + 1, 1)


for t, i, c in X:
    if t == "1":
        i = int(i)
        
        if S[i - 1] != c:
            # Delete index
            d[S[i - 1]].add(i, -1)
            
            # Insert index
            d[c].add(i, 1)
            S[i - 1] = c
    else:
        l = int(i)
        r = int(c)
        
        res = 0
        for c in range(ord("a"), ord("z") + 1):
            s = chr(c)
            res += int(d[s].sum(r) - d[s].sum(l - 1) > 0)

        print(res)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

al = "abcdefghijklmnopqrstuvwxyz"
ald = {}
for i in range(26):
    ald[al[i]] = i

def BIT_query(BIT, idx):
    res_sum = 0
    while idx > 0:
        res_sum += BIT[idx]
        idx -= idx&(-idx)
    return res_sum

def BIT_update(N, BIT, idx, x):
    while idx <= N:
        BIT[idx] += x
        idx += idx&(-idx)
    return

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

S = [s for s in S]

bits = [[0]*(N+1) for i in range(26)]

for i in range(N):
    ind = ald[S[i]]
    BIT_update(N, bits[ind], i+1, 1)

for i in range(Q):
    f, a, b = (i for i in input().split())
    if f == "1":
        a = int(a)
        if S[a-1] == b:
            pass
        else:
            ind = ald[S[a-1]]
            BIT_update(N, bits[ind], a, -1)
            ind = ald[b]
            BIT_update(N, bits[ind], a, 1)
            S[a-1] = b
    else:
        a = int(a)
        b = int(b)
        ans = 0
        for bit in bits:
            if a != 1:
                mi = BIT_query(bit, a-1)
            else:
                mi = 0
            if BIT_query(bit, b) > mi:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, initial_values, f=max, zero=0, converter=lambda x:x):
        self.__f, self.__z, self.__c, self.__size = f, zero, converter, len(initial_values)
        self.__n = 1 << ((self.__size - 1).bit_length())
        self.__dat = [zero] * (2 * self.__n)
        zi = self.__get_leaf(0)
        for i, v in enumerate(initial_values): self.__dat[zi + i] = converter(v)
        for i in range(zi-1, -1, -1): self.__dat[i] = f(*self.__get_children(i))
    
    def update(self, index, value):
        i, v = self.__get_leaf(index), self.__c(value)
        if self.__dat[i] == v: return
        self.__dat[i] = v
        while i:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))
    
    def query(self, from_inclusive, to_exclusive):
        ans = self.__z
        if to_exclusive <= from_inclusive: return ans
        l, r = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        while r - l > 1:
            if self.__is_right(l): ans = self.__f(ans, self.__dat[l])
            if self.__is_left(r): ans, r = self.__f(ans, self.__dat[r]), r-1
            l, r = l//2, self.__get_parent(r)
        ans = self.__f(ans, self.__dat[l])
        if l != r: ans = self.__f(ans, self.__dat[r])
        return ans

    def __get_leaf(self, i): return self.__n + i - 1
    def __get_parent(self, i): return (i-1)//2
    def __get_children(self, i): return (self.__dat[2*i+1], self.__dat[2*i+2])
    def __is_left(self, i): return i&1 == 1
    def __is_right(self, i): return i&1 == 0

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

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, initial_values, f=max, zero=0, converter=lambda x:x):
        self.__f, self.__z, self.__c, self.__size = f, zero, converter, len(initial_values)
        self.__n = 1 << ((self.__size - 1).bit_length())
        self.__dat = [zero] * (2 * self.__n)
        zi = self.__get_leaf(0)
        for i, v in enumerate(initial_values): self.__dat[zi + i] = converter(v)
        for i in range(zi-1, -1, -1): self.__dat[i] = f(*self.__get_children(i))
    
    def update(self, index, value):
        i, v = self.__get_leaf(index), self.__c(value)
        if self.__dat[i] == v: return
        self.__dat[i] = v
        while i:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))
    
    def query(self, from_inclusive, to_exclusive):
        ans = self.__z
        if to_exclusive <= from_inclusive: return ans
        l, r = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        while r - l > 1:
            if self.__is_right(l): ans = self.__f(ans, self.__dat[l])
            if self.__is_left(r): ans, r = self.__f(ans, self.__dat[r]), r-1
            l, r = l//2, self.__get_parent(r)
        ans = self.__f(ans, self.__dat[l])
        if l != r: ans = self.__f(ans, self.__dat[r])
        return ans

    def __get_leaf(self, i): return self.__n + i - 1
    def __get_parent(self, i): return (i-1)//2
    def __get_children(self, i): return (self.__dat[2*i+1], self.__dat[2*i+2])
    def __is_left(self, i): return i&1 == 1
    def __is_right(self, i): return i&1 == 0

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

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, initial_values, f=max, zero=0):
        self.__f, self.__z, self.__size = f, zero, len(initial_values)
        self.__n = 1 << ((self.__size - 1).bit_length())
        self.__dat = [zero] * (2 * self.__n)
        zi = self.__get_leaf(0)
        for i, v in enumerate(initial_values): self.__dat[zi + i] = v
        for i in range(zi-1, -1, -1): self.__dat[i] = self.__f(*self.__get_children(i))
    
    def update(self, index, value):
        i = self.__get_leaf(index)
        if self.__dat[i] == value: return
        self.__dat[i] = value
        while i:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))
    
    def query(self, from_inclusive, to_exclusive):
        ans = self.__z
        if to_exclusive <= from_inclusive: return ans
        l, r = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        while r - l > 1:
            if self.__is_right(l): ans = self.__f(ans, self.__dat[l])
            if self.__is_left(r): ans, r = self.__f(ans, self.__dat[r]), r-1
            l, r = l//2, self.__get_parent(r)
        ans = self.__f(ans, self.__dat[l])
        if l != r: ans = self.__f(ans, self.__dat[r])
        return ans

    def __get_leaf(self, i): return self.__n + i - 1
    def __get_parent(self, i): return (i-1)//2
    def __get_children(self, i): return (self.__dat[2*i+1], self.__dat[2*i+2])
    def __is_left(self, i): return i&1 == 1
    def __is_right(self, i): return i&1 == 0

N = int(input())
S = input()
g = lambda c: 1 << (ord(c)-ord('a'))
tree = SegmentTree([g(c) for c in S], lambda x,y:x|y)
Q = int(input())
for _ in range(Q):
    t, a, b = input().split()
    if t == '1': tree.update(int(a)-1, g(b))
    else: print(bin(tree.query(int(a)-1, int(b))).count('1'))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, initial_values, f=max, zero=0):
        self.__f, self.__z, self.__size = f, zero, len(initial_values)
        self.__n = 1 << ((self.__size - 1).bit_length())
        self.__dat = [zero for _ in range(2 * self.__n)]
        zi = self.__get_leaf(0)
        for i, v in enumerate(initial_values): self.__dat[zi + i] = v
        for i in range(zi-1, -1, -1): self.__dat[i] = self.__f(*self.__get_children(i))
    
    def update(self, index, value):
        i = self.__get_leaf(index)
        if self.__dat[i] == value: return
        self.__dat[i] = value
        while i:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))
    
    def query(self, from_inclusive, to_exclusive):
        ans = self.__z
        if to_exclusive <= from_inclusive: return ans
        l, r = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        while r - l > 1:
            if self.__is_right(l): ans = self.__f(ans, self.__dat[l])
            if self.__is_left(r): ans, r = self.__f(ans, self.__dat[r]), r-1
            l, r = l//2, self.__get_parent(r)
        ans = self.__f(ans, self.__dat[l])
        if l != r: ans = self.__f(ans, self.__dat[r])
        return ans

    def __get_leaf(self, i): return self.__n + i - 1
    def __get_parent(self, i): return (i-1)//2
    def __get_children(self, i): return (self.__dat[2*i+1], self.__dat[2*i+2])
    def __is_left(self, i): return i&1 == 1
    def __is_right(self, i): return i&1 == 0

N = int(input())
S = input()
g = lambda c: 1 << (ord(c)-ord('a'))
tree = SegmentTree([g(c) for c in S], lambda x,y:x|y)
Q = int(input())
for _ in range(Q):
    t, a, b = input().split()
    if t == '1': tree.update(int(a)-1, g(b))
    else: print(bin(tree.query(int(a)-1, int(b))).count('1'))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, initial_values, f=max, zero=0):
        self.__size = len(initial_values)
        self.__n = 1 << ((self.__size - 1).bit_length())
        self.__f = f
        self.__z = zero
        self.__dat = [zero for _ in range(2 * self.__n)]
        zi = self.__get_leaf(0)
        for i, v in enumerate(initial_values):
            self.__dat[zi + i] = v
        for i in range(zi-1, -1, -1):
            self.__dat[i] = self.__f(*self.__get_children(i))
    
    def update(self, index, value):
        i = self.__get_leaf(index)
        if self.__dat[i] == value: return
        self.__dat[i] = value
        while i > 0:
            i = self.__get_parent(i)
            self.__dat[i] = self.__f(*self.__get_children(i))
    
    def query(self, from_inclusive, to_exclusive):
        if to_exclusive <= from_inclusive: return self.__z
        a, b = self.__get_leaf(from_inclusive), self.__get_leaf(to_exclusive) - 1
        ans = self.__z
        while b - a > 1:
            if self.__is_right(a): ans = self.__f(ans, self.__dat[a])
            if self.__is_left(b): ans, b = self.__f(ans, self.__dat[b]), b-1
            a, b = a//2, self.__get_parent(b)
        ans = self.__f(ans, self.__dat[a])
        if a != b: ans = self.__f(ans, self.__dat[b])
        return ans

    def __get_leaf(self, i): return self.__n + i - 1
    def __get_parent(self, i): return (i-1)//2
    def __get_children(self, i): return (self.__dat[2*i+1], self.__dat[2*i+2])
    def __is_left(self, i): return i&1 == 1
    def __is_right(self, i): return i&1 == 0

N = int(input())
S = input()
g = lambda c: 1 << (ord(c)-ord('a'))
tree = SegmentTree([g(c) for c in S], lambda x,y:x|y)
Q = int(input())
for _ in range(Q):
    t, a, b = input().split()
    if t == '1': tree.update(int(a)-1, g(b))
    else: print(bin(tree.query(int(a)-1, int(b))).count('1'))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, initial_values, f=max, zero=0):
        self.__size = len(initial_values)
        self.__n = 1 << ((self.__size - 1).bit_length())
        self.__f = f
        self.__z = zero
        self.__dat = [zero for _ in range(2 * self.__n)]
        zi = self.__n - 1
        for i, v in enumerate(initial_values):
            self.__dat[zi + i] = v
        for i in range(zi-1, -1, -1):
            self.__dat[i] = self.__f(self.__dat[2*i+1], self.__dat[2*i+2])
    
    def update(self, index, value):
        i = self.__n + index - 1
        if self.__dat[i] == value: return
        self.__dat[i] = value
        while i > 0:
            i = (i-1)//2
            self.__dat[i] = self.__f(self.__dat[2*i+1], self.__dat[2*i+2])
    
    def query(self, from_inclusive, to_exclusive):
        if to_exclusive <= from_inclusive: return self.__z
        a, b = self.__n + from_inclusive - 1, self.__n + to_exclusive - 2
        ans = self.__z
        while b - a > 1:
            if a&1 == 0: ans = self.__f(ans, self.__dat[a])
            if b&1 == 1: ans, b = self.__f(ans, self.__dat[b]), b-1
            a, b = a//2, (b-1)//2
        ans = self.__f(ans, self.__dat[a])
        if a != b: ans = self.__f(ans, self.__dat[b])
        return ans

N = int(input())
S = input()
g = lambda c: 1 << (ord(c)-ord('a'))
tree = SegmentTree([g(c) for c in S], lambda x,y:x|y)
Q = int(input())
for _ in range(Q):
    t, a, b = input().split()
    if t == '1': tree.update(int(a)-1, g(b))
    else: print(bin(tree.query(int(a)-1, int(b))).count('1'))

Submission status: Accepted

Solution code:
class SegmentTree:
    def __init__(self, initial_values, f=max, zero=0):
        self.__size = len(initial_values)
        self.__n = 1 << ((self.__size - 1).bit_length())
        self.__f = f
        self.__z = zero
        self.__dat = [zero] * (2 * self.__n)
        self.__get_leaf = lambda i: self.__n + i - 1
        self.__get_parent = lambda i: (i-1)//2
        self.__get_children = lambda i: (self.__dat[2*i+1], self.__dat[2*i+2])
        self.__is_left = lambda i: i&1 == 1
        self.__is_right = lambda i: i&1 == 0
        zi = self.__get_leaf(0)
        dat, get_children = self.__dat, self.__get_children
        for i, v in enumerate(initial_values):
            dat[zi + i] = v
        for i in range(zi-1, -1, -1):
            dat[i] = f(*get_children(i))
    
    def update(self, index, value):
        f, dat, get_leaf, get_parent, get_children = self.__f, self.__dat, self.__get_leaf, self.__get_parent, self.__get_children
        i = get_leaf(index)
        if dat[i] == value: return
        dat[i] = value
        while i > 0:
            i = get_parent(i)
            dat[i] = f(*get_children(i))
    
    def query(self, from_inclusive, to_exclusive):
        f, z, dat, get_leaf, get_parent, is_left, is_right = self.__f, self.__z, self.__dat, self.__get_leaf, self.__get_parent, self.__is_left, self.__is_right
        if to_exclusive <= from_inclusive: return z
        a, b = get_leaf(from_inclusive), get_leaf(to_exclusive) - 1
        ans = z
        while b - a > 1:
            if is_right(a): ans = f(ans, dat[a])
            if is_left(b): ans, b = f(ans, dat[b]), b-1
            a, b = a//2, get_parent(b)
        ans = f(ans, dat[a])
        if a != b: ans = f(ans, dat[b])
        return ans

N = int(input())
S = input()
g = lambda c: 1 << (ord(c)-ord('a'))
tree = SegmentTree([g(c) for c in S], lambda x,y:x|y)
Q = int(input())
for _ in range(Q):
    t, a, b = input().split()
    if t == '1': tree.update(int(a)-1, g(b))
    else: print(bin(tree.query(int(a)-1, int(b))).count('1'))