Problem:


Score : 500 points

Problem Statement

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

Process Q queries of the following two types:

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

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

Constraints

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

S is a string consisting of lowercase English letters.

c_q is a lowercase English letter.

1 \leq N \leq 500000

1 \leq Q \leq 20000

|S| = N

1 \leq i_q \leq N

1 \leq l_q \leq r_q \leq N

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

Input

Input is given from Standard Input in the following format:

N
S
Q
Query_1
\vdots
Query_Q

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

1 i_q c_q

2 l_q r_q

Output

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

Sample Input 1

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

Sample Output 1

3
1
5

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

In the second query, S is modified to abcdzbd.

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

In the fourth query, S is modified to abcazbd.

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

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



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


Sample output:
3
1
5

Submission status: Accepted

Solution code:
from collections import defaultdict
import bisect

n = int(input())
s = input()
S = []
cnt_ch = defaultdict(list)
for i in range(n):
    S.append(s[i])
    cnt_ch[s[i]].append(i)
    
    
    
    
q = int(input())
for i in range(q):
    qw = input()
    if qw[0] == "1":
        qw = qw[2:]
        i, ch = map(str, qw.split())
        if S[int(i) - 1] == ch:
            continue
        remove = bisect.bisect_left(cnt_ch[S[int(i) - 1]], int(i) - 1)
        del cnt_ch[S[int(i) - 1]][remove]
        S[int(i) - 1] = ch
        if not cnt_ch[ch]:
            cnt_ch[ch].append(int(i) - 1)
            continue
        bisect.insort_left(cnt_ch[ch], int(i) - 1)
        
        
    else:
        #print(cnt_ch)
        qw = qw[2:]
        l, r = map(int, qw.split())
        cnt = 0
        for i in range(ord("a"),ord("a") + 26):
            if not cnt_ch[chr(i)]:
                continue
            edge = bisect.bisect_left(cnt_ch[chr(i)], l - 1)
            #print(cnt_ch[chr(i)][edge - 1:])
            #if bisect.bisect_left(cnt_ch[chr(i)][edge:], i) < r:
            #print(cnt_ch[chr(i)])
            #print(l, r)
            #print(edge)
            if edge < len(cnt_ch[chr(i)]):
                if cnt_ch[chr(i)][edge] < r:
                    cnt += 1
            #print(cnt, "cnt", chr(i))
        print(cnt)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = input().rstrip()
Q = int(input())
qs = [input().split() for i in range(Q)]

def ctoi(c):
    return ord(c) - ord('a')

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w): # 0-indexed
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def _sum(self,x): # 1-indexed
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
    def sum(self,l,r): # [l,r)
        return self._sum(r) - self._sum(l)
bits = [BinaryIndexedTree(N) for _ in range(26)]

for i,c in enumerate(S):
    bits[ctoi(c)].add(i,1)

s = list(S)
ans = []
for a,b,c in qs:
    if a=='1':
        x = int(b)-1
        bits[ctoi(c)].add(x,1)
        bits[ctoi(s[x])].add(x,-1)
        s[x] = c
    else:
        b,c = int(b)-1,int(c)
        tmp = 0
        for i in range(26):
            if bits[i].sum(b,c) > 0:
                tmp += 1
        ans.append(tmp)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = input().rstrip()
Q = int(input())
qs = [input().split() for i in range(Q)]

def ctoi(c):
    return ord(c) - ord('a')

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w):
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def _sum(self,x):
        x += 1
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
    def sum(self,l,r):
        return self._sum(r-1) - self._sum(l-1)
bits = [BinaryIndexedTree(N) for _ in range(26)]

for i,c in enumerate(S):
    bits[ctoi(c)].add(i,1)

s = list(S)
ans = []
for a,b,c in qs:
    if a=='1':
        x = int(b)-1
        bits[ctoi(c)].add(x,1)
        bits[ctoi(s[x])].add(x,-1)
        s[x] = c
    else:
        b,c = int(b)-1,int(c)
        tmp = 0
        for i in range(26):
            if bits[i].sum(b,c) > 0:
                tmp += 1
        ans.append(tmp)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = input().rstrip()
