Problem:


Score : 500 points

Problem Statement

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

Process Q queries of the following two types:

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

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

Constraints

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

S is a string consisting of lowercase English letters.

c_q is a lowercase English letter.

1 \leq N \leq 500000

1 \leq Q \leq 20000

|S| = N

1 \leq i_q \leq N

1 \leq l_q \leq r_q \leq N

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

Input

Input is given from Standard Input in the following format:

N
S
Q
Query_1
\vdots
Query_Q

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

1 i_q c_q

2 l_q r_q

Output

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

Sample Input 1

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

Sample Output 1

3
1
5

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

In the second query, S is modified to abcdzbd.

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

In the fourth query, S is modified to abcazbd.

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

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



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


Sample output:
3
1
5

Submission status: Accepted

Solution code:
class SegmentTree():
    def segfunc(self, x, y):
        return x|y #関数
    
    def __init__(self, a): #a:リスト
        n = len(a)
        self.ide_ele = 0 #単位元
        self.num = 2**((n-1).bit_length()) #num:n以上の最小の2のべき乗
        self.seg = [self.ide_ele]*2*self.num
        
        #set_val
        for i in range(n):
            self.seg[i+self.num-1] = a[i]
        #built
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1], self.seg[2*i+2])
        
        
    def update(self, k, s):
        x = 1<<(ord(s)-97)
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
            
    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q - p > 1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res

def popcount(x):
    '''xの立っているビット数をカウントする関数
    (xは64bit整数)'''

    # 2bitごとの組に分け、立っているビット数を2bitで表現する
    x = x - ((x >> 1) & 0x5555555555555555)

    # 4bit整数に 上位2bit + 下位2bit を計算した値を入れる
    x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)

    x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f # 8bitごと
    x = x + (x >> 8) # 16bitごと
    x = x + (x >> 16) # 32bitごと
    x = x + (x >> 32) # 64bitごと = 全部の合計
    return x & 0x0000007f
    

N = int(input())
S = list(input())
for i in range(N):
    S[i] = 1<<(ord(S[i])-97)
Seg = SegmentTree(S)
Q = int(input())
for i in range(Q):
    x, y, z = input().split()
    if int(x) == 1:
        Seg.update(int(y)-1, z)
    else:
        print(popcount(Seg.query(int(y)-1, int(z))))

Submission status: Accepted

Solution code:
# AtCoder Beginner Contest 157
# E - Simple String Queries
# https://atcoder.jp/contests/abc157/tasks/abc157_e
from bisect import bisect_left, insort_left
import sys
input = sys.stdin.readline
OFS = ord('a')
_ = input()
S = list(input()[:-1])

D = [[] for _ in [0]*26]
for i, s in enumerate(S):
    D[ord(s)-OFS].append(i)

for _ in [0]*int(input()):
    Q = input()[:-1].split()
    if Q[0] == '1':
        i, c = int(Q[1])-1, Q[2]

        if S[i] != c:
            s = ord(S[i])-OFS
            D[s].pop(bisect_left(D[s], i))
            insort_left(D[ord(c)-OFS], i)
            S[i] = c

    else:
        l, r = int(Q[1])-1, int(Q[2])-1

        cnt = 0
        for L in D:
            i = bisect_left(L, l)
            if i < len(L) and L[i] <= r:
                cnt += 1

        print(cnt)

Submission status: Accepted

Solution code:
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
      
import sys
input = sys.stdin.readline
from operator import or_

input()
seg = SegmentTree([1 << ord(x) - 97 for x in input()[:-1]], or_, 0)
ans = []
for _ in range(int(input())):
  f, x, y = input().split()
  if f == "1":
    seg.update(int(x) - 1, 1 << ord(y) - 97)
  else:
    ans.append(bin(seg.find(int(x) - 1, int(y))).count("1"))
print(*ans)

Submission status: Accepted

Solution code:
#!/usr/bin/python3
import bisect

n = int(input())
s = input()
q = int(input())

