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:
N = int(input())
S = input()
Q = int(input())
set_dic = {}
for i,s in enumerate(S):
    if s not in set_dic.keys():
        set_dic[s] = {i+1}
    else:
        set_dic[s].add(i+1)

for _ in range(Q):
    query = input()
    if query[0] == "1":
        i = int(query[2])
        c = query[4]
        for l in set_dic.values():
            l.discard(i)
        if c not in set_dic.keys():
            set_dic[c] = {i}
        else:
            set_dic[c].add(i)
    else:
        l = int(query[2])
        r = int(query[4])
        ans = 0
        for eachset in set_dic.values():
            for i in range(l,r+1):
                if i in eachset:
                    ans += 1
                    break
        print(ans)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
Q = int(input())
ans = []
for _ in range(Q):
    query = input()
    if query[0] == "1":
        i = int(query[2])
        c = query[4]
        S = S[:i-1] + c + S[i:]
    else:
        l = int(query[2])
        r = int(query[4])
        ans.append(len(set(S[l-1:r])))
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
N = int(input())
S = input()
Q = int(input())
for _ in range(Q):
    query = input()
    if query[0] == "1":
        i = int(query[2])
        c = query[4]
        S = S[:i-1] + c + S[i:]
    else:
        l = int(query[2])
        r = int(query[4])
        print(len(set(S[l-1:r])))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10 ** 9)

def dfs(x, seen):
  seen.add(x)
  for i in G[x]:
    if i in seen:
      continue
    dfs(i, seen)

N, M, K = map(int, input().split())

S = set()
G = [[] for i in range(N)]
for _ in range(M):
  A, B = map(int, input().split())
  A -= 1
  B -= 1
  G[A].append(B)
  G[B].append(A)
  S.add(A)
  S.add(B)

R = []
while len(S) != 0:
    seen = set()
    dfs(S.pop(), seen)
    R.append(seen)
    S = S - seen

Block = [set() for i in range(N)]
for _ in range(K):
  C, D = map(int, input().split())
  Block[C-1].add(D-1)
  Block[D-1].add(C-1)

seq = [0]*N

for r in R:
    lr = len(r)
    for j in r:
        seq[j] =  lr - len(G[j]) - len(r&Block[j]) - 1

print(*seq)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import string 

dic={c:[] for c in string.ascii_lowercase}
N=int(input())
S=list(input())
Q=int(input())
for i in range(len(S)):
  dic[S[i]].append(i+1)
  
for i in range(Q):
  a,b,c=map(str,input().split())
  if a=='1':
    if S[int(b)-1]==c:
      continue
    b=int(b)
    f=S[b-1]
    d=bisect_left(dic[f],b)
    e=bisect_left(dic[c],b)
    dic[f].pop(d)
    dic[c].insert(e,b)
  else:
    ans=0
    b,c=int(b),int(c)
    for j in string.ascii_lowercase:
      d=bisect_left(dic[j],b)
      if d<len(dic[j]):
        if dic[j][d]<=c:
          ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
import string 

dic={c:[] for c in string.ascii_lowercase}
N=int(input())
S=list(input())
Q=int(input())
for i in range(len(S)):
  dic[S[i]].append(i+1)
for i in range(Q):
  a,b,c=map(str,input().split())
  if a=='1':
    if S[int(b)-1]==c:
      continue
    d=bisect_left(dic[S[int(b)-1]],int(b))
    e=bisect_left(dic[c],int(b))
    dic[S[int(b)-1]].pop(d)
    dic[c].insert(e,int(b))
  else:
    ans=0
    b,c=int(b),int(c)
    for j in string.ascii_lowercase:
      d=bisect_left(dic[j],b)
      if d<len(dic[j]):
        if dic[j][d]<=c:
          ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
Q = int(input())
target = ord("a")
k = [[0 for _ in range(n)] for _ in range(26)]
c = [0 for _ in range(n)]

for i in range(n):
	henkou = ord(s[i])-target
	k[henkou][i] += 1
	c[i] = henkou