Q = int(input())
qs = [input().split() for i in range(Q)]

def ctoi(c):
    return ord(c) - ord('a')

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w):
        x += 1
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def sum(self,x):
        x += 1
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
bits = [BinaryIndexedTree(N) for _ in range(26)]

for i,c in enumerate(S):
    bits[ctoi(c)].add(i,1)

s = list(S)
ans = []
for a,b,c in qs:
    if a=='1':
        x = int(b)-1
        bits[ctoi(c)].add(x,1)
        bits[ctoi(s[x])].add(x,-1)
        s[x] = c
    else:
        b,c = int(b)-1,int(c)-1
        tmp = 0
        for i in range(26):
            if bits[i].sum(c) - bits[i].sum(b-1) > 0:
                tmp += 1
        ans.append(tmp)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
S = input().rstrip()
Q = int(input())
qs = [input().split() for i in range(Q)]

def ctoi(c):
    return ord(c) - ord('a')

class BinaryIndexedTree:
    def __init__(self,size):
        self.N = size
        self.bit = [0]*(size+1)
    def add(self,x,w):
        while x <= self.N:
            self.bit[x] += w
            x += (x & -x)
    def sum(self,x):
        ret = 0
        while x > 0:
            ret += self.bit[x]
            x -= (x & -x)
        return ret
bits = [BinaryIndexedTree(N) for _ in range(26)]

for i,c in enumerate(S):
    bits[ctoi(c)].add(i+1,1)

s = list(S)
ans = []
for a,b,c in qs:
    if a=='1':
        x = int(b)
        bits[ctoi(c)].add(x,1)
        bits[ctoi(s[x-1])].add(x,-1)
        s[x-1] = c
    else:
        tmp = 0
        for i in range(26):
            if bits[i].sum(int(c)) - bits[i].sum(int(b)-1) > 0:
                tmp += 1
        ans.append(tmp)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import bisect
import sys
def input(): return sys.stdin.readline().rstrip()

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

char_idx = [[] for _ in range(26)]
for i in range(n):
    char_idx[ord(s[i])-ord('a')].append(i)
# print(char_idx)

query = [input().split() for _ in range(q)]
# print(query)

for t, a, b in query:
    if t=='1':
        i = int(a) - 1
        if s[i] == b:
            continue
        else:
            idx = bisect.bisect_left(char_idx[ord(s[i])-ord('a')], i)
            if char_idx[ord(s[i])-ord('a')][idx] == i:
                del char_idx[ord(s[i])-ord('a')][idx]
            bisect.insort_left(char_idx[ord(b)-ord('a')], i)
            s[i] = b
    else:
        l = int(a) - 1
        r = int(b) - 1
        ans = 0
        for i in range(26):
            if len(char_idx[i]) == 0:
                continue
            it = bisect.bisect_left(char_idx[i], l)
            if it < len(char_idx[i]) and char_idx[i][it] <= r:
                ans += 1
        print(ans)

Submission status: Accepted

Solution code:
"""
AtCoder Beginner Contest 157  E - Simple String Queries

文字列Sに対して、
クエリ1：i番目の文字をcに変更
クエリ2：S[l~r]に何種類の文字があるか

各クエリについて、律儀に文字を変えて、l~rについて何種類あるか調べると間に合わないはず。

~~~ABCCDC~~~
        ↑を別の文字にした時に、最後に出てくるCがその二個左、のような情報をちゃんと残したい。
→ 最後の位置が知りたいとかではなく、lとrを指定した時に、その間にあるかが知りたい（具体的な位置が知りたいわけではない）
　そうするt、a〜zについて、l~rに存在するか、みたいな確認ができそう

N <= 5 * 10**5
Q <= 2 * 10**4
なので、bisect使えば間に合うのか？よくわからん

Sとしてではなく、現時点で何文字目がなになのかも持っておいたほうが楽か。

"""

import bisect

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

# 現時点でどこに何があるか
cS = [""] * N
# ある文字の位置
char_idxs = [[]for _  in range(26)]

