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()[:-1]
n = int(input())
ss = list(input())
q = int(input())
s = []
for i in range(len(ss)):
    a = ord(ss[i])-97
    s.append(a)
#print(s) #test
h = 0
nn = n
while nn:
    nn //= 2
    h += 1

seg = [[0 for _ in range(26)] for _ in range((2**(h+1))-1)]
for i in range(2**h-1, n-1+2**h):
    nl = [i] #所属するsegの番号リスト
    y = i
    for j in range(h):
        y = (y-1)//2
        nl.append(y) #nl完成
    for k in nl:
        seg[k][s[i-2**h+1]] += 1

for _ in range(q):
    bs, cs, ds = input().split()
    b = int(bs)
    c = int(cs)
    if b == 1:
        #print("クエリ1処理開始") #test
        f = ord(ds)-97
        x = c + 2**h - 2
        cl = [x]
        for j in range(h):
            x = (x-1)//2
            cl.append(x)
        #print(cl) #test
        #print(c) #test
        #print(s[c-1]) #test
        for k in cl:
            seg[k][s[c-1]] -= 1
            seg[k][f] += 1
        #print(seg) #test
    else:
        #print("クエリ2処理開始") #test
        d = int(ds)
        C = 2**h + c - 1
        D = 2**h + d
        LI = [] #敷居リスト
        t = C
        u = 1
        jud = False
        while True:
            if t * u == D:
                break
            elif t%2 != 0:
                if (t+1) * u <= D:
                    LI.append(t)
                    t += 1
                else:
                    t *= 2
                    u //= 2
            else:
                if (t+2) * u <= D:
                    t //= 2
                    u *= 2
                elif (t+1) * u <= D:
                    LI.append(t)
                    t += 1
                else:
                    t *= 2
                    u //= 2
        #print(LI)
        sumlist = [0 for _ in range(26)] #範囲内の個数
        for sh in LI:
            sh -= 1
            for j in range(26):
                sumlist[j] += seg[sh][j]
        #print(sumlist)
        ans = 0
        for numbers in sumlist:
            if numbers != 0:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
al = 'abcdefghijklmnopqrstuvwxyz'
N=int(input())
S=input()
Q=int(input())
from bisect import bisect_left, bisect_right
dic = {}
for i in range(N):
  if not S[i] in dic:
    dic[S[i]]=[i+1]
  else:
    dic[S[i]].append(i+1)
def fg1(l, r):
  l = int(l)
  dic[S[l-1]].remove(l)
  if not r in dic:
    dic[r]=[l]
  else:
    ins = bisect_left(dic[r], l)
    dicr = dic[r][:ins]
    dicr.append(l)
    dicr += dic[r][ins:]
    dic[r]=dicr
def fg2(l, r):
  l, r = int(l), int(r)
  ret = 0
  for d in list(dic.keys()):
    li = bisect_left(dic[d], l)
    if li<=len(dic[d])-1:
      ret += (dic[d][li]<=r)
  print(ret)
  
for i in range(Q):
  fg, l, r = input().split()
  if fg=='1':
    fg1(l, r)
  else:
    fg2(l, r)

Submission status: Runtime Error

Solution code:
al = 'abcdefghijklmnopqrstuvwxyz'
N=int(input())
S=input()
Q=int(input())
from bisect import bisect_left, bisect_right
dic = {}
for i in range(N):
  if not S[i] in dic:
    dic[S[i]]=[i+1]
  else:
    dic[S[i]].append(i+1)
def fg1(l, r):
  l = int(l)
  dic[S[l-1]].remove(l)
  if not r in dic:
    dic[r]=[l]
  else:
    ins = bisect_left(dic[r], l)
    dicr = dic[r][:ins]
    dicr.append(l)
    dicr += dic[r][ins:]
    dic[r]=dicr
def fg2(l, r):
  l, r = int(l), int(r)
  ret = 0
  for d in list(dic.keys()):
    ll = bisect_left(dic[d], l)
    rr = bisect_right(dic[d], r)
    ret += ll<rr
  print(ret)
  
for i in range(Q):
  fg, l, r = input().split()
  if fg=='1':
    fg1(l, r)
  else:
    fg2(l, r)

Submission status: Runtime Error

Solution code:
import collections

