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: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
#segtree
#https://juppy.hatenablog.com/entry/2019/05/02/%E8%9F%BB%E6%9C%AC_python_%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder
#####segfunc######
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 = set()
#num:n以上の最小の2のべき乗
n=int(input())
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
s=str(input())[2:n+2]
init([{ord(s[i])-97}for i in range(n)])
q=int(input())
for _ in range(q):
  quer=str(input())
  x,a,b=quer[2:7:2]
  if x=="1":
    i,c=a,b
    update(int(i)-1,{ord(c)-97})
  else:
    l,r=a,b
    print(len(query(int(l)-1,int(r))))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
#segtree
#https://juppy.hatenablog.com/entry/2019/05/02/%E8%9F%BB%E6%9C%AC_python_%E3%82%BB%E3%82%B0%E3%83%A1%E3%83%B3%E3%83%88%E6%9C%A8_%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0_Atcoder
#####segfunc######
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 = set()
#num:n以上の最小の2のべき乗
n=int(input())
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
s=str(input())[2:n+2]
print(s)
init([{ord(s[i])-97}for i in range(n)])
q=int(input())
for _ in range(q):
  quer=str(input())
  x,a,b=quer[2:7:2]
  if x=="1":
    i,c=a,b
    update(int(i)-1,{ord(c)-97})
  else:
    l,r=a,b
    print(len(query(int(l)-1,int(r))))

Submission status: Runtime Error

Solution code:
def main():
  import sys
  b=sys.stdin.buffer
  n=int(b.readline())
  d=[0]*n+[1<<c-97for c in b.readline()[:n]]
  for i in range(n-1,0,-1):d[i]=d[i+i]|d[i-~i]
  r=[]
  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: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
#####segfunc######
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 = set()

#num:n以上の最小の2のべき乗
n=int(input())
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
s=input()
init([{s[i]-97}for i in range(n)])
q=int(input())
for _ in range(q):
  quer=str(input())
  x,a,b=quer[2:7:2]
  if x=="1":
    i,c=a,b
    update(int(i)-1,{ord(c)-97})
  else:
    l,r=a,b
    print(len(query(int(l)-1,int(r))))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
#####segfunc######
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 = set()

#num:n以上の最小の2のべき乗
n=int(input())
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
s=input()
init([{s[i]}for i in range(n)])
q=int(input())
for _ in range(q):
  quer=input().split()
  if quer[0]=="1":
    i,c=quer[1],quer[2]
    update(int(i)-1,{c})
  else:
    l,r=quer[1],quer[2]
    print(len(query(int(l)-1,int(r))))

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
#####segfunc######
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 = set()

#num:n以上の最小の2のべき乗
n=int(input())
num =2**(n-1).bit_length()
seg=[ide_ele]*2*num
s=input()
init([{i}for i in s])
q=int(input())
for _ in range(q):
  quer=input().split()
  if quer[0]=="1":
    _,i,c=quer
    update(int(i)-1,{c})
  else:
    _,l,r=quer
    print(len(query(int(l)-1,int(r))))

Submission status: Runtime Error

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.read().split("\n")):
        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: Runtime Error

Solution code:
#!python3

import sys

from bisect import bisect, insort_left

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

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

    c0 = ord('a')
    S1 = [[] for i in range(26)]
    for i, c1 in enumerate(S):
        ci = ord(c1) - c0
        S1[ci].append(i)

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

            c1 = ord(S[i]) - c0
            s1 = S1[c1]
            s1.pop(bisect(s1, i))
            S[i] = j
            c1 = ord(j) - c0
            insort_left(S1[c1], i)
        elif cmd == "2":
            j = int(j) - 1
            num = 0

            for s1 in S1:
                ls = len(s1)
                k = bisect(s1, i-1, 0, ls)

                if k == ls:
                    continue
                if i <= s1[k] <= j:
                    num += 1

            ans.append(num)

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

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#####segfunc######
def segfunc(x,y):
    return x + y

def init(init_val,j):
    #set_val
    for i in range(n):
        seg[j][i+num-1]=init_val[i]    
    #built
    for i in range(num-2,-1,-1) :
        seg[j][i]=segfunc(seg[j][2*i+1],seg[j][2*i+2]) 
    
def update(k,x,j):
    k += num-1
    seg[j][k] = x
    while k:
        k = (k-1)//2
        seg[j][k] = segfunc(seg[j][k*2+1],seg[j][k*2+2])
    