# i番目は文字s、を保存
for i,s in enumerate(S):
    cS[i] = s
    char_idxs[ord(s) - 97].append(i)

query = [tuple(map(str, input().split())) for _ in range(Q)]




for q,a,b in query:
    
    # q == 1の時、a番目の文字をbに置き換え
    if q == "1":
        # 現時点の文字と置き換え後が同じなら何もしない
        if cS[int(a) - 1] == b:
            continue
        else:
            #print("---", char_idxs[ord(cS[]) - 97], int(a)-1, bisect.bisect_right(char_idxs[ord(b) - 97], int(a)-1))
            # a番目の文字を書き換える

            
            idx = bisect.bisect_right(char_idxs[ord(cS[int(a)-1]) - 97], int(a)-1)
            # idxの左の値がa番目であれば、それを消す
            if char_idxs[ord(cS[int(a)-1]) - 97][idx-1] == int(a)-1:
                # delの方が早いか？
                char_idxs[ord(cS[int(a)-1]) - 97][idx-1:idx] = []
            
            # bの文字がa番目にあるよ、を保存
            bisect.insort_right(char_idxs[ord(b) - 97], int(a) - 1)

            # 置き換え
            cS[int(a) - 1] = b

    # q == 2の時、範囲の文字種の個数を調べる
    else:
        cnt = 0
        for i in range(26):
            # そもそもその文字が文字列全体になければ考えない
            if len(char_idxs[i]) == 0: continue
            # bisect_leftで a-1 を入れられる場所を探して、その時に右にある値がb-1以下であれば含まれる
            l = bisect.bisect_left(char_idxs[i], int(a)-1)
            #r = bisect.bisect_right(char_idxs[i], int(b)-1)

            # char_idxs[i][l]はa-1より右に文字種iが初めて出てくる位置なので、それがb-1を含む右側にあればOK
            if l < len(char_idxs[i]) and char_idxs[i][l] <= int(b)-1:
                cnt += 1

        print(cnt)

Submission status: Accepted

Solution code:

import bisect

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

# 現時点でどこに何があるか
cS = [""] * N
# ある文字の位置
char_idxs = [[]for _  in range(26)]

# i番目は文字s、を保存
for i,s in enumerate(S):
    cS[i] = s
    char_idxs[ord(s) - 97].append(i)

query = [tuple(map(str, input().split())) for _ in range(Q)]




for q,a,b in query:
    
    # q == 1の時、a番目の文字をbに置き換え
    if q == "1":
        # 現時点の文字と置き換え後が同じなら何もしない
        if cS[int(a) - 1] == b:
            continue
        else:
            #print("---", char_idxs[ord(cS[]) - 97], int(a)-1, bisect.bisect_right(char_idxs[ord(b) - 97], int(a)-1))
            # a番目の文字を書き換える

            
            idx = bisect.bisect_right(char_idxs[ord(cS[int(a)-1]) - 97], int(a)-1)
            # idxの左の値がa番目であれば、それを消す
            if char_idxs[ord(cS[int(a)-1]) - 97][idx-1] == int(a)-1:
                # delの方が早いか？
                char_idxs[ord(cS[int(a)-1]) - 97][idx-1:idx] = []
            
            # bの文字がa番目にあるよ、を保存
            bisect.insort_right(char_idxs[ord(b) - 97], int(a) - 1)

            # 置き換え
            cS[int(a) - 1] = b

    # q == 2の時、範囲の文字種の個数を調べる
    else:
        cnt = 0
        for i in range(26):
            # そもそもその文字が文字列全体になければ考えない
            if len(char_idxs[i]) == 0: continue
            # bisect_leftで a-1 を入れられる場所を探して、その時に右にある値がb-1以下であれば含まれる
            l = bisect.bisect_left(char_idxs[i], int(a)-1)
            #r = bisect.bisect_right(char_idxs[i], int(b)-1)

            # char_idxs[i][l]はa-1より右に文字種iが初めて出てくる位置なので、それがb-1を含む右側にあればOK
            if l < len(char_idxs[i]) and char_idxs[i][l] <= int(b)-1:
                cnt += 1

        print(cnt)