idxs = [ [] for i in range(26) ]
sl = [ s[i] for i in range(n) ]

for i in range(n):
    idxs[ord(s[i]) - ord('a')].append(i + 1)

#print(idxs)

qs = []
for i in range(q):
    qs.append(input())

for qi in qs:
    (op, x, y) = qi.split()
    if op == '1':
        j = int(x)
        c = y
        oc = sl[j - 1]
        if oc != c:
            sl[j - 1] = c
            idx = bisect.bisect_left(idxs[ord(oc) - ord('a')], j)
            del idxs[ord(oc) - ord('a')][idx]
            idx = bisect.bisect_left(idxs[ord(c) - ord('a')], j)
            idxs[ord(c) - ord('a')].insert(idx, j)
        
    elif op == '2':
        l = int(x)
        r = int(y)
        c = 0
        for i in range(26):
            il = bisect.bisect_left(idxs[i], l)
            ir = bisect.bisect_right(idxs[i], r)
            if il < ir:
                c += 1
        print(c)

Submission status: Accepted

Solution code:
import bisect
n = int(input().strip())
S = list(input().strip())
L=[[] for _ in range(26)]
for i,s in enumerate(S):
    L[ord(s)-ord("a")].append(i)

q = int(input().strip())
for _ in range(q):
    query=input().strip().split()
    if query[0]=="1":
        i=int(query[1])
        i-=1
        c=query[2]
        if S[i]!=c:
            delInd=bisect.bisect_left(L[ord(S[i])-ord("a")],i)
            del L[ord(S[i])-ord("a")][delInd]
            bisect.insort(L[ord(c)-ord("a")], i)
            S[i]=c
    else:
        l,r=map(int,[query[1],query[2]])
        l-=1; r-=1
        ans=0
        for j in range(26):
            ind=bisect.bisect_left(L[j],l)
            if ind<len(L[j]) and L[j][ind]<=r:
                ans+=1
        print(ans)

Submission status: Accepted

Solution code:
n = int(input())
s = input()
q = int(input())

queris = []
for _ in range(q):
    t, a, b = input().split()
    queris.append((t, a, b))


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

seg = [0] * (2 * size - 1)

def alph2bit(alph):
    return 1 << (ord(alph) - ord('a'))

def update(i, x, segment_tree):
    i += size - 1
    segment_tree[i] = alph2bit(x)
    while i > 0:
        i = (i - 1) // 2 # 親を更新していく。
        segment_tree[i] = segment_tree[i * 2 + 1] | segment_tree[i * 2 + 2]