class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)
	
	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def __init__(self, a):
		self.bitlen = len(a)+1
		self.bit = [0]*(len(a)+1)
		for i, j in enumerate(a):
			self.add(i, j)

b = [BIT(k[i]) for i in range(26)]

for _ in range(Q):
	q = input()
	if q[0] == "1":
		qa = int(q[2])
		hen = ord(q[4])-target
		b[hen].add(qa-1, 1)
		b[c[qa-1]].add(qa-1, -1)
		c[qa-1] = hen
	else:
		ans = 0
		qta = int(q[2])
		qtb = int(q[4])
		for i in range(26):
			if b[i].sum(qta-1, qtb) != 0:
				ans += 1
		print(ans)

Submission status: Runtime Error

Solution code:
n = int(input())
s = input()
Q = int(input())
target = ord("a")
al = [chr(target+i) for i in range(26)]
k = [[0 for _ in range(n)] for _ in range(26)]

for i in range(n):
	henkou = ord(s[i])-target
	k[henkou][i] += 1

class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)
	
	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def __init__(self, a):
		self.bitlen = len(a)+1
		self.bit = [0]*(len(a)+1)
		for i, j in enumerate(a):
			self.add(i, j)

b = [BIT(k[i]) for i in range(26)]

for _ in range(Q):
	q = input()
	if q[0] == "1":
		qa = int(q[2])
		qb = q[4]
		b[ord(qb)-target].add(qa-1, 1)
		b[ord(s[qa-1])-target].add(qa-1, -1)
	else:
		ans = 0
		qta = int(q[2])
		qtb = int(q[4])
		for i in range(26):
			if b[i].sum(qta-1, qtb) != 0:
				ans += 1
		print(ans)

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
s = input()
Q = int(input())
target = ord("a")
al = [chr(target+i) for i in range(26)]
k = [[0 for _ in range(n)] for _ in range(26)]

"""
空間計算量は大丈夫なのか？
"""


for i in range(n):
	henkou = ord(s[i])-target
	k[henkou][i] += 1
#ここまででO(n)かな？

"""
わたしはBITしかわからないのでBITを使います
26 * O(n)になりそうだが大丈夫かな？
"""

class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)

	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def search(self, a):
		tmpsum = 0
		i = 0
		k = (self.bitlen-1).bit_length()
		while k >= 0:
			tmpk = 2**k
			if i+tmpk <= self.bitlen-1:
				if tmpsum + self.bit[i+tmpk] < a:
					tmpsum += self.bit[i+tmpk]
					i += tmpk
			k = k - 1
		return i+1
	
	def output(self, a):
		return self.query(a+1)-self.query(a)
	
	def listout(self):
		return self.bit
	
	def __init__(self, a):
		self.bitlen = len(a)+1
		self.bit = [0]*(len(a)+1)
		for i, j in enumerate(a):
			self.add(i, j)

b = [BIT(k[i]) for i in range(26)]

"""
さてどうする？
type 2 -> search型 26*O(log n)
type 1 -> add 4通り 4*O(log n)
微妙なところだな、通るのか？

type 1　差を求める.
"""

for _ in range(Q):
	q = input()
	if q[0] == "1":
		qa = int(q[2])
		qb = q[4]
		b[ord(qb)-target].add(qa-1, 1)
		b[ord(s[qa-1])-target].add(qa-1, -1)
	else:
		ans = 0
		qa = int(q[2])
		qb = int(q[4])
		for i in range(26):
			if b[i].sum(qa-1, qb) != 0:
				ans += 1
		print(ans)

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
s = input()
Q = int(input())
al = [chr(ord("a") + i) for i in range(26)]
k = [[0 for _ in range(n)] for _ in range(26)]
c = []

"""
空間計算量は大丈夫なのか？
"""

for i in range(n):
	target = ord("a")
	henkou = ord(s[i])-target
	k[henkou][i] += 1
	c.append(henkou)
#ここまででO(n)かな？

"""
わたしはBITしかわからないのでBITを使います
26 * O(n)になりそうだが大丈夫かな？
"""