Submission status: Accepted

Solution code:
import sys;input=sys.stdin.readline
n=int(input())
s=input()
num=2**(n-1).bit_length()
def segfunc(x,y):return x|y
seg=[0]*(2*num-1)
for i in range(n):seg[i+num-1]=2**(ord(s[i])-97)
for i in range(num-2,-1,-1):seg[i]=segfunc(seg[2*i+1],seg[2*i+2])
def update(i,x):
  i+=num-1;seg[i]=x
  while i:i=(i-1)//2;seg[i]=segfunc(seg[i*2+1],seg[i*2+2])
def query(l,r):
  l+=num-1;r+=num-1
  if l==r:return seg[l]
  s=seg[l];l+=1
  while r-l>1:
    if ~l%2:s=segfunc(seg[l],s)
    if r%2:s=segfunc(seg[r],s);r-=1
    l//=2;r=(r-1)//2
  if l==r:return segfunc(s,seg[l])
  return segfunc(s,segfunc(seg[l],seg[r]))
for _ in range(int(input())):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,2**(ord(c)-97))
  else:
    _,l,r=quer
    print(sum(map(int,bin(query(int(l)-1,int(r)-1))[2:])))

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  input=b.readline
  n=int(input())
  d=[set()for _ in range(n)]+[{c}for c in input()]
  for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
  r=[]
  add=r.append
  input()
  for q,a,b in zip(*[iter(b.read().split())]*3):
    i=int(a)+n-1
    if q<b'2':
      d[i]={b[0]}
      while i:
        i>>=1
        d[i]=d[i+i]|d[i-~i]
      continue
    j=int(b)+n
    s=set()
    while i<j:
      if i&1:
        s|=d[i]
        i+=1
      if j&1:
        j-=1
        s|=d[j]
      i>>=1
      j>>=1
    add(len(s))
  print(' '.join(map(str,r)))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  input=b.readline
  n=int(input())
  d=[0]*n+[1<<c-97for c in input()[:n]]
  for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
  r=[]
  add=r.append
  input()
  for q,a,b in zip(*[iter(b.read().split())]*3):
    i,s=int(a)+n-1,0
    if q<b'2':
      d[i]=1<<b[0]-97
      while i:
        i>>=1
        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>>=1
      j>>=1
    add(bin(s).count('1'))
  print(' '.join(map(str,r)))
main()

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  input=b.readline
  n=int(input())
  d=[0]*n+[1<<c-97for c in input()[:n]]
  for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
  r=[]
  input()
  for q,a,b in zip(*[iter(b.read().split())]*3):
    i,s=int(a)+n-1,0
    if q<b'2':
      d[i]=1<<b[0]-97
      while i:
        i>>=1
        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>>=1
      j>>=1
    r+=bin(s).count('1'),
  print(' '.join(map(str,r)))
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  input=b.readline
  n=int(input())
  d=[0]*n+[1<<c-97for c in input()[:n]]
  for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
  r=[]
  input()
  for q,a,b in zip(*[iter(b.read().split())]*3):
    i,s=int(a)+n-1,0
    if q<b'2':
      d[i]=1<<b[0]-97
      while i:
        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
    r+=bin(s).count('1'),
  print(' '.join(map(str,r)))
main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
  import sys
  n,s,_,*t=sys.stdin.buffer.read().split()
  n=int(n)
  d=[0]*n+[2**(c-97)for c in s]
  for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
  r=[]
  for q,a,b in zip(*[iter(t)]*3):
    i,s=int(a)+n-1,0
    if q<b'2':
      d[i]=2**(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
    r+=bin(s).count('1'),
  print(' '.join(map(str,r)))
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]
  r=[]
  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
    r+=bin(s).count('1'),
  print(' '.join(map(str,r)))
main()

Submission status: Accepted

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

