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:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class SegmentTree:
  __slots__ = ['ide','n','seg','segfunc']

  def __init__(self,size,func,element):
    self.segfunc = func
    self.ide = element
    # self.size = sizeを超える最小の2冪の数
    self.n = 2 ** (n-1).bit_length()
    # 全てのnodeの数は(2*n-1)個
    # 上にn-1個,最下段にn個
    self.seg = [self.ide] * (2*self.n-1)

  def apply(self,array):
    arraysize = len(array)
    # 配列埋め込み
    for i in range(arraysize):
      self.seg[self.n-1+i] = array[i]
    # 上にあげる
    for i in range(self.n-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.n -1
    self.seg[k] = x
    while k:
      k = (k-1)//2
      self.seg[k] = self.segfunc(self.seg[2*k+1],self.seg[2*k+2])

  def query(self,l,r):
    # 半開区間[l,r)
    l += self.n-1; r += self.n-1
    vl = vr = self.ide
    while l < r:
      if l & 1 == 0:
        vl = self.segfunc(vl,self.seg[l])
        l += 1
      if r & 1 == 0:
        vr = self.segfunc(vr,self.seg[r-1])
      l = (l-1)//2; r = (r-1)//2
    return self.segfunc(vl,vr)

  def query1(self,l,r):
    # 半開区間[l,r)
    l += self.n-1; r += self.n-1
    res = self.ide
    while l < r:
      if l & 1 == 0:
        res = self.segfunc(res,self.seg[l])
        l += 1
      if r & 1 == 0:
        res = self.segfunc(res,self.seg[r-1])
      l = (l-1)//2; r = (r-1)//2
    return res

  def query2(self, p, q):
      if q <= p:
          return self.ide
      p += self.n - 1
      q += self.n - 2
      res = self.ide
      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 segor(a,b):
  return a|b

n = int(input())
st = SegmentTree(n,segor,0)
S = input()
data = [0] * n
for i,si in enumerate(S):
  k = ord(si)-ord("a")
  data[i] = 1 << k
st.apply(data)
Q = int(input())
for _ in range(Q):
  typo,a,b = input().split()
  if typo == "1":
    st.update(int(a)-1,1 << (ord(b)-ord("a")))
  if typo == "2":
    print(bin((st.query1(int(a)-1,int(b))))[2:].count("1"))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class SegmentTree:
  __slots__ = ['ide','n','seg','segfunc']

  def __init__(self,size,func,element):
    self.segfunc = func
    self.ide = element
    # self.size = sizeを超える最小の2冪の数
    self.n = 2 ** (n-1).bit_length()
    # 全てのnodeの数は(2*n-1)個
    # 上にn-1個,最下段にn個
    self.seg = [self.ide] * (2*self.n-1)

  def apply(self,array):
    arraysize = len(array)
    # 配列埋め込み
    for i in range(arraysize):
      self.seg[self.n-1+i] = array[i]
    # 上にあげる
    for i in range(self.n-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.n -1
    self.seg[k] = x
    while k:
      k = (k-1)//2
      self.seg[k] = self.segfunc(self.seg[2*k+1],self.seg[2*k+2])

  def query(self,l,r):
    # 半開区間[l,r)
    l += self.n-1; r += self.n-1
    vl = vr = self.ide
    while l < r:
      if l & 1 == 0:
        vl = self.segfunc(vl,self.seg[l])
        l += 1
      if r & 1 == 0:
        vr = self.segfunc(vr,self.seg[r-1])
      l = (l-1)//2; r = (r-1)//2
    return self.segfunc(vl,vr)

  def query2(self, p, q):
      if q <= p:
          return self.ide
      p += self.n - 1
      q += self.n - 2
      res = self.ide
      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 segor(a,b):
  return a|b

n = int(input())
st = SegmentTree(n,segor,0)
S = input()
data = [0] * n
for i,si in enumerate(S):
  k = ord(si)-ord("a")
  data[i] = 1 << k
st.apply(data)
Q = int(input())
for _ in range(Q):
  typo,a,b = input().split()
  if typo == "1":
    st.update(int(a)-1,1 << (ord(b)-ord("a")))
  if typo == "2":
    print(bin((st.query2(int(a)-1,int(b))))[2:].count("1"))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class SegmentTree:
  __slots__ = ['ide','n','seg','segfunc']

  def __init__(self,size,func,element):
    self.segfunc = func
    self.ide = element
    # self.size = sizeを超える最小の2冪の数
    self.n = 2 ** (n-1).bit_length()
    # 全てのnodeの数は(2*n-1)個
    # 上にn-1個,最下段にn個
    self.seg = [self.ide] * (2*self.n-1)

  def apply(self,array):
    arraysize = len(array)
    # 配列埋め込み
    for i in range(arraysize):
      self.seg[self.n-1+i] = array[i]
    # 上にあげる
    for i in range(self.n-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.n -1
    self.seg[k] = x
    while k:
      k = (k-1)//2
      self.seg[k] = self.segfunc(self.seg[2*k+1],self.seg[2*k+2])

  def query(self,l,r):
    # 半開区間[l,r)
    l += self.n-1; r += self.n-1
    vl = vr = self.ide
    while l < r:
      if l & 1 == 0:
        vl = self.segfunc(vl,self.seg[l])
        l += 1
      if r & 1 == 0:
        vr = self.segfunc(vr,self.seg[r-1])
      l = (l-1)//2; r = (r-1)//2
    return self.segfunc(vl,vr)

def segor(a,b):
  return a|b

n = int(input())
st = SegmentTree(n,segor,0)
S = input()
data = [0] * n
for i,si in enumerate(S):
  k = ord(si)-ord("a")
  data[i] = 1 << k
st.apply(data)
Q = int(input())
for _ in range(Q):
  typo,a,b = input().split()
  if typo == "1":
    st.update(int(a)-1,1 << (ord(b)-ord("a")))
  if typo == "2":
    print(bin((st.query(int(a)-1,int(b))))[2:].count("1"))

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

class SegmentTree:
  __slots__ = ['ide','n','seg','segfunc']

  def __init__(self,size,func,element):
    self.segfunc = func
    self.ide = element
    # self.size = sizeを超える最小の2冪の数
    self.n = 2 ** (n-1).bit_length()
    # 全てのnodeの数は(2*n-1)個
    # 上にn-1個,最下段にn個
    self.seg = [self.ide] * (2*self.n-1)

  def apply(self,array):
    arraysize = len(array)
    # 配列埋め込み
    for i in range(arraysize):
      self.seg[self.n-1+i] = array[i]
    # 上にあげる
    for i in range(self.n-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.n -1
    self.seg[k] = x
    while k:
      k = (k-1)//2
      self.seg[k] = self.segfunc(self.seg[2*k+1],self.seg[2*k+2])

  def notrec(self,l,r):
    # 半開区間[l,r)
    l += self.n-1; r += self.n-1
    vl = vr = self.ide
    while l < r:
      if l & 1 == 0:
        vl = self.segfunc(vl,self.seg[l])
        l += 1
      if r & 1 == 0:
        vr = self.segfunc(vr,self.seg[r-1])
      l = (l-1)//2; r = (r-1)//2
    return self.segfunc(vl,vr)

def makebin(s):
  k = ord(s)-ord("a")
  # print(1<<k,k)
  return 1 << k

def segfunc(a,b):
  return a | b

def out(n):
  count = 0
  while n:
    if n & 1 == 1:
      print(chr(ord("a")+count))
    n//=2
    count += 1

n = int(input())
st = SegmentTree(n,segfunc,0)
S = input()
for i,si in enumerate(S):
  st.update(i,makebin(si))
Q = int(input())
# print(st.seg)
# exit()
for _ in range(Q):
  typo,a,b = input().split()
  if typo == "1":
    st.update(int(a)-1,makebin(b))
  else:
    print(bin(st.notrec(int(a)-1,int(b)))[1:].count("1"))

Submission status: Accepted

Solution code:
class SegmentTree:

    def __init__(self, ls, ide, seg_func):
        n = len(ls)
        self.num = 2 ** (n - 1).bit_length()
        self.seg_func = seg_func
        self.ide = ide
        self.tree = [self.ide] * (2 * self.num - 1)
        for i, l in enumerate(ls):
            self.tree[i + self.num - 1] = l

        for i in range(self.num - 2, -1, -1):  # 子を束ねて親を更新
            self.tree[i] = seg_func(self.tree[2 * i + 1], self.tree[2 * i + 2])

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

    def query(self, l, r):
        if r < l:
            return ValueError('invalid index')

        l += self.num - 1
        r += self.num - 2
        res = self.ide
        while r - l > 1:  # 右から寄りながら結果を結合していくイメージ
            if l & 1 == 0:
                res = self.seg_func(res, self.tree[l])
            if r & 1 == 1:
                res = self.seg_func(res, self.tree[r])
                r -= 1
            l = l // 2  # 親の一つ右に移動
            r = (r - 1) // 2  # 親の一つ左に移動
        if l == r:
            res = self.seg_func(res, self.tree[l])
        else:
            res = self.seg_func(res, self.tree[l])
            res = self.seg_func(res, self.tree[r])
        return res


def f(a, b):
    return a | b


n = int(input())
s = [1 << (ord(r) - ord("a")) for r in input()]
q = int(input())
st = SegmentTree(s, 0, f)

for _ in range(q):
    m, i, c = input().split()

    if int(m) - 1:
        x = st.query(int(i)-1, int(c))
        print(bin(x).count("1"))
    else:
        st.update(int(i)-1, 1 << (ord(c) - ord("a")))

Submission status: Accepted

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]
import sys
sys.setrecursionlimit(10**6)

n=i1()
s=input()
q=i1()
N=0
while n:
  n>>=1
  N+=1
n=2**N

t=[0 for i in range(2*n-1)]

def ud(i,x):
  i+=n-1
  t[i]=x
  while i:
    i=(i-1)//2
    t[i]=t[i*2+1] | t[i*2+2]

def qr(a,b,k,l,r):
  
  if r<=a or b<=l:
     return 0
  elif a<=l and r<=b:
     
     return t[k]
  else:
     return qr(a,b,k*2+1,l,(l+r)//2) | qr(a,b,k*2+2,(l+r)//2,r)

for i in range(len(s)):
  ud(i,1<<(ord(s[i])-ord("a")))

while q:
 [ty,i,c]=[i for i in input().split()]
 ty=int(ty)
 i=int(i)
 if ty==1:
   ud(i-1,1<<(ord(c)-ord("a")))
 else:
   c=int(c)
   x=0
   z=qr(i-1,c,0,0,n)
   while z:
     if z%2==1:
        x+=1
     z>>=1
   print(x)
 q-=1

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n = int(input())

ss = list(input())
s = []
for i in range(n):
    s.append(1<<(ord(ss[i])-97))

#####segfunc######
def segfunc(x,y):
    #print(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,k,l,r):
    if r<=p or q<=l:
        return ide_ele
    if p<=l and r<=q:
        return seg[k]
    else:
        vl = query(p,q,k*2+1,l,(r+l)//2)
        vr = query(p,q,k*2+2,(l+r)//2,r)
        return segfunc(vl,vr)

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

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


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c

q = int(input())

for i in range(q):
    qq,xx,yy = map(str,input().split())
    if qq == '1':
        xx = int(xx)
        update(xx-1,1<<(ord(yy)-97))
    else:
        xx,yy = int(xx),int(yy)
        res = query(xx-1,yy,0,0,num)
        print(popcnt(res))

Submission status: Accepted

Solution code:
N = int(input())
S = list(input())
Q = int(input())


#セグメント木
#次の2つの処理をO(log N)で実施することができる
# s, tが与えられた時、区間[s, t)の最小値を求める
# i, xが与えられた時、a_iの値をxに変更する

# INIT = 10 ** 18 #初期値 答えに関係ないもの
MAX_N = 10 ** 6 #与えられる要素数の最大

data = [0] * (2 * MAX_N - 1) #MAX_Nで初期化

#ここに機能をもたせる
def func(vl, vr):
    return (vl | vr)

def init(n_):
    #簡単のため要素数を2のべき乗に
    n = 1
    while n < n_:
        n *= 2
    return n

n = init(N)

def update(k, a): #k番目の値をaに変更 0-index
    # B[a] = k
    k += n - 1
    data[k] = (1 << a)
    while k > 0: #登りながら更新
        k = (k - 1)//2
        data[k] = func(data[k * 2 + 1], data[k * 2 + 2])

def query(a, b, k = 0, l = 0, r = n):
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return data[k]
    else:
        vl = query(a, b, k * 2 + 1, l, (l + r)//2)
        vr = query(a, b, k * 2 + 2, (l + r)//2, r)
        return func(vl, vr)

def initialize(A): #リストAを与えて初期化する
    for i, a in enumerate(A):
        data[i + n - 1] = (1 << (ord(a) - 97))
        # B[a] = i
    for i in range((2 * n - 3)//2, -1, -1):
        data[i] = func(data[i * 2 + 1], data[i * 2 + 2])

# def index(a): #要素aがもとのどこに保存されているかを返す関数
#     return B[a]

# def value(index): #indexが与えられた時、index番目の値を得る
#     return data[index + n - 1]

#初期値の入力
initialize(S)

# print (data)

#クエリの数
# Q = int(input())
for _ in range(Q):
    a, b, c = map(str, input().split())
    if a == '1':
        update(int(b) - 1, (ord(c) - 97))
    else:
        tmp = query(int(b) - 1, int(c))
        count = 0
        for j in range(26):
            if (tmp >> j) & 1 == 1:
                count += 1
        # print (tmp)
        print (count)
# print (data)

Submission status: Accepted

Solution code:
# どの文字を持っているかを二進数で1000101010...と表す
# or で足していく
class SegmentTree:
  arr=None
  tree=None
  n=0
  # 結果に影響を与えないdefault value
  DEF=0

  def __init__(self,arr):
    self.arr=arr
    size=len(arr)
    # n階層目は2**(n-1)要素
    self.n=1
    while self.n<size:
      self.n*=2
    self.tree=[self.DEF]*(2*self.n-1)
    # 親=(n-1)//2
    # 子=2*n+1,2*n+2
    # 最下階層の要素を埋めていく
    for i in range(size):
      self.tree[i+self.n-1]=arr[i]
    for i in range(self.n-2,-1,-1):
      self.tree[i]=self.__choose__(self.tree[2*i+1],self.tree[2*i+2])
    
    
  # 区間からの代表値の選び方を定義する（最小値を選ぶ場合はminなど）
  def __choose__(self,a,b):
    return a | b
  
  # 添字xをvalで更新する
  def update(self,x,val):
    x+=self.n-1
    self.tree[x]=val
    while x>0:
      x=(x-1)//2
      self.tree[x]=self.__choose__(self.tree[2*x+1],self.tree[2*x+2])
      
  # 対象区間[a,b)の値を求めるクエリ (bは含まないので注意)
  # k:自分がいるノードのindex
  # [l,r):検査する区間
  def get_val(self,a,b,k=0,l=0,r=-1):
    # 最初に呼び出されたときは対象区間が[0,N)
    if r<0:
      r=self.n
      
    # 要求区間と対象区間が交わらない
    if r<=a or b<=l:
      return self.DEF
    
    # 要求区間が対象区間を完全に満たす->対象区間を計算に使用する
    if a<=l and r<=b:
      return self.tree[k]
    
    # 要求区間が対象区間の一部を満たす->子を探索
    ll=self.get_val(a,b,2*k+1,l,(l+r)//2)
    rr=self.get_val(a,b,2*k+2,(l+r)//2,r)
    
    return self.__choose__(ll,rr)
    
  def show(self):
    print("----")
    print(list(map(bin,self.tree)))
    print(self.tree)
    
base=ord("a")
ALPHA="abcdefghijklmnopqrstuvwxyz"
def change_alpha_to_num(c):
  if c not in ALPHA:
    return 0
  return 1<<(ord(c)-base)

import sys
readline=sys.stdin.readline

N=int(readline())
S=readline()
Sarr=list(map(change_alpha_to_num,list(S)))
ST=SegmentTree(Sarr)
Q=int(readline())
for i in range(Q):
  q=list(readline().split())
  if q[0]=="1":
    i,c=int(q[1])-1,q[2]
    ST.update(i,change_alpha_to_num(c))
  elif q[0]=="2":
    l,r=int(q[1])-1,int(q[2])-1
    print(bin(ST.get_val(l,r+1)).count("1"))

Submission status: Accepted

Solution code:
# どの文字を持っているかを二進数で1000101010...と表す
# or で足していく
class SegmentTree:
  arr=None
  tree=None
  n=0
  # 結果に影響を与えないdefault value
  DEF=0

  def __init__(self,arr):
  #  print("arr",arr)
    self.arr=arr
    size=len(arr)
    # n階層目は2**(n-1)要素
    self.n=1
    while self.n<size:
      self.n*=2
    self.tree=[self.DEF]*(2*self.n-1)
    # 親=(n-1)//2
    # 子=2*n+1,2*n+2
    # 最下階層の要素を埋めていく
    for i in range(size):
    #  print(arr[i])
      self.tree[i+self.n-1]=arr[i]
    for i in range(self.n-2,-1,-1):
      self.tree[i]=self.__choose__(self.tree[2*i+1],self.tree[2*i+2])
    
    
  # 区間からの代表値の選び方を定義する（最小値を選ぶ場合はminなど）
  def __choose__(self,a,b):
    #print("a",a,"b",b)
    return a | b
  
  # 添字xをvalで更新する
  def update(self,x,val):
    x+=self.n-1
  #  print("x",x,"val",val)
    self.tree[x]=val
    while x>0:
      x=(x-1)//2
      self.tree[x]=self.__choose__(self.tree[2*x+1],self.tree[2*x+2])
      
  # 対象区間[a,b)の値を求めるクエリ (bは含まないので注意)
  # k:自分がいるノードのindex
  # [l,r):検査する区間
  def get_val(self,a,b,k=0,l=0,r=-1):
    # 最初に呼び出されたときは対象区間が[0,N)
    if r<0:
      r=self.n
      
    # 要求区間と対象区間が交わらない
    if r<=a or b<=l:
      return self.DEF
    
    # 要求区間が対象区間を完全に満たす->対象区間を計算に使用する
    if a<=l and r<=b:
      return self.tree[k]
    
    # 要求区間が対象区間の一部を満たす->子を探索
    ll=self.get_val(a,b,2*k+1,l,(l+r)//2)
    rr=self.get_val(a,b,2*k+2,(l+r)//2,r)
    
    return self.__choose__(ll,rr)
    
  def show(self):
    print("----")
    print(list(map(bin,self.tree)))
    print(self.tree)
    
base=ord("a")
ALPHA="abcdefghijklmnopqrstuvwxyz"
def change_alpha_to_num(c):
  if c not in ALPHA:
    return 0
  # print("c",c,"ord(c)",ord(c),"base",base)
  return 1<<(ord(c)-base)

import sys
readline=sys.stdin.readline

N=int(readline())
S=readline()
Sarr=list(map(change_alpha_to_num,list(S)))
ST=SegmentTree(Sarr)
#ST.show()
Q=int(readline())
for i in range(Q):
  q=list(readline().split())
  if q[0]=="1":
    #print("q",q)
    i,c=int(q[1])-1,q[2]
    ST.update(i,change_alpha_to_num(c))
    #ST.show()
  elif q[0]=="2":
    l,r=int(q[1])-1,int(q[2])-1
  #  print(ST.get_val(l,r+1))
    print(bin(ST.get_val(l,r+1)).count("1"))

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines


def string_to_number(a):
    return 1 << (ord(a) - ord("a"))

class SegmentTree:
    def __init__(self, A):
        self.n = 2**(len(A)-1).bit_length()
        self.identity = 0
        self.seg = [self.identity] * (2 * self.n)
        
        for i, a in enumerate(A):
            self.seg[self.n-1+i] = string_to_number(a)
        for i in range(self.n-2,-1,-1):
            self.seg[i] = self.seg[2*i+1] | self.seg[2*i+2]

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

            
    def query(self, a, b):
        if b == a:
        	return 1
        a += self.n - 1
        b += self.n - 2
        res = self.identity
        while b - a > 1:
            if a & 1 == 0:
                res |= self.seg[a]
            if b & 1 == 1:
                res |= self.seg[b]
                b -= 1
            a = a // 2
            b = (b - 1) // 2
        if a == b:
            res |= self.seg[a]
        else:
            res |= (self.seg[a] | self.seg[b])
        
        return bin(res).count("1")


def main():
    N = int(readline())
    s = readline().strip()
    seg = SegmentTree(list(s))
    #print(seg.seg)

    Q = int(readline())
    for _ in range(Q):
        q, a, b = map(str, readline().split())
        if q == "1":
            seg.update(int(a)-1, b)
        else:
            print(seg.query(int(a)-1, int(b)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import bisect

def main():
    n = int(input())
    s = bytearray(input().encode())
    q = int(input())

    alpha = [ord('a')+i for i in range(26)]
    alpha_map = {c: [] for c in alpha}
    for i, c in enumerate(s):
        bisect.insort(alpha_map[c], i+1)

    for _ in range(q):
        t, a, b = [p for p in input().split()]
        t = int(t)
        a = int(a)
        if t == 1:
            char = s[a-1]
            b = ord(b)
            if char == b:
                continue
            src_lst = alpha_map[char]
            dst_lst = alpha_map[b]
            idx = bisect.bisect_left(src_lst, a)
            if idx < len(src_lst):
                src_lst.pop(idx)
            bisect.insort(dst_lst, a)
            s[a-1] = b
        else:
            b = int(b)
            cnt = 0
            for _, lst in alpha_map.items():
                idx = bisect.bisect_left(lst, a)
                if idx < len(lst) and lst[idx] <= b:
                    cnt +=1
            print(cnt)
main()

Submission status: Accepted

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

n = int(input())
s = list(str(input()))
s = [{ord(c)-ord('a')} for c in s]

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[2*k+1], seg[2*k+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%2 == 0:
            res = segfunc(res, seg[p])
        if q%2 == 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

# identity element
ide_ele = set()

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

init(s)

q = int(input())
for _ in range(q):
    t, x, y = map(str, input().split())
    if t == '1':
        i = int(x)-1
        c = {ord(y)-ord('a')}
        update(i, c)
    else:
        l = int(x)-1
        r = int(y)-1
        print(len(query(l, r+1)))

Submission status: Accepted

Solution code:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp:
      seg[c][tmp] -= 1
      tmp >>= 1
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp:
      seg[b][tmp] += 1
      tmp >>= 1
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp-1:
          if tmp & 1:
            l += seg[d][tmp-1]
          tmp >>= 1
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp-1:
        if tmp & 1:
          r += seg[d][tmp-1]
        tmp >>= 1
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

Submission status: Accepted

Solution code:
#13:19
n = int(input())
s = input()
t = []
for i in range(n):
  t.append(ord(s[i])-97)
q = int(input())
scale = 19
seg = [[0 for _ in range(2**(scale+1))] for _ in range(26)]
for i in range(n):
  tmp = int(i) + 2 ** scale
  x = t[i]
  while tmp != 0:
    seg[x][tmp] += 1
    tmp //= 2
#print(seg)
raw = []
for _ in range(q):
  d,a,b = input().split()
  d = int(d)
  if d == 1:
    a = int(a) - 1
    b = ord(b) - 97
  else:
    a = int(a) - 2
    b = int(b) - 1
  raw.append([d,a,b])
for p in range(q):
  d,a,b = raw[p]
  if d == 1:
    tmp = int(a)
    c = t[tmp]
    tmp += 2**scale
    while tmp != 0:
      seg[c][tmp] -= 1
      tmp >>= 1
    tmp = int(a)
    t[tmp] = b
    tmp += 2**scale
    while tmp != 0:
      seg[b][tmp] += 1
      tmp >>= 1
  else:
    ans = 0
    for d in range(26):
      l = 0
      r = 0
      if a == -1:
        l = 0
      else:
        tmp = a + 2**scale
        l += seg[d][tmp]
        while tmp != 1:
          if tmp & 1:
            l += seg[d][tmp-1]
          tmp >>= 1
      tmp = b + 2**scale
      r += seg[d][tmp]
      while tmp != 1:
        if tmp & 1:
          r += seg[d][tmp-1]
        tmp >>= 1
      if r > l:
        ans += 1
      #print(d,r,l)
    print(ans)
#print(t)

Submission status: Accepted

Solution code:


# 点更新，区間クエリ
class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return x|y

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

A = [0]*N
atmp = ord('a')

for i in range(N):
    A[i] = 1<<(ord(S[i])-atmp)
    
seg = SegTree(N,A,segfunc,0)
popcount = lambda x: bin(x).count('1')

ans = []
for i in range(Q):
    t,l,r = map(str,input().split())
    if t=='1':
        i = int(l)-1
        c = r
        upt = 1<<(ord(c)-atmp)
        seg.update(i,upt)
        
    else:
        l,r = int(l)-1,int(r)
        ans.append(popcount(seg.query(l,r)))

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
"""segfunc"""


# 論理和を返す
def segfunc(x, y):
    return x | y


def init(init_val):
    # set_val
    for i in range(N):
        seg[i-1+num] = init_val[i]

    # built
    for i in range(num-2, -1, -1):  # 木の下の方から埋めていく, nではなくnumであることに注意
        seg[i] = segfunc(seg[2*i+1], seg[2*i+2])  # 子のインデックス


# 更新
def update(k, x):
    k += num-1  # 場所kに対するseg木の葉のindex?
    seg[k] = x
    while k:
        k = (k-1)//2  # 親のノードのindexを取得
        seg[k] = segfunc(seg[2*k+1], seg[2*k+2])


def query(p, q):
    if q <= p:  # 半開区間なので、等しくてもアウト？
        return ide_ele
    p += num-1
    q += num-2  # 半開区間なので、q側を-2している？
    res = ide_ele
    while q-p > 1:
        if p % 2 == 0:
            res = segfunc(res, seg[p])
        if q % 2 == 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

N = int(input())
ss = list(input())
s = []
for i in range(N):
    s.append(1<<(ord(ss[i]))-97)

# num: n以上の最小の2のベキ乗
num = 2**(N-1).bit_length()
seg = [ide_ele]*2*num

init(s)


def popcnt(n):
    c = (n & 0x5555555555555555) + ((n>>1) & 0x5555555555555555)
    c = (c & 0x3333333333333333) + ((c>>2) & 0x3333333333333333)
    c = (c & 0x0f0f0f0f0f0f0f0f) + ((c>>4) & 0x0f0f0f0f0f0f0f0f)
    c = (c & 0x00ff00ff00ff00ff) + ((c>>8) & 0x00ff00ff00ff00ff)
    c = (c & 0x0000ffff0000ffff) + ((c>>16) & 0x0000ffff0000ffff)
    c = (c & 0x00000000ffffffff) + ((c>>32) & 0x00000000ffffffff)
    return c


q = int(input())
for i in range(q):
    qq, xx, yy = map(str, input().split())
    if qq == '1':
        xx = int(xx)
        update(xx-1,1<<(ord(yy)-97))
    else:
        xx, yy = int(xx), int(yy)
        res = query(xx-1,yy)
        print(popcnt(res))