class BIT:
	"""
	<Attention> 0-indexed.
	query ... return the sum [0 to m]
	sum ... return the sum [a to b]
	sumall ... return the sum [all]
	add ... 'add' number to element (be careful that it doesn't set a value.)
	search ... the sum version of bisect.right
	output ... return the n-th element
	listout ... return the BIT list
	"""
	def query(self, m):
		res = 0
		while m > 0:
			res += self.bit[m]
			m -= m&(-m)
		return res
	
	def sum(self, a, b):
		return self.query(b)-self.query(a)
	
	def sumall(self):
		bitlen = self.bitlen-1
		return self.query(bitlen)

	def add(self, m, x):
		m += 1
		bitlen = len(self.bit)
		while m <= bitlen-1:
			self.bit[m] += x
			m += m&(-m)
		return
	
	def search(self, a):
		tmpsum = 0
		i = 0
		k = (self.bitlen-1).bit_length()
		while k >= 0:
			tmpk = 2**k
			if i+tmpk <= self.bitlen-1:
				if tmpsum + self.bit[i+tmpk] < a:
					tmpsum += self.bit[i+tmpk]
					i += tmpk
			k = k - 1
		return i+1
	
	def output(self, a):
		return self.query(a+1)-self.query(a)
	
	def listout(self):
		return self.bit
	
	def __init__(self, a):
		self.bitlen = len(a)+1
		self.bit = [0]*(len(a)+1)
		for i, j in enumerate(a):
			self.add(i, j)

b = [BIT(k[i]) for i in range(26)]

"""
さてどうする？
type 2 -> search型 26*O(log n)
type 1 -> add 4通り 4*O(log n)
微妙なところだな、通るのか？

type 1　差を求める.
"""

for _ in range(Q):
	q = input()
	if q[0] == "1":
		qa = int(q[2])
		qb = q[4]
		b[ord(qb)-target].add(qa-1, 1)
		b[c[qa-1]].add(qa-1, -1)
	else:
		ans = 0
		qa = int(q[2])
		qb = int(q[4])
		for i in range(26):
			if b[i].sum(qa-1, qb) != 0:
				ans += 1
		print(ans)

Submission status: Runtime Error

Solution code:
import bisect
n = int(input())
s = input()
q = int(input())
dic = {}

for i in range(n):
  if s[i] not in dic:
    dic[s[i]] = [i+1]
  else:
    dic[s[i]].append(i+1)
    
for i in range(q):
  query = input().split()
  if query[0] == "1":
    idx = bisect.bisect_left(dic[s[int(query[1])-1]], int(query[1]))
    dic[s[int(query[1])-1]].pop(idx)
    if query[2] not in dic:
      dic[query[2]] = [int(query[1])]
    else:
      dic[query[2]].append(int(query[1]))
  else:
    cnt = 0
    """
    for key in dic:
      if bisect.bisect_left(dic[key], int(query[1])) != bisect.bisect_left(dic[key], int(query[2])+1):
        cnt += 1
    """
    print(cnt)

Submission status: Runtime Error

Solution code:
s = input()
q = int(input())
dic = {}

for i in range(n):
  if s[i] not in dic:
    dic[s[i]] = [i+1]
  else:
    dic[s[i]].append(i+1)
    
for i in range(q):
  query = input().split()
  if query[0] == "1":
    idx = bisect.bisect_left(dic[s[int(query[1])-1]], int(query[1]))
    dic[s[int(query[1])-1]].pop(idx)
    if query[2] not in dic:
      dic[query[2]] = [int(query[1])]
    else:
      dic[query[2]].append(int(query[1]))
  else:
    cnt = 0
    for key in dic:
      if bisect.bisect_left(dic[key], int(query[1])) != bisect.bisect_left(dic[key], int(query[2])+1):
        cnt += 1
    print(cnt)

Submission status: Runtime Error