class SegmentTree:
    def __init__(self, n, func=lambda x, y: min(x, y), ide=float("inf")):
        self.n = 2 ** (n-1).bit_length()
        self.data = [ide] * (self.n*2)
        self.func, self.ide = func, ide
    
    def build(self, data):
        for i, x in enumerate(data):
            self.data[self.n+i] = x
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def update(self, i, x):
        i += self.n
        self.data[i] = x
        while i > 1:
            i //= 2
            self.data[i] = self.func(self.data[i*2], self.data[i*2+1])

    def query(self, l, r):
        l += self.n; r += self.n 
        res = self.ide
        while l < r:
            if l & 1:
                res = self.func(res, self.data[l])
                l += 1
            if r & 1:
                res = self.func(res, self.data[r-1])
            l //= 2; r //= 2
        return res
    
    def get(self, i):
        return self.data[self.n + i]

st = [SegmentTree(n, lambda x, y: x+y, 0) for _ in range(26)]
for i, c in enumerate(s): st[ord(c)-97].update(i, 1)

for _ in range(q):
    a, b, c = input().split()
    if a == "1":
        idx = int(b)-1
        for i in range(26):
            st[i].update(idx, 0)
        st[ord(c)-97].update(idx, 1)
    else:
        l, r = int(b)-1, int(c)
        res = 0
        for i in range(26):
            res += bool(st[i].query(l, r))
        print(res)

Submission status: Accepted

Solution code:
SIZE = 2**20 # 2**20 > N=500000