N = int(input())
S = list(input())
Q = int(input())
for _ in range(Q):
    Q1, Q2, Q3 = map(int, input().split())
    if Q1 == '1':
        S[int(Q2)-1] = ord(Q3)
    else:
        print(len(collections.Counter(S[int(Q2)-1: int(Q3)])))

Submission status: Runtime Error

Solution code:
N=int(input())
S=[*str(input())]

n=1
while N>n:
	n*=2

d=[[0]*(2*n) for _ in range(26)]

def ci(c):
	return "abcdefghijklmnopqrstuvwxyz".find(c)

def update(d,k,a):
	k+=n-1
	d[k]=a
	while k>0:
		k=~-k//2
		d[k]=d[k*2+1]+d[k*2+2]

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

for i,c in enumerate(S):
	update(d[ci(c)],i,1)

for i in range(int(input())):
	t,x,y=input().split()
	if t=='1':
		update(d[ci(S[int(x)-1])],int(x)-1,0)
		update(d[ci(y)],int(x)-1,1)
	else:
		a=0
		for j in range(26):
			if query(d[j],int(x)-1,int(y),0,0,n)>0:
				a+=1
		print(a)

Submission status: Runtime Error

Solution code:
from bisect import insort_left
n = int(input())
s = input()
q = int(input())
dic = {}
for ind, c in enumerate(s):
    if c in dic:
        dic[c].append(ind)
    else:
        dic[c] = [ind]

for _ in range(q):
    t, a, b = input().split()
    a = int(a)-1
    if t=='1':
        find_c = False
        for c, li in dic.items():
            if a in li:
                li.remove(a)
            if c==b:
                insort_left(li, a)
                find_c = True
        if not find_c:
            dic[b] = [a]
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if li[0]<=b and li[-1]>=a:
                tmp += 1
        print(tmp)

Submission status: Runtime Error

Solution code:
import bisect
from collections import defaultdict

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


alpha_dic = defaultdict(list)

for i, s in enumerate(S):
    alpha_dic[s].append(i)

for _ in range(Q):
    l, m, n = input().split()

    if l == '1':
        m = int(m) - 1
        c = S[m]

        if c == n:
            continue
        else:
            i = bisect.bisect_left(alpha_dic[c], m)
            del alpha_dic[c][i]

            bisect.insort_left(alpha_dic[n], m)
    else:
        m, n = int(m) - 1, int(n) - 1

        cnt = 0
        for _, val in alpha_dic.items():
            left_idx = bisect.bisect_left(val, m)
            right_idx = bisect.bisect_left(val, n)
            x = len(val)

            if left_idx > right_idx or left_idx == x or (left_idx == 0 and right_idx == 0 and val[0] != m and val[0] != n):
                continue
            else:
                cnt += 1

        print(cnt)

Submission status: Runtime Error

Solution code:
i don't understand

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys

DEBUG = False

class SegmentTree:

    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.nodes = [0 for _ in range(self.n * 2)]
    
    def update(self, idx, val):
        nodes = self.nodes

        idx += self.n - 1
        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = nodes[idx * 2 + 1] | nodes[idx * 2 + 2]
    
    def _query(self, l, r, scope_idx, scope_l, scope_r):
        if r <= scope_l or l >= scope_r:
            return 0
        if l <= scope_l and r >= scope_r:
            return self.nodes[scope_idx]
        vl = self._query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
        vr = self._query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
        return vl | vr
    
    def query(self, l, r):
        return self._query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    read()
    s = read()

    a_ord = ord("a")
    bit_offsets = {chr(c_ord): c_ord - a_ord for c_ord in range(ord("a"), ord("z"))}

    apps = SegmentTree(len(s))
    i = 0
    for c in s:
        apps.update(i, 1 << bit_offsets[c])
        i += 1

    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.update(int(i) - 1, 1 << bit_offsets[c])
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(bin(apps.query(int(l) - 1, int(r) - 1 + 1)).count("1"))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys

DEBUG = False

class SegmentTree:

    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.nodes = [0 for _ in range(self.n * 2)]
    
    def update(self, idx, val):
        nodes = self.nodes

        idx += self.n - 1
        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = nodes[idx * 2 + 1] | nodes[idx * 2 + 2]
    
    def _query(self, l, r, scope_idx, scope_l, scope_r):
        if r <= scope_l or l >= scope_r:
            return 0
        if l <= scope_l and r >= scope_r:
            return self.nodes[scope_idx]
        vl = self._query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
        vr = self._query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
        return vl | vr
    
    def query(self, l, r):
        return self._query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return