def query(s, t, k, l, r, segment_tree):
    if r <= s or t <= l: # 区間が全くかぶらない場合
        return 0
    if s <= l and r <= t: # 求められた区間が、l, rを完全に含んでいる。
        return segment_tree[k]
    else:
        ask_left = query(s, t, k * 2 + 1, l, (l + r) // 2, segment_tree)
        ask_right = query(s, t, k * 2 + 2, (l + r) // 2, r, segment_tree)
        return ask_left | ask_right

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

for t, a, b in queris:
    if t == '1':
        update(int(a) - 1, b, seg)
    else:
        result = query(int(a) - 1, int(b), 0, 0, size, seg)
        print(bin(result).count('1'))

Submission status: Accepted

Solution code:
from string import ascii_lowercase
import sys


def input():
    return sys.stdin.readline().strip()


def sum_b(data, i):
    s = 0
    while i > 0:
        s += data[i]
        i -= i & -i
    return s


def add_b(data, i, x):
    while i <= n:
        data[i] += x
        i += i & -i


n = int(input())
s = input()
q = int(input())

bits = {c: [0] * (n + 1) for c in ascii_lowercase}
[add_b(bits[c], i, 1) for i, c in enumerate(s, 1)]

for q_type, *q in (input().split() for _ in range(q)):
    if q_type == '1':
        iq = int(q[0])
        cq = q[1]
        for b in bits.values():
            if sum_b(b, iq) - sum_b(b, iq - 1) == 1:
                add_b(b, iq, -1)
                break
        add_b(bits[cq], iq, 1)
    else:
        l, r = map(int, q)
        print(sum([bool(sum_b(b, r) - sum_b(b, l - 1) > 0) for b in bits.values()]))

Submission status: Accepted

Solution code:
from string import ascii_lowercase
import sys


def input():
    return sys.stdin.readline().strip()


class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0] * (n + 1)
        self.k_init = 2 ** (self.n - 1).bit_length()

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

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


n = int(input())
s = input()
q = int(input())

bits = {c: BIT(n) for c in ascii_lowercase}
[bits[c].add(i, 1) for i, c in enumerate(s, 1)]
queries = (input().split() for _ in range(q))

for q_type, *q in queries:
    if q_type == '1':
        iq = int(q[0])
        cq = q[1]
        for b in bits.values():
            if b.sum(iq) - b.sum(iq - 1) == 1:
                b.add(iq, -1)
                break
        bits[cq].add(iq, 1)
    else:
        l, r = map(int, q)
        print(sum([bool(v.sum(r) - v.sum(l - 1) > 0) for v in bits.values()]))

Submission status: Accepted

Solution code:
n = int(input())
s = input()
q = int(input())


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

        self.ll = []
        self.rr = []
        i = self.n
        for _ in range(self.logn+1):
            for j in range(0, self.n, i):
                self.ll.append(j)
                self.rr.append(j + i)
            i //= 2

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r, i=0):
        ll = self.ll[i]
        rr = self.rr[i]
        if l <= ll and rr <= r:
            return self.b[i]
        elif rr <= l or r <= ll:
            return self.one
        else:
            return self.func(self.get_segment(l, r, i * 2 + 1),
                             self.get_segment(l, r, i * 2 + 2))


def get_int(s):
    abc = "abcdefghijklmnopqrstuvwxyz"
    return 1 << abc.index(s)


seg = SegmentTree([get_int(i) for i in s], int.__or__, 0)

for _ in range(q):
    q, i, j = input().split()
    if q == "1":
        seg.update(int(i) - 1, get_int(j))
    else:
        aa = seg.get_segment(int(i) - 1, int(j))
        ans = 0
        for i in range(26):
            if (aa >> i) & 1 == 1:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect, insort
def main():
    n = int(input())
    s = list(input())
    q = int(input())
    _is = {chr(i):[] for i in range(ord("a"), ord("a")+27)}
    for i, si in enumerate(s):
        _is[si].append(i)
    for _ in range(q):
        t, i, c = input().split()
        i = int(i)-1
        if t == "1":
            if s[i] != c:
                index = bisect_left(_is[s[i]], i)
                del _is[s[i]][index]
                insort(_is[c], i)
                s[i] = c
        else:
            c = int(c) - 1
            cnt = 0
            for _isi in _is.values():
                if _isi:
                    is_in = bisect(_isi, c)-bisect_left(_isi, i)
                    if is_in:
                        cnt += 1
            print(cnt)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def RSQ_add(i, x, y):
    while True:
        if i > n:
            break
        BIT[y][i] += x
        i += i & -i

def RSQ_getsum(i, x):
    s = 0
    while True:
        if i <= 0:
            break
        s += BIT[x][i]
        i -= i & -i
    return s

n = int(input())
s = list(input())
q = int(input())
BIT = [[0] * (n + 1) for _ in range(26)]
for i in range(n):
    y = ord(s[i]) - 97
    RSQ_add(i + 1, 1, y)
for _ in range(q):
    com, a, b = map(str, input().split())
    com, a = int(com), int(a)
    if com == 1:
        RSQ_add(a, -1, ord(s[a - 1]) - 97)
        RSQ_add(a, 1, ord(b) - 97)
        s[a - 1] = b
    else:
        b = int(b)
        ans = 0
        for i in range(26):
            if RSQ_getsum(b, i) - RSQ_getsum(a - 1, i) >= 1:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