class SegmentTree:
    def __init__(self, size):
        self.size = size
        self.seg = [0] * (2 * size)

    def update(self, pos, ch):
        # update leaf
        i = self.size + pos - 1
        self.seg[i] = 1 << (ord(ch)-ord('a'))
        # update tree
        while i > 0:
            i = (i - 1) // 2
            self.seg[i] = self.seg[i*2+1] | self.seg[i*2+2]

    def _query(self, a, b, k, left, right):
        if right<a or b<left:
            return 0
        if a<=left and right<=b:
            return self.seg[k]

        vl = self._query(a,b,k*2+1, left, (left+right)//2)
        vr = self._query(a,b,k*2+2, (left+right)//2+1, right)
        return vl | vr

    def query(self, a, b):
        return self._query(a,b,0,0,self.size-1)


def resolve():
    N = int(input())
    S = input().strip()
    Q = int(input())
    table = [[] for _ in range(26)]
    sg = SegmentTree(SIZE)
    for i,ch in enumerate(S):
        sg.update(i, ch)

    for i in range(Q):
        query = input().strip().split()
        if query[0] == '1':
            pos = int(query[1])-1
            sg.update(pos, query[2])
        else:
            left = int(query[1])-1
            right = int(query[2])-1
            bits = sg.query(left, right)
            count = 0
            for j in range(26):
                count += (bits>>j) & 1
            print(count)

resolve()

Submission status: Accepted

Solution code:
#!python3

import sys

input = sys.stdin.readline

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    smap = [1<<(i-c0) for i in range(c0, ord('z')+1)]

    T = [0]*N + [smap[ord(S[i])-c0] for i in range(N)]

    for i in range(N-1, 0, -1):
        i2 = i << 1
        T[i] = T[i2] | T[i2|1]

    ans = []
    #print(T)
    for cmd, i, j in zip(*[iter(sys.stdin.read().split())]*3):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            S[i] = j
            i0 = N + i
            T[i0] = smap[ord(j)-c0]
            while i0 > 1:
                i0 = i0 >> 1
                T[i0] = T[i0+i0] | T[i0-~i0]
        elif cmd == "2":
            i += N
            j = int(j) + N

            d1 = 0
            while i < j:
                if i & 1:
                    d1 |= T[i]
                    i += 1
                if j & 1:
                    j -= 1
                    d1 |= T[j]

                i >>= 1; j >>=1

            ans.append(bin(d1).count('1'))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys

iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    smap = [1<<(i-c0) for i in range(c0, ord('z')+1)]

    T = [0]*N + [smap[ord(S[i])-c0] for i in range(N)]

    for i in range(N-1, 0, -1):
        i2 = i << 1
        T[i] = T[i2] | T[i2|1]

    ans = []
    #print(T)
    for cmd, i, j in zip(*[iter(sys.stdin.read().split())]*3):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            S[i] = j
            i0 = N + i
            T[i0] = smap[ord(j)-c0]
            while i0 > 1:
                i0 = i0 >> 1
                T[i0] = T[i0+i0] | T[i0-~i0]
        elif cmd == "2":
            i += N
            j = int(j) + N

            d1 = 0
            while i < j:
                if i & 1:
                    d1 |= T[i]
                    i += 1
                if j & 1:
                    j -= 1
                    d1 |= T[j]

                i >>= 1; j >>=1

            ans.append(bin(d1).count('1'))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    smap = [1<<(i-c0) for i in range(c0, ord('z')+1)]

    T = [0]*N + [smap[ord(S[i])-c0] for i in range(N)]

    for i in range(N-1, 0, -1):
        i2 = i << 1
        T[i] = T[i2] | T[i2|1]

    ans = []
    #print(T)
    for cmd, i, j in zip(*[iter(sys.stdin.read().split())]*3):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            S[i] = j
            i0 = N + i
            T[i0] = smap[ord(j)-c0]
            while i0 > 1:
                i0 = i0 >> 1
                T[i0] = T[i0+i0] | T[i0-~i0]
        elif cmd == "2":
            i += N
            j = int(j) + N

            d1 = 0
            while i < j:
                if i & 1:
                    d1 |= T[i]
                    i += 1
                if j & 1:
                    j -= 1
                    d1 |= T[j]

                i >>= 1; j >>=1

            ans.append(bin(d1).count('1'))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys

iim = lambda: map(int, input().rstrip().split())

def popcnt2(n):
    a = (
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    )
    ans = 0
    while n:
        ans += a[n&0xff]
        n >>= 8
    return ans

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    smap = [1<<(i-c0) for i in range(c0, ord('z')+1)]

    T = [0]*N + [smap[ord(S[i])-c0] for i in range(N)]

    for i in range(N-1, 0, -1):
        i2 = i << 1
        T[i] = T[i2] | T[i2|1]

    ans = []
    #print(T)
    for cmd, i, j in zip(*[iter(sys.stdin.read().split())]*3):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            S[i] = j
            i0 = N + i
            T[i0] = smap[ord(j)-c0]
            while i0 > 1:
                i0 = i0 >> 1
                T[i0] = T[i0+i0] | T[i0-~i0]
        elif cmd == "2":
            i += N
            j = int(j) + N

            d1 = 0
            while i < j:
                if i & 1:
                    d1 |= T[i]
                    i += 1
                if j & 1:
                    j -= 1
                    d1 |= T[j]

                i >>= 1; j >>=1

            ans.append(popcnt2(d1))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!python3

import sys

iim = lambda: map(int, input().rstrip().split())

def popcnt2(n):
    a = (
        0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
        4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
    )
    ans = 0
    while n:
        ans += a[n&0xff]
        n >>= 8
    return ans

def resolve():
    N = int(input())
    S = list(input())
    Q = int(input())

    c0 = ord('a')
    smap = [1<<(i-c0) for i in range(c0, ord('z')+1)]

    T = [0]*N + [smap[ord(S[i])-c0] for i in range(N)]

    for i in range(N-1, 0, -1):
        i2 = i << 1
        T[i] = T[i2] | T[i2|1]

    ans = []
    #print(T)
    for cmd, i, j in (line.split() for line in sys.stdin.readlines()):
        i = int(i) - 1
        if cmd == "1":
            if S[i] == j:
                continue

            S[i] = j
            i0 = N + i
            T[i0] = smap[ord(j)-c0]
            while i0 > 1:
                i0 = i0 >> 1
                T[i0] = T[i0+i0] | T[i0-~i0]
        elif cmd == "2":
            i += N
            j = int(j) + N

            d1 = 0
            while i < j:
                if i & 1:
                    d1 |= T[i]
                    i += 1
                if j & 1:
                    j -= 1
                    d1 |= T[j]

                i >>= 1; j >>=1

            ans.append(popcnt2(d1))

    print(*ans, sep="\n")

if __name__ == "__main__":
    resolve()