def main():
    read()
    s = read()

    bit_offsets = {chr(c_ord): ord(c_ord) - ord("a") for c_ord in range(ord("a"), ord("z"))}

    apps = SegmentTree(len(s))
    i = 0
    for c in s:
        apps.update(i, 1 << bit_offsets[c])
        i += 1

    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.update(int(i) - 1, 1 << bit_offsets[c])
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(bin(apps.query(int(l) - 1, int(r) - 1 + 1)).count("1"))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys

DEBUG = False

class SegmentTree:

    def __init__(self, n):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.fillval = 0
        self.nodes = [0 for _ in range(self.n)]
    
    def update(self, idx, val):
        nodes = self.nodes

        idx += self.n - 1
        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = nodes[idx * 2 + 1] | nodes[idx * 2 + 2]
    
    
    def query(self, l, r):
        fillval = self.fillval
        nodes = self.nodes
        
        def _query(l, r, scope_idx, scope_l, scope_r):
            if r <= scope_l or l >= scope_r:
                return fillval
            if l <= scope_l and r >= scope_r:
                return nodes[scope_idx]
            vl = _query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
            vr = _query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
            return vl | vr

        return _query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

class LetterAppearance:
    def __init__(self, chars):
        self.chars_app = SegmentTree(len(chars))
        for i in range(0, len(chars)):
            bit = ord(chars[i]) - ord("a")
            self.chars_app.update(i, 1 << bit)
    
    def replace(self, pos, char):
        bit = ord(char) - ord("a")
        self.chars_app.update(pos, 1 << bit)

    def query(self, l, r):
        return bin(self.chars_app.query(l, r)).count("1")


def main():
    read()
    s = read()
    apps = LetterAppearance(s)
    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.replace(int(i) - 1, c)
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(apps.query(int(l) - 1, int(r) - 1 + 1))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys

DEBUG = False

