Problem p02763 (python)

Fixed submission:
n = int(input())
stmp = list(input())
Q = int(input())
target = ord("a")
s = [ord(stmp[i])-target for i in range(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 __init__(self, n):
		self.bitlen = n+1
		self.bit = [0]*(n+1)

b = [BIT(n) for i in range(26)]
for i in range(n):
	b[s[i]].add(i, 1)

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

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
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)

Buggy submission (verdict: Runtime Error):
try:
	n = int(input())
	s = input()
	q = int(input())
	for i in range(q):
		c=list(input().split())
		if c[0]=="1":
			s=s[:int(c[1])-1]+c[2]+s[int(c[1]):]
		else:
			print(len(set(s[int(c[1])-1:int(c[2])])))
except:
    import traceback
    traceback.print_exc()
input()