def query(p,q,j):
    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[j][p])
        if q&1 == 1:
            res = segfunc(res,seg[j][q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = segfunc(res,seg[j][p])
    else:
        res = segfunc(segfunc(res,seg[j][p]),seg[j][q])
    return res


n = int(input())
s = list(input())
q = int(input())
al = []
l = [[0 for i in range(n)] for i in range(26)]
for i in range(n):
    l[ord(s[i])-97][i] = 1
seg = [[] for i in range(26)]
for i in range(26):
#####単位元######
    ide_ele = 0
#num:n以上の最小の2のべき乗
    num =2**(n-1).bit_length()
    seg[i]=[ide_ele]*2*num
    init(l[i],i)
for i in range(q):
    q1 = list(input())
    if q1[0] == "1":
        p = int(q1[2])
        r = ord(q1[4]) - 97
        for j in range(26):
            if l[j][p-1] == 1 and j != r:
                update(p-1,0,j)
            elif j == r:
                update(p-1,1,j)
    else:
        a = int(q1[2])
        b = int(q1[4])
        #print(a,b,seg)
        aa = 0
        for j in range(26):
            if query(a-1,b,j) > 0:
                aa += 1
        al.append(aa)
for i in al:
    print(i)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
from collections import *
from math import * 

def main():
    N = int(input())
    S = list(input())

    n = ceil(N**0.5)
    count = [Counter() for i in range(n)]

    for i in range(N): count[i//n][S[i]] += 1

    for i in range(int(input())):
        q = input().split()

        if q[0] == '1':
            x = int(q[1])-1
            count[x//n][S[x]] -= 1
            count[x//n][q[2]] += 1
            S[x] = q[2]

        else:
            ans = set()

            l = int(q[1])-1
            r = int(q[2])-1

            l_idx = l // n 
            r_idx = r // n 

            if l_idx == r_idx: ans = set(S[l:r+1])
            else:
                l_idx += 1
                r_idx -= 1
                while l_idx <= r_idx:
                    ans |= set(k for k, v in count[l_idx].items() if v)
                    l_idx += 1

                ans.add(S[l])
                if not l % n: ans |= set(k for k, v in count[l//n].items() if v)
                else:
                    for j in range(l%n-1): ans.add(S[l+j])

                ans.add(S[r])
                for j in range(r%n, -1, -1): ans.add(S[r-j])

            print(len(ans))

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
 
 def main():
    N = int(input())
    S = input().rstrip()
    tree = SegmentTree(initial_values=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().rstrip().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, n=None, f=max, zero_factory=int, converter=lambda x:x, initial_values=None):
        assert(n or initial_values)
        self.__f, self.__z, self.__c = f, zero_factory, converter
        size = n if n else len(initial_values)
        self.__n = 1 << ((size - 1).bit_length())
        d = [zero_factory() for _ in range(2 * self.__n + 1)]
        self.__dat = d
        if initial_values:
            for i, v in enumerate(initial_values): d[self.__n + i] = converter(v)
            for i in range(self.__n - 1, 0, -1): d[i] = f(d[i<<1], d[i<<1|1])

    def update(self, index, value):
        i, v, d = index + self.__n, self.__c(value), self.__dat
        if d[i] == v: return
        d[i] = v
        while i:
            i = i >> 1
            d[i] = self.__f(d[i<<1], d[i<<1|1])

    def query(self, from_inclusive, to_exclusive):
        ans = self.__z()
        if to_exclusive <= from_inclusive: return ans
        l, r = from_inclusive + self.__n, to_exclusive + self.__n
        while l < r:
            if l & 1: ans, l = self.__f(ans, self.__dat[l]), l+1
            if r & 1: ans, r = self.__f(ans, self.__dat[r-1]), r-1
            l, r = l >> 1, r >> 1
        return ans

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
# 各文字についての出現位置を平行二分探索木など(順番を保持する配列)で持っておく
import bisect

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

S_list=[c for c in S]

indexes=[[] for _ in range(26)]
for i in range(N):
    indexes[ord(S_list[i])-ord("a")].append(i)
for q in query:
    t=q[0]
    if t=="1":
        i, c = int(q[1])-1, q[2]
        # 文字列情報を上書き
        indexes[ord(S_list[i])-ord("a")].remove(i)
        S_list=c
        bisect.insort(indexes[ord(S_list[i])-ord("a")], i)
    else:
        l, r = int(q[1])-1, int(q[2]) # l以上なのでlはデクリメント
        ans=0
        for i in range(26):
            it = bisect.bisect_left(indexes[i], l)
            if it < len(indexes[i]) and indexes[i][it] < r: 
                ans+=1
        print(ans)

Submission status: Runtime Error

Solution code:
import math as ma

def conq(s, l, r):
    mid = ma.floor((r-l+1)/2)
    if r-l < 10:
        return list(set(s[l-1:r]))
    else:
        s1 = list(set(conq(s, l, mid)))
        s2 = list(set(conq(s, mid+1, r)))
        return s1 + s2

n = int(input())
s = list(input())
q = int(input())
s1, s2 = [], []

for i in range(q):
    t, i, c = input().split()
    if t == '1':
        s[int(i)-1] = c
    elif t == '2':
        l, r = int(i), int(c)
#         mid = ma.floor((r-l+1)/2)
#         s1 = list(set(s[l-1:mid]))
#         s2 = list(set(s[mid:r]))
        print(len(set(conq(s,l,r))))

Submission status: Runtime Error

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

for i in range(q):
    t, il, cr = input().split()
    if t == '1':
        s[int(il)+1] = cr
    elif t == '2':
        print(len(set(list(s[int(il)+1:int(cr)+1]))))

Submission status: Runtime Error

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

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

bit = [BIT(n) for i in range(26)]
for i in range(n):
    bit[ord(s[i])-97].add(i+1, 1)
s = list(s)
for _ in range(q):
    query, i, c = input().split()
    if query == "1":
        i = int(i)
        c = ord(c)-97
        if bit[c].get(i) == 0:
            bit[c].add(i, 1)
            bit[ord(s[i])-97].add(i, -1)
            s[i] = chr(c+97)
            print(s)
    else:
        ans = 0
        for k in range(26):
            if bit[k].get(int(i)-1, int(c)) >= 1:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

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

bit = [BIT(n) for i in range(26)]
for i in range(n):
    bit[ord(s[i])-97].add(i+1, 1)
s = list(s)
for _ in range(q):
    query, i, c = input().split()
    if query == "1":
        i = int(i)
        c = ord(c)-97
        if bit[c].get(i) == 0:
            bit[c].add(i+1, 1)
            bit[ord(s[i])-97].add(i+1, -1)
            s[i] = chr(c+97)
    else:
        ans = 0
        for k in range(26):
            if bit[k].get(int(i)-1, int(c)) >= 1:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
import bisect

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

alpha_map = {i:[] for i in alpha}
for i,c in enumerate(s):
    bisect.insort(alpha_map[c],i+1)
    
for _ in range(q):
    x,y,z = map(str,input().split())
    if int(x) == 1:
        y = int(y)
        bef = s[y-1]
        if bef == z:
            continue
        alpha_map[bef].pop(bisect.bisect_left(alpha_map[bef],y))
        bisect.insort(alpha_map[z],y)
        s = s[:y-1]+z+s[y:]
    else:
        count = 0
        for i,j in alpha_map.items():
            idx = bisect.bisect_left(j,int(y))
            if idx < len(j) and j[idx] <= int(z):
                    count += 1
        print(count)

Submission status: Runtime Error

Solution code:
#include<cstdio>
#include<math.h>
#include<algorithm>
#include<vector>
#include<queue>
#include<string>
#include<set>
#include<cstring>
#include<map>
 
 
using namespace std;
#define int long long int
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1001001001
#define LLINF 1001001001001001001
#define mp make_pair
#define pb push_back
#define mod 1000000007


int N,Q;
char S[500005];
set<int> alphabets_appear[30];


signed main(){
    scanf("%lld %s %lld",&N,S,&Q);
    rep(i,N){
        alphabets_appear[S[i]-'a'].insert(i);
    }
    rep(i,Q){
        int type;
        scanf("%lld",&type);
        if(type==1){
            int t1;char t2;
            scanf("%lld %c\n",&t1,&t2);
            alphabets_appear[S[t1]-'a'].erase(t1);
            alphabets_appear[t2-'a'].insert(t1);
        }else{
            int ans=0;
            int t1;int t2;
            scanf("%lld %lld\n",&t1,&t2);t1--;t2--;
            for(char i='a';i<='z';i++){
                auto itr=alphabets_appear[i-'a'].lower_bound(t1);
                if(itr==alphabets_appear[i-'a'].end())continue;
                if(*itr<=t2)ans++;
                
            }
            printf("%lld\n",ans);
        }
    }
    return 0;
}

Submission status: Runtime Error

Solution code:
import collections

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

Query = []
for i in range(Q):
    Query.append(input().split())

for Q_temp in Query:
    if int(Q_temp[0]) is 1:
        S[int(Q_temp[1]) - 1] = Q_temp[2]
    else:
        output = collections.Counter(S[int(Q_temp[1] - 1): int(Q_temp[2])])
        print(len(output))

Submission status: Runtime Error

Solution code:
import collections

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

Query = []
for i in range(Q):
    Query.append(input().split())

for Q_temp in Query:
    if int(Q_temp[0]) is 1:
        S[int(Q_temp[1])] = Q_temp[2]
    else:
        output = collections.Counter(S[int(Q_temp[1]): int(Q_temp[2])])
        print(len(output))

Submission status: Runtime Error

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: Runtime Error

Solution code:
#!python3

import sys
from functools import reduce
from operator import or_
from collections import defaultdict

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

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

    N=len(S)
    lo, hi = 100, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = lo
    S1 = [None] * nn

    for i in range(nn):
        sd = S1[i] = defaultdict(int)
        i1 = i * nn
        for j in range(i1, min(N, i1+nn)):
            sd[S[j]] += 1

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            c1 = S[i]
            i1 = i // nn
            S1[i1][c1] -= 1
            S[i] = j
            S1[i1][j] += 1
        elif cmd == "2":
            j = int(j)

            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            if ia < ja:
                ss = set()
                ss = reduce(or_, (k for i1 in range(ia, ja) for k, v in S1[i1].items() if v > 0), ss)

                if ib > 0:
                    for i1 in range(i, i-ib+nn):
                        ss.add(S[i1])
                if jb > 0:
                    for i1 in range(ja*nn, j):
                        ss.add(S[i1])
            else:
                ss = set(S[k] for k in range(i, j))

            ans.append(len(ss))

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

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
from functools import reduce
from operator import or_

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

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

    N=len(S)
    lo, hi = 0, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = md+1
    S1 = [None] * nn

    for i in range(nn):
        ii = i * nn
        S1[i] = set(S[j] for j in range(ii, min(N, ii+nn)))

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            ii = i // nn
            S[i] = j
            i2 = ii * nn
            S1[ii] = set(S[k] for k in range(i2, min(N, i2+nn)))
        elif cmd == "2":
            j = int(j)
            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            ss = set()
            ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

            if ib > 0:
                for i1 in range(i, i-ib+nn):
                    ss.add(S[i1])
            if jb > 0:
                for i1 in range(ja*nn, j):
                    ss.add(S[i1])

            ans.append(len(ss))

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

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
from functools import reduce
from operator import or_

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

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

    lo, hi = 0, N//2
    md = 1
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = md+1
    S1 = [None] * (nn+1)

    for i in range(N//nn):
        ii = i * nn
        S1[i] = set(S[j] for j in range(ii, min(N, ii+nn)))

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            ii = i // nn
            S[i] = j
            i2 = ii * nn
            S1[ii] = set(S[k] for k in range(i2, min(N, i2+nn)))
        elif cmd == "2":
            j = int(j)
            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            ss = set()
            ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

            if ib > 0:
                for i1 in range(i, i-ib+nn):
                    ss.add(S[i1])
            if jb > 0:
                for i1 in range(ja*nn, j):
                    ss.add(S[i1])

            ans.append(len(ss))

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

if __name__ == "__main__":
    resolve()

Submission status: Runtime Error

Solution code:
#!python3

import sys
from functools import reduce
from operator import or_

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

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

    lo, hi = 0, N//2
    while lo < hi:
        md = (lo+hi) // 2
        if md**2 < N:
            lo = md + 1
        else:
            hi = md
    nn = md+1
    S1 = [None] * (nn+1)

    for i in range(N//nn+1):
        ii = i * nn
        S1[i] = set(S[j] for j in range(ii, min(N, ii+nn)))

    ans = []
    for cmd, i, j in (line.split() for line in sys.stdin):
        i = int(i) - 1
        if cmd == "1":
            ii = i // nn
            S[i] = j
            i2 = ii * nn
            S1[ii] = set(S[k] for k in range(i2, min(N, i2+nn)))
        elif cmd == "2":
            j = int(j)
            ia, ib = divmod(i, nn)
            ja, jb = divmod(j, nn)

            if ib > 0:
                ia += 1
            ss = set()
            ss = reduce(or_, (S1[i1] for i1 in range(ia, ja)), ss)

            if ib > 0:
                for i1 in range(i, i-ib+nn):
                    ss.add(S[i1])
            if jb > 0:
                for i1 in range(ja*nn, j):
                    ss.add(S[i1])

            ans.append(len(ss))

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

if __name__ == "__main__":
    resolve()