class SegmentTree:
    def __init__(self, n, merge_func, fillval=sys.maxsize):
        self.n = 1
        while self.n < n:
            self.n *= 2
        self.nodes = [fillval] * (self.n * 2 - 1)
        self.merge_func = merge_func
        self.fillval = fillval
    
    def update(self, idx, val):
        nodes = self.nodes
        mergef = self.merge_func

        idx += self.n - 1
        nodes[idx] = val
        while idx > 0:
            idx = (idx - 1) // 2
            nodes[idx] = mergef(nodes[idx * 2 + 1], nodes[idx * 2 + 2])
    
    
    def query(self, l, r):
        fillval = self.fillval
        nodes = self.nodes
        mergef = self.merge_func
        
        def _query(l, r, scope_idx, scope_l, scope_r):
            if r <= scope_l or l >= scope_r:
                return fillval
            if l <= scope_l and r >= scope_r:
                return nodes[scope_idx]
            vl = _query(l, r, scope_idx * 2 + 1, scope_l, (scope_l + scope_r) // 2)
            vr = _query(l, r, scope_idx * 2 + 2, (scope_l + scope_r) // 2, scope_r)
            return mergef(vl, vr)

        return _query(l, r, 0, 0, self.n)


def read(t = str):
    return t(sys.stdin.readline().rstrip())

def read_list(t = str, sep = " "):
    return [t(s) for s in sys.stdin.readline().rstrip().split(sep)]

def dprint(*args, **kwargs):
    if DEBUG:
        print(*args, **kwargs)
    return

class LetterAppearance:
    def __init__(self, chars):
        self.chars = chars
        self.chars_app = SegmentTree(len(chars), lambda x, y: x.union(y), set())
        for i in range(0, len(chars)):
            self.chars_app.update(i, set([chars[i]]))
    
    def replace(self, pos, char):
        if self.chars[pos] == char:
            return
        self.chars_app.update(pos, set([char]))
        self.chars[pos] = char

    def query(self, l, r):
        return len(self.chars_app.query(l, r))


def main():
    read()
    s = read()
    apps = LetterAppearance(s)
    nr_q = read(int)
    for i in range(0, nr_q):
        q = read_list()
        if q[0] == "1":
            _, i, c = q  # i_q in the question starts from 1, not 0
            apps.replace(int(i) - 1, c)
        else:
            _, l, r = q  # l_q and r_q in the question start from 1, not 0
            print(apps.query(int(l) - 1, int(r) - 1 + 1))  # query in the question includes both edges


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import collections

alphabets = list("abcdefghijklmnopqrstuvwxyz")

def do1(s_dic, i, c, index):
    for t in alphabets:
        if(i in dic[t]):
            s_dic[t].remove(i)
            break
    s_dic[c].add(i)
    
def do2(s_dic, l, r):
    for t in alphabets:
        for p in dic[t]:
            if(l-1 <= p and p < r):
                ans += 1
                break
    print(ans)
    
def make_dic(S):
    hist = collections.Counter()
    for i, s in enumerate(S):
        if(hist[s] == 0):
            hist[s] = set()
        hist[s].add(i)
    return hist

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

s_dic = make_dic(S)

for q in range(Q):
    query = input().split()
    if(query[0] == "1"):
        do1(s_dic, int(query[1]) - 1, query[2])
    else:
        do2(s_dic, int(query[1]), int(query[2]))

Submission status: Runtime Error

Solution code:
def do1(current_s, i, c, index):
    current_s[i] = c
    
def do2(current_s, l, r):
    ans = set()
    for i in range(l-1, r):
        ans.add(current_s[i])
    print(len(ans))
    

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

index = 0
for q in range(Q):
    query = input().split()
    if(query[0] == "1"):
        do1(S, int(query[1]) - 1, query[2])
    else:
        do2(S, int(query[1]), int(query[2]))

Submission status: Runtime Error

Solution code:
# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math

n, k = map(int, input().split())
a = list(map(int, input().split()))
# n = int(input())
mod = 10 ** 9 + 7
a.sort(reverse = True)
# print(a)
ans = 0


def C(n, k, mod):
    if k == 0:
        return 1
    elif n < k or k < 0:
        return 0
    else:
        x,y = 1,1
        while k > 0:
            x *= n
            y *= k
            n, k = n-1, k-1

        return x * pow(y, mod-2, mod) % mod


for i in range(0,n-k+1):
    ans += a[i] * C(n-i-1, k-1, mod)
    ans %= mod

a.reverse()
for i in range(0,n-k+1):
    ans -= a[i] * C(n-i-1, k-1, mod)
    ans %= mod



print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left,insort_left
n=int(input())
s=input()
lindex=[[] for _ in range(26)]
for i in range(n):
  lindex[ord(s[i])-97].append(i)
q=int(input())
for i in range(q):
  q1,q2,q3=input().split()
  if q1=='1':
    q2=int(q2)-1
    idx=bisect_left(lindex[ord(s[q2])-97],q2)
    if s[q2]!=q3:
      del lindex[ord(s[q2])-97][idx]
      insort_left(lindex[ord(q3)-97],q2)
  else:
    l=int(q2)-1
    r=int(q3)-1
    cnt=0
    for j in range(26):
      if len(lindex[j])==0:
        continue
      idx=bisect_left(lindex[j],l)
      if len(lindex[j])>idx and lindex[j][idx]<=r:
        cnt+=1
    print(cnt)

Submission status: Runtime Error

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

N = int(input())
S = list(input().rstrip())
ord_a = ord("a")

# N: 処理する区間の長さ
INF = 2**31-1

LV = (N-1).bit_length()
N0 = 2**LV
data = [[0]*(2*N0) for _ in range(26)]
lazy = [[0]*(2*N0) for _ in range(26)]

def gindex(l, r):
    L = (l + N0) >> 1; R = (r + N0) >> 1
    lc = 0 if l & 1 else (L & -L).bit_length()
    rc = 0 if r & 1 else (R & -R).bit_length()
    for i in range(LV):
        if rc <= i:
            yield R
        if L < R and lc <= i:
            yield L
        L >>= 1; R >>= 1

# 遅延伝搬処理
def propagates(k, *ids):
    for i in reversed(ids):
        v = lazy[k][i-1]
        if not v:
            continue
        lazy[k][2*i-1] += v; lazy[k][2*i] += v
        data[k][2*i-1] += v; data[k][2*i] += v
        lazy[k][i-1] = 0

# 区間[l, r)にxを加算
def update(l, r, x, k):
    *ids, = gindex(l, r)
    propagates(k, *ids)

    L = N0 + l; R = N0 + r
    while L < R:
        if R & 1:
            R -= 1
            lazy[k][R-1] += x; data[k][R-1] += x
        if L & 1:
            lazy[k][L-1] += x; data[k][L-1] += x
            L += 1
        L >>= 1; R >>= 1
    for i in ids:
        data[k][i-1] = max(data[k][2*i-1], data[k][2*i])

# 区間[l, r)内の最大値を求める
def query(l, r, k):
    propagates(k, *gindex(l, r))
    L = N0 + l; R = N0 + r

    s = -INF
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[k][R-1])
        if L & 1:
            s = max(s, data[k][L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

for j in range(N):
    u = S[j]
    update(j, N, 1, ord(u) - ord_a)

Q = int(input())

for _ in range(Q):
    q = input().rstrip().split()
    if q[0] == "2":
        l, r = int(q[1]) - 1, int(q[2]) - 1
        cnt = 0
        for i in range(26):
            if l == 0:
                cnt += int(query(r, r + 1, i) > 0)
            else:
                cnt += int((query(r, r + 1, i) - query(l - 1, l, i) > 0))
        print(cnt)
    else:
        i, c = int(q[1]) - 1, q[2]
        update(l, N, -1, ord(S[i]) - ord_a)
        S[i] = c
        update(l, N, 1, ord(S[i]) - ord_a)

Submission status: Runtime Error

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

def func(l, r):
    res = [inf for _ in range(26)]
    aa = ord('a')
    for i in range(l, r + 1):
        for j in range(26):
            if chr(j + aa) == s[i]:
                res[j] = min(res[j], j)
    return res

n = INT()
s = list(STR())
ss = [[] for _ in range(26)]
for i in range(n):
    ss[ord(s[i]) - ord('a')].append(i)
q = INT()
for _ in range(q):
    que = S_LIST()
    if que[0] == '1':
        i = int(que[1])
        c = que[2]
        idx = bisect.bisect_left(ss[ord(s[i - 1]) - ord('a')], i - 1)
        del ss[ord(s[i - 1]) - ord('a')][idx]
        bisect.insort_left(ss[ord(c) - ord('a')], i - 1)
    else:
        l = int(que[1])
        r = int(que[2])
        ans = 0
        for i in range(26):
            if len(ss[i]) != 0:
                a = bisect.bisect_left(ss[i], l - 1)
                if a < len(ss[i]) and ss[i][a] <= r - 1:
                    ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
import bisect
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7

def func(l, r):
    res = [inf for _ in range(26)]
    aa = ord('a')
    for i in range(l, r + 1):
        for j in range(26):
            if chr(j + aa) == s[i]:
                res[j] = min(res[j], j)
    return res

n = INT()
s = list(STR())
ss = [[] for _ in range(26)]
for i in range(n):
    ss[ord(s[i]) - ord('a')].append(i)
q = INT()
for _ in range(q):
    que = S_LIST()
    if que[0] == '1':
        i = int(que[1])
        c = que[2]
        idx = bisect.bisect_left(ss[ord(s[i - 1]) - ord('a')], i - 1)
        del ss[ord(s[i - 1]) - ord('a')][idx]
        ss[ord(c) - ord('a')].append(i - 1)
        ss[ord(c) - ord('a')].sort()
    else:
        l = int(que[1])
        r = int(que[2])
        ans = 0
        for i in range(26):
            if len(ss[i]) != 0:
                a = bisect.bisect_left(ss[i], l - 1)
                if a < len(ss[i]) and ss[i][a] <= r - 1:
                    ans += 1
        print(ans)

Submission status: Runtime Error

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
        S[int(i) - 1] = ch
        remove = bisect.bisect_left(cnt_ch[S[int(i) - 1]], int(i) - 1)
        del cnt_ch[S[int(i) - 1]][remove]
        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: Runtime Error

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]
        if not cnt_ch[ch]:
            cnt_ch[ch].append(int(i) - 1)
            continue
        bisect.insort(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: Runtime Error

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]
        bisect.insort(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)
            #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: Runtime Error

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]
        bisect.insort(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: Runtime Error

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
    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')