def main():
  import bisect
  
  n = int(input())
  s = list(input())
  q = int(input())
  
  d = {}
  for i in range(26):
    d[chr(ord('a')+i)] = []
  for i in range(n):
    d[s[i]].append(i)
  #print(d)
  
  for i in range(q):
    t,a,b = input().split()
    if t == '1':
      a = int(a)-1
      if s[a] == b:
        continue
      #idx = bisect.bisect_left(d[s[a]],a)
      #d[s[a]].pop(idx)
      d[s[a]].remove(a)
      bisect.insort_left(d[b],a)
      s[a] = b
    else:
      a = int(a)-1
      b = int(b)-1
      c = 0
      for i in range(26):
        idx = bisect.bisect_left(d[chr(ord('a')+i)],a)
        if idx < len(d[chr(ord('a')+i)]) and d[chr(ord('a')+i)][idx] <= b:
          c += 1
      print(c)
  
main()

Submission status: Accepted

Solution code:
def main():
  import bisect
  
  n = int(input())
  s = list(input())
  q = int(input())
  
  d = {}
  for i in range(26):
    d[chr(ord('a')+i)] = []
  for i in range(n):
    d[s[i]].append(i)
  #print(d)
  
  for i in range(q):
    t,a,b = input().split()
    if t == '1':
      a = int(a)-1
      if s[a] == b:
        continue
      idx = bisect.bisect_left(d[s[a]],a)
      d[s[a]].pop(idx)
      bisect.insort_left(d[b],a)
      s[a] = b
    else:
      a = int(a)-1
      b = int(b)-1
      c = 0
      for i in range(26):
        idx = bisect.bisect_left(d[chr(ord('a')+i)],a)
        if idx < len(d[chr(ord('a')+i)]) and d[chr(ord('a')+i)][idx] <= b:
          c += 1
      print(c)
  
main()

Submission status: Accepted

Solution code:
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]=segfunc(seg[2*i+1],seg[2*i+2])

def update(k,x):
    k += num-1
    seg[k] = x
    while k:
        k = (k-1)//2
        seg[k] = segfunc(seg[k*2+1],seg[k*2+2])