Solution code:
from collections import defaultdict
class segtree:
    def x_func(self,d1,d2):
        dret=defaultdict(int)
        keys=set(d1.keys())|set(d2.keys())
        for k in keys:
            dret[k]+=d1[k]+d2[k]
        return dret
    def __init__(self,N):
        self.n=(1<<len(bin(N-1)[2:]))
        self.x=[defaultdict(int) for _ in range(2*self.n)]
    def build(self,seq):
        for i, j in enumerate(seq):
            self.x[i+self.n][j]+=1
        for i in range(self.n-1, 0, -1):
            self.x[i]=self.x_func(self.x[i*2],self.x[i*2+1])
    def update(self, i, c):
        j=i+self.n
        s=list(self.x[j].keys())[0]
        while j>0:
            self.x[j][s]-=1
            self.x[j][c]+=1
            j//=2
    def get(self,l,r):
        ans=defaultdict(int)
        l+=self.n
        r+=self.n
        while l<r:
            if l%2==1:
                ans=self.x_func(self.x[l],ans)
                l+=1
            if r%2==0:
                ans=self.x_func(self.x[r],ans)
                r-=1
            l//=2
            r//=2
        if l==r:
            ans=self.x_func(self.x[r],ans)
        cnt=0
        for k in ans.keys():
            if ans[k]>0:
                cnt+=1
        print(cnt)
        
n=int(input())
s=list(input())
seg=segtree(n)
seg.build(s)
#print(seg.x)
for _ in range(int(input())):
    que=list(input().split())
    if que[0]=='1':
        seg.update(int(que[1]), que[2])
    elif que[0]=='2':
        seg.get(int(que[1])-1,int(que[2])-1)

Submission status: Runtime Error

Solution code:
n=int(input())
s=input()
q=int(input())
for i in range(q):
    a=list(map(str,input().split()))
    if int(a[0])==1:
       tmp=int(a[1])-1
       s=s[:tmp]+a[2]+s[tmp+1:]
       print(s)
    else:
        front=int(a[1])-1
        after=int(a[2])-1
        kind=0
        for j in range(26):
            alpha=chr(ord('a') + j)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)

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

    a_ord = ord('a')
    z_ord = ord('z')

    set_list = [[] for _ in range(z_ord+1)]
    for i in range(N):
        s = S[i]
        bisect.insort_left(set_list[ord(s)],i)

    Q = int(input())
    for q in range(Q):
        ipt = input().split()
        if ipt[0] == "1":
            i,c = int(ipt[1]), ipt[2]
            j = ord(S[i-1])

            if j == ord(c): continue
            set_list[j].remove(i-1)
            bisect.insort_left(set_list[ord(c)],i-1)
            S[i-1] = c
            # print(set_list[])

        else:
            l,r = int(ipt[1]), int(ipt[2])
            ans = 0
            # if l == r:
            #     print(1)
            #     continue

            for i in range(a_ord,z_ord+1):
                st = set_list[i]
                if not len(st) > 0: continue

                # print(i,set_list[i])
                l_p = bisect.bisect_left(st,l-1)
                r_p = bisect.bisect_right(st,r-1)

                # print(l-1,r-1,l_p,r_p)
                if l_p < r_p:
                    ans += 1

            # print(ans,"____")
            print(ans)



if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

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

    a_ord = ord('a')
    z_ord = ord('z')

    set_list = [set() for _ in range(z_ord+1)]
    for i in range(N):
        s = S[i]
        set_list[ord(s)].add(i)

    Q = int(input())
    for q in range(Q):
        ipt = input().split()
        if ipt[0] == "1":
            i,c = int(ipt[1]), ipt[2]
            s = S[i-1]

            set_list[ord(s)].remove(i-1)
            set_list[ord(c)].add(i-1)

        else:
            l,r = int(ipt[1]), int(ipt[2])
            ans = 0
            # if l == r:
            #     print(1)
            #     continue

            for i in range(a_ord,z_ord+1):
                st = list(set_list[i])
                if not len(st) > 0: continue

                # print(i,set_list[i])
                l_p = bisect.bisect_left(st,l-1)
                r_p = bisect.bisect_right(st,r-1)

                # print(l-1,r-1,l_p,r_p)
                if l_p < r_p:
                    ans += 1

            # print(ans,"____")
            print(ans)