def query(p,q):
    if q<=p:
        return ide_ele
    p += num-1
    q += num-2
    res=ide_ele
    while q-p>1:
        if p&1 == 0:
            res = segfunc(res,seg[p])
        if q&1 == 1:
            res = segfunc(res,seg[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[p])
    else:
        res = segfunc(segfunc(res,seg[p]),seg[q])
    return res

#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
n=int(input())
S=input()
Q=int(input())

num =2**(n-1).bit_length()
seg=[ide_ele]*2*num

alphabetlist=['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
alphabet={key:alphabetlist.index(key)  for key in alphabetlist}

data=[0 for i in range(0,n)]
for i in range(0,n):
    data[i]=2**(alphabet[S[i]])

init(data)

ans=[]
for i in range(0,Q):
    q,a,b=input().split()
    if q=='1':
        update(int(a)-1,2**(alphabet[b]))
    else:
        a=int(a)
        b=int(b)
        ans.append(query(a-1,b))

for i in range(len(ans)):
    x=ans[i]
    print(bin(x).count('1'))

Submission status: Accepted

Solution code:
class SegmentTree:
  """Segmant Tree for query process.

  Args:
    a (List[int]): array.
    identity (int): identity element with f.
  """
  def __init__(self, a, identity=0):
    self.a = a
    self.n = len(a)
    self.identity = identity
    self.depth = (self.n - 1).bit_length()
    self.segment = (1 << self.depth) - 1
    self.tree = [identity] * (self.segment * 2 + 1)
    self.tree[self.segment : self.n + self.segment] = a
    for i in range(self.segment - 1, -1, -1):
      self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

  def update(self, i: int, x: int):
    i += self.segment
    self.tree[i] = x
    while i:
      i = (i - 1) // 2
      self.tree[i] = self.f(self.tree[2*i+1], self.tree[2*i+2])

  def query(self, l: int, r: int) -> int:
    """Query at [l, r]

    Args:
      l (int): left
      r (int): right

    Returns:
      int: result
    """
    if l > r:
      return self.identity
    l += self.segment
    r += self.segment
    res = self.identity
    while l <= r:
      if not l & 1:
        res = self.f(self.tree[l], res)
      if r & 1:
        res = self.f(res, self.tree[r])
      l = l // 2
      r = (r - 2) // 2
    return res

  def f(self, x: int, y: int) -> int:
    return x | y

n = int(input())
s = input()
q = int(input())
a = ord('a')
segment_tree = SegmentTree([1 << (ord(c) - a) for c in s])
for _ in range(q):
  query = input().split()
  if query[0] == '1':
    i = int(query[1]) - 1
    c = query[2]
    segment_tree.update(i, 1 << (ord(c) - a))
  else:
    l = int(query[1]) - 1
    r = int(query[2]) - 1
    bit = segment_tree.query(l, r)
    print(format(bit, 'b').count('1'))

Submission status: Accepted

Solution code:
import sys

# import bisect
# from collections import Counter, deque, defaultdict
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
# import itertools
# from operator import attrgetter, itemgetter

# import math

# from numba import jit

# from scipy import
# import numpy as np
# import networkx as nx

# import matplotlib.pyplot as plt

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class SegmentTree:

    def __init__(self, array, operator, identity):
        self.identity = identity
        self.operator = operator

        self.array_size = len(array)
        self.tree_height = (self.array_size - 1).bit_length()
        self.tree_size = 2 ** (self.tree_height + 1)
        self.leaf_start_index = 2 ** self.tree_height
        self.tree = [self.identity] * self.tree_size

        for i in range(self.array_size):
            x = 1 << (ord(array[i]) - 96)
            self.tree[self.leaf_start_index + i] = x

        for i in range(self.leaf_start_index - 1, 0, -1):
            self.tree[i] = self.operator(self.tree[i << 1], self.tree[i << 1 | 1])

    def update(self, index, val):
        x = 1 << (ord(val) - 96)

        cur_node = self.leaf_start_index + index
        self.tree[cur_node] = x

        while cur_node > 1:
            self.tree[cur_node >> 1] = self.operator(self.tree[cur_node], self.tree[cur_node ^ 1])
            cur_node >>= 1

    def query(self, begin, end):
        if begin < 0:
            begin = 0
        elif begin > self.array_size:
            return self.identity
        if end > self.array_size:
            end = self.array_size
        elif end < 1:
            return self.identity

        res = self.identity

        left = begin + self.leaf_start_index
        right = end + self.leaf_start_index

        while left < right:
            if left & 1:
                res = self.operator(res, self.tree[left])
                left += 1

            if right & 1:
                right -= 1
                res = self.operator(res, self.tree[right])

            left >>= 1
            right >>= 1

        return res


def main():
    from operator import or_
    n = int(input())
    s = input()
    q = int(input())

    seg = SegmentTree(s, or_, 0)

    for i in range(q):
        q1, q2, q3 = readline().split()
        q1, q2 = int(q1), int(q2)
        if q1 == 1:
            seg.update(q2-1, q3.rstrip("\n"))
        else:
            q3 = int(q3)
            print(bin(seg.query(q2-1, q3)).count("1"))


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        値の初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret

N = int(input())
S = input()
Q = int(input())
Seg = SegmentTree(N, lambda x, y: x | y, 0)

def a2n(a):
    return ord(a) - ord('a')

def createBit(a):
    return 1 << a2n(a)

for i, s in enumerate(S):
    Seg.set(i, createBit(s))
Seg.build()

for _ in range(Q):
    t, l, r = input().split()
    if int(t) == 1:
        Seg.update(int(l)-1, createBit(r))
    else:
        print(bin(Seg.query(int(l)-1, int(r))).count('1'))

# N = int(input())
# S = input()
# Q = int(input())
# queries = [list(input().split()) for _ in range(Q)]


# def a2n(a):
#     return ord(a)-ord("a")


# def createInp(a):
#     return 1 << a2n(a)


# Seg = SegmentTree(len(S), lambda x, y: x | y, init=0)
# for i, s in enumerate(S):
#     Seg.set(i, createInp(s))
# Seg.build()

# for q, l, r in queries:
#     if q == "1":
#         Seg.update(int(l)-1, createInp(r))
#     else:
#         print(bin(Seg.query(int(l)-1, int(r))).count('1'))

Submission status: Accepted

Solution code:
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


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


def a2n(a):
    return ord(a)-ord("a")


def createInp(a):
    return 1 << a2n(a)


Seg = SegmentTree(len(S), lambda x, y: x | y, init=0)
for i, s in enumerate(S):
    Seg.set(i, createInp(s))
Seg.build()

for q, l, r in queries:
    if q == "1":
        Seg.update(int(l)-1, createInp(r))
    else:
        print(bin(Seg.query(int(l)-1, int(r))).count('1'))

Submission status: Accepted

Solution code:
class SegmentTree():
    '''
    非再帰
    segment tree
    '''

    def __init__(self, n, func, init=float('inf')):
        '''
        n->配列の長さ
        func:func(a,b)->val,　func=minだとRMQになる
        木の高さhとすると,
        n:h-1までのノード数。h段目のノードにアクセスするために使う。
        data:ノード。
        parent:k->child k*2+1とk*2+2
        '''
        self.n = 2**(n-1).bit_length()
        self.init = init
        self.data = [init]*(2*self.n)
        self.func = func

    def set(self, k, v):
        '''
        あたいの初期化
        '''
        self.data[k+self.n-1] = v

    def build(self):
        '''
        setの後に一斉更新
        '''
        for k in reversed(range(self.n-1)):
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def update(self, k, a):
        '''
        list[k]=aに更新する。
        更新ぶんをrootまで更新
        '''
        k += self.n-1
        self.data[k] = a

        while k > 0:
            k = (k-1)//2
            self.data[k] = self.func(self.data[k*2+1], self.data[k*2+2])

    def query(self, l, r):
        '''
        [l,r)のfuncを求める
        '''
        L = l+self.n
        R = r+self.n
        ret = self.init
        while L < R:
            if R & 1:
                R -= 1
                ret = self.func(ret, self.data[R-1])
            if L & 1:
                ret = self.func(ret, self.data[L-1])
                L += 1
            L >>= 1
            R >>= 1
        return ret


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


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


def a2n(a):
    return ord(a)-ord("a")


def createInp(n):
    return 1 << n


Seg = SegmentTree(len(S), lam, init=0)
for i, s in enumerate(S):
    Seg.set(i, createInp(a2n(s)))
Seg.build()

for q, l, r in queries:
    if q == "1":
        Seg.update(int(l)-1, createInp(a2n(r)))
    else:
        print(bin(Seg.query(int(l)-1, int(r))).count('1'))

Submission status: Accepted

Solution code:
def popcount(x):
    return bin(x).count('1')

def initialize(N):
    i=1
    while i<N:
        i*=2
    return [0]*(2*i-1),i

def update(i,x):
    i+=d-1
    bit=ord(x)-97
    SEG[i]=0 | (1<<bit)
    while i>0:
        i=(i-1)//2
        SEG[i]=SEG[i*2+1]|SEG[i*2+2]
        
def find(a,b,k,l,r):
    if r<=a or b<=l:
        return 0
    if a<=l and r<=b:
        return SEG[k]
    else:
        c1=find(a,b,2*k+1,l,(l+r)//2)
        c2=find(a,b,2*k+2,(l+r)//2,r)
        return c1|c2
        
N=int(input())
S=input()
Q=int(input())
SEG,d=initialize(N)
for i in range(N):
    update(i,S[i])
for i in range(Q):
    com,s,t=map(str,input().split())
    if(com=='1'):
        update(int(s)-1,t)
    else:
        print(popcount(find(int(s)-1,int(t),0,0,d)))