if __name__ == "__main__":
  main()

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
class SegmentTree:
    #for pypy
    #treeは1-based-index
    __slots__=["size","func","default_val","tree","first_idx"]
    def __init__(self,initial_value_list,func,default_val,first_index=0):
        n=len(initial_value_list)
        self.first_idx=first_index
        self.size=1<<(n-1).bit_length()
        self.func=func#適用関数
        self.default_val=default_val#初期値
        self.tree=[default_val for i in range(2*self.size)]
        # 木の構築
        for i in range(n):
            d=[0]*26;d[initial_value_list[i]-97]=1
            self.tree[self.size+i]=d
        for i in range(self.size-1,0,-1):
            self.tree[i]=self.func(self.tree[2*i],self.tree[2*i+1])

    def update(self,k,x):
        k+=self.size-self.first_idx
        self.tree[k]=x
        while k>1:
            k>>=1
            self.tree[k]=self.func(self.tree[2*k],self.tree[2*k+1])
    def query(self, l, r):
        l+=self.size
        r+=self.size
        lret,rret=self.default_val,self.default_val
        while l<r:
            if l&1:
                lret=self.func(lret,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rret=self.func(self.tree[r], rret) # モノイドでは可換律は保証されていないので演算の方向に注意
            l>>=1
            r>>=1
        return self.func(lret, rret)
n=int(input())
def add(x,y):
    v=[0]*26
    for i in range(26):
        v[i]=x[i]+y[i]
    return v
seg=SegmentTree(list(input().rstrip()),add,[0]*26,1)
q=int(input())

for i in range(q):
    a,s,d=input().split()
    if int(a)==1:
        s=int(s)
        v=[0]*26;v[int.from_bytes(d,'big')-97]+=1
        seg.update(s,v)
        
    else:
        r=seg.query(1,int(s))
        l=seg.query(1,int(d)+1)
        
        ans=0
        for i in range(26):
            if l[i]>r[i]:ans+=1
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
class SegmentTree:
    #for pypy
    #treeは1-based-index
    __slots__=["size","func","default_val","tree","first_idx"]
    def __init__(self,initial_value_list,func,default_val,first_index=0):
        n=len(initial_value_list)
        self.first_idx=first_index
        self.size=1<<(n-1).bit_length()
        self.func=func#適用関数
        self.default_val=default_val#初期値
        self.tree=[default_val for i in range(2*self.size)]
        # 木の構築
        for i in range(n):
            d=[0]*26;d[initial_value_list[i]-97]=1
            self.tree[self.size+i]=d
        for i in range(self.size-1,0,-1):
            self.tree[i]=self.func(self.tree[2*i],self.tree[2*i+1])

    def update(self,k,x):
        k+=self.size-self.first_idx
        self.tree[k]=x
        while k>1:
            k>>=1
            self.tree[k]=self.func(self.tree[2*k],self.tree[2*k+1])
    def query(self, l, r):
        l+=self.size
        r+=self.size
        lret,rret=self.default_val,self.default_val
        while l<r:
            if l&1:
                lret=self.func(lret,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rret=self.func(self.tree[r], rret) # モノイドでは可換律は保証されていないので演算の方向に注意
            l>>=1
            r>>=1
        return self.func(lret, rret)
n=int(input())
def add(x,y):
    v=[0]*26
    for i in range(26):
        v[i]=x[i]+y[i]
    return v
seg=SegmentTree(list(input().rstrip()),add,[0]*26,1)
q=int(input())

for i in range(q):
    a,s,d=input().split()
    if int(a)==1:
        s=int(s)
        v=[0]*26;v[int.from_bytes(d,'big')-97]+=1
        seg.update(s,v)
        
    else:
        r=seg.query(1,int(s)-1)
        l=seg.query(1,int(d)+1)
        
        ans=0
        for i in range(26):
            if l[i]>r[i]:ans+=1
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
input=sys.stdin.buffer.readline
sys.setrecursionlimit(10**9)
class SegmentTree:
    #for pypy
    #treeは1-based-index
    __slots__=["size","func","default_val","tree","first_idx"]
    def __init__(self,initial_value_list,func,default_val,first_index=0):
        n=len(initial_value_list)
        self.first_idx=first_index
        self.size=1<<(n-1).bit_length()
        self.func=func#適用関数
        self.default_val=default_val#初期値
        self.tree=[default_val for i in range(2*self.size)]
        # 木の構築
        for i in range(n):
            d=[0]*26;d[initial_value_list[i]-97]=1
            self.tree[self.size+i]=d
        for i in range(self.size-1,0,-1):
            self.tree[i]=self.func(self.tree[2*i],self.tree[2*i+1])

    def update(self,k,x):
        k+=self.size-self.first_idx
        self.tree[k]=x
        while k>1:
            k>>=1
            self.tree[k]=self.func(self.tree[2*k],self.tree[2*k+1])
    def query(self, l, r):
        l+=self.size
        r+=self.size
        lret,rret=self.default_val,self.default_val
        while l<r:
            if l&1:
                lret=self.func(lret,self.tree[l])
                l+=1
            if r&1:
                r-=1
                rret=self.func(self.tree[r], rret) # モノイドでは可換律は保証されていないので演算の方向に注意
            l>>=1
            r>>=1
        return self.func(lret, rret)
n=int(input())
def add(x,y):
    v=[0]*26
    for i in range(26):
        v[i]=x[i]+y[i]
    return v
seg=SegmentTree(list(input().rstrip()),add,[0]*26,1)
q=int(input())
print(*seg.tree,sep="\n")
for i in range(q):
    a,s,d=input().split()
    if int(a)==1:
        s=int(s)
        v=[0]*26;v[int.from_bytes(d,'big')-97]+=1
        seg.update(s,v)
        print(*seg.tree,sep="\n")
        
    else:
        r=seg.query(1,int(s)-1)
        l=seg.query(1,int(d)+1)
        
        ans=0
        for i in range(26):
            if l[i]>r[i]:ans+=1
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
import bisect
import copy

N = int(sys.stdin.readline().rstrip())
S = list(sys.stdin.readline().rstrip())
Q = int(sys.stdin.readline().rstrip())

cnt = [0] * 26
cumcnt = [cnt]

for i, s in enumerate(S):
    tmp = copy.copy(cumcnt[i])
    tmp[ord(s) - ord("a")] += 1
    cumcnt.append(tmp)

q_remove = {}
q_add = {}

for _ in range(Q):
    t, i, c = sys.stdin.readline().rstrip().split()
    t = int(t)
    i = int(i)
    d = S[i - 1]
    if t == 1:
        if d != c:
            if d not in q_remove.keys():
                q_remove[d] = [i]
            else:
                # q_remove[d].append(i)
                bisect.insort(q_remove[d], i)
            if c not in q_add.keys():
                q_add[c] = [i]
            else:
                # q_add[c].append(i)
                bisect.insort(q_add[d], i)
    else:
        c = int(c)
        cnt_l = copy.copy(cumcnt[i - 1])
        cnt_r = copy.copy(cumcnt[c])
        for q, idx in q_add.items():
            x = bisect.bisect_right(idx, i - 1)
            y = bisect.bisect_right(idx, c)
            cnt_l[ord(q) - ord("a")] += x
            cnt_r[ord(q) - ord("a")] += y
        for q, idx in q_remove.items():
            x = bisect.bisect_right(idx, i - 1)
            y = bisect.bisect_right(idx, c)
            cnt_l[ord(q) - ord("a")] -= x
            cnt_r[ord(q) - ord("a")] -= y
        ans = 0
        for l, r in zip(cnt_l, cnt_r):
            if r - l > 0:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
import bisect

N = int(input())
S = list(input())
Q = int(input())
K = []
for i in range(Q):
    a = list(input().split())
    K.append([int(a[0]),int(a[1]),a[2]])

C = {}
for i in range(97,97+26):
    C[chr(i)] = []

for i in C.values():
    i.append(-1)

for i in range(N):
    C[S[i]].append(i)

for i in C.values():
    i.append(10**8)

for i in range(Q):
    if K[i][0] == 1:
        t = K[i][1]-1
        C[S[t]].remove(t)
        C[K[i][2]].append(t)
        C[K[i][2]].sort()
    else:
        s = K[i][1] - 1
        t = int(K[i][2]) - 1
        ans = 0
        for v in C.values():
            a = bisect.bisect_left(v,s)
            b = bisect.bisect_right(v,t)
            if a != b:
                ans += 1
        print(ans)

Submission status: Runtime Error

Solution code:
from bisect import bisect_left
from bisect import bisect_right

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

ind_list = [[] for _ in range(26)]

for i, x in enumerate(s):
    ind_list[ord(x)-97].append(i)

for _ in range(q):
    _type, val1, val2 = input().split()
    if _type == '1':
        i = int(val1)-1
        c = val2
        ind_list[ord(s[i])-97].remove(i)
        ind_list[ord(c)-97].append(i)
        ind_list[ord(c)-97].sort()
    elif _type == '2':
        l = int(val1)-1
        r = int(val2)-1
        ans = 0
        for i in range(26):
            if bisect_right(ind_list[i], r) - bisect_left(ind_list[i], l) > 0:
                ans += 1
        print(ans)
    else:
        print('Exception caught!')
        exit()

Submission status: Runtime Error

Solution code:
import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        if s==B:
            continue
        o=ord(s)-ord("a")
        alphabet[o].pop(bisect.bisect_left(alphabet[o],A-1))
        index=bisect.bisect(alphabet[B-1],A-1)
        alphabet[B-1].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            #indexR=bisect.bisect_right(alphabet[i],B-1)
            #ans+=(indexL!=indexR)
            if indexL==len(alphabet[i]):
                continue
            ans+=(alphabet[i][indexL]<=B-1)
        print(ans)

Submission status: Runtime Error

Solution code:
import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        if s==B:
            continue
        o=ord(s)-ord("a")
        alphabet[o].pop(bisect.bisect_left(alphabet[o],A-1))
        index=bisect.bisect(alphabet[o],A-1)
        #alphabet[o]=alphabet[o][:index]+[A-1]+alphabet[o][index:]
        #bisect.insort(alphabet[o],A-1)
        alphabet[B-1].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            #indexR=bisect.bisect_right(alphabet[i],B-1)
            #ans+=(indexL!=indexR)
            if indexL==len(alphabet[i]):
                continue
            ans+=(alphabet[i][indexL]<=B-1)
        print(ans)

Submission status: Runtime Error

Solution code:
import bisect
N=input()
S=list(input())
alphabet=[[] for _ in range(26)]
for i,s in enumerate(S):
    alphabet[ord(s)-ord('a')].append(i)
Q=int(input())
for _ in range(Q):
    Type,A,B=input().split()
    if Type=="1":
        A=int(A)
        s=S[A-1]
        o=ord(s)-ord("a")
        alphabet[o].pop(bisect.bisect_left(alphabet[o],A-1))
        index=bisect.bisect(alphabet[o],A-1)
        #alphabet[o]=alphabet[o][:index]+[A-1]+alphabet[o][index:]
        #bisect.insort(alphabet[o],A-1)
        alphabet[ord(B)-ord("a")].insert(index,A-1)
        S[A-1]=B
    else:
        A=int(A)
        B=int(B)
        ans=0
        for i in range(26):
            indexL=bisect.bisect_left(alphabet[i],A-1)
            #indexR=bisect.bisect_right(alphabet[i],B-1)
            #ans+=(indexL!=indexR)
            if indexL==len(alphabet[i]):
                continue
            ans+=(alphabet[i][indexL]<=B-1)
        print(ans)