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: Wrong Answer

Solution code:
N = int(input())
S = ["*"]*(N+1)
S[1:] = list(input())
Q = int(input())
q1,q2,q3 = [0]*Q,[0]*Q,[0]*Q
for i in range(Q):
    tmp = input().split()
    q1[i],q2[i] = map(int,tmp[:2])
    if q1[i] == 2:
        q3[i] = int(tmp[2])
    else:
        q3[i] = tmp[2]

class BIT:
    def __init__(self, n, init_list):
        self.num = n + 1
        self.tree = [0] * self.num
        for i, e in enumerate(init_list):
            self.update(i, e)

    #a_kにxを加算
    def update(self, k, x):
        k = k + 1
        while k < self.num:
            self.tree[k] += x
            k += (k & (-k))
        return

    def query1(self, r):
        ret = 0
        while r > 0:
            ret += self.tree[r]
            r -= r & (-r)
        return ret

    #通常のスライスと同じ。lは含み、rは含まない
    def query2(self, l, r):
        return self.query1(r) - self.query1(l)

s_pos = [BIT(N+1,[0]*(N+1)) for _ in range(26)]

for i in range(1,N+1):
    s_pos[ord(S[i]) - ord("a")].update(i,1)

alphabets = [chr(ord("a") + i) for i in range(26)]

for i in range(Q):
    if q1[i] == 1:
        s_pos[ord(S[q2[i]]) - ord("a")].update(q2[i],-1)
        S[q2[i]] = q3[i]
        print(S)
        s_pos[ord(q3[i]) - ord("a")].update(q2[i],1)
    else:
        ans = 0
        for c in alphabets:
            if s_pos[ord(c) - ord("a")].query2(q2[i],q3[i]+1) > 0:
                ans += 1
        print(ans)

Submission status: Wrong Answer

Solution code:
class SegmentTree():
    """A segment Tree.

    This is a segment tree without recursions.
    This can support queries as follows:
     - update a single value in O(logN).
     - get the folded value of values in a segment [l, r) in O(logN)
    N is the length of the given iterable value.

    Parameters
    ----------
    iterable : Iterable[_T]
        An iterable value which will be converted into a segment tree
    func : Callable[[_T, _T], _T]
        A binary function which returns the same type as given two.
        This has to satisfy the associative law:
            func(a, func(b, c)) = func(func(a, b), c)
    e : _T
        The identity element of the given func.
        In other words, this satisfies:
            func(x, e) = func(e, x) = x
    """
    
    def __init__(self, iterable, func, e):
        self.func = func
        self.e = e

        ls = list(iterable)
        self.n = 1 << len(ls).bit_length()
        ls.extend( [self.e] * (self.n - len(ls)) )

        self.data = [self.e] * self.n + ls
        for i in range(self.n-1, 0, -1):
            self.data[i] = self.func(self.data[2*i], self.data[2*i+1])

    def replace(self, index, value):
        """replace the old value of the given index with the given new value.

        This replaces the old value of the given index with the given new value in O(logN).
        This is like "list[index] = value".

        Parameters
        ----------
        index : int
            The index of the value which will be replaced.
        value : _T
            The new value with which the old value will be replaced.
        """
        index += self.n
        self.data[index] = value
        index //= 2
        while index > 0:
            self.data[index] = self.func(self.data[2*index], self.data[2*index+1])
            index //= 2
        
    def folded(self, l, r):
        """get the folded value of values in a segment [l, r).

        This get the folded value of values in a segment [l, r) in O(logN).
        If func is add, it returns the sum of values in [l, r).
        In other words, this is eqivalent to "sum(list[l:r])".
        If func is other functions, then this is equivalent to "accumulate(list[l:r], func)".

        Parameters
        ----------
        l : int
            The left edge.
        r : int
            The right edge.

        Returns
        -------
        _T(the same type as the type of the element of the given iterable)
            This is equivalent to func(list[l], func(list[l+1], ... ) ).
            If func is represented as '*', then it's:
            list[l] * list[l+1] * ... * list[r-1] 
        """

        left_folded = self.e
        right_folded = self.e
        l += self.n
        r += self.n
        while l < r:
            if l % 2:
                left_folded = self.func(left_folded, self.data[l])
                l += 1
            if r % 2:
                r -= 1
                right_folded = self.func(self.data[r], right_folded)
            l //= 2
            r //= 2
        
        return self.func(left_folded, right_folded)


from operator import or_

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

ls = [1 << (ord(c) - ord('a')) for c in S]
segtree = SegmentTree(ls, or_, 0)

Q = int(input())
for _ in range(Q):
    s = input()
    if s[0] == '1':
        i, c = s[2:].split()
        segtree.replace(int(i), 1 << (ord(c) - ord('a')))
    else:
        l, r = map(int, s[2:].split())
        value = segtree.folded(l-1, r)
        print(format(value, 'b').count('1'))

Submission status: Wrong Answer

Solution code:
import sys

input = lambda: sys.stdin.readline().rstrip()


class SegTree:

    def __init__(self, init_val, segfunc, ide_ele):

        n = len(init_val)
        self.ide_ele = ide_ele
        self.segfunc = segfunc
        self.num = 2**(n - 1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num

        for i in range(n):
            self.seg[i + self.num - 1] = init_val[i]

        for i in range(self.num - 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.num - 1
        self.seg[k] = x
        while k:
            k = (k - 1) // 2
            self.seg[k] = self.segfunc(self.seg[k * 2 + 1], self.seg[k * 2 + 2])

    def query(self, p, q):
        if q <= p:
            return self.ide_ele
        p += self.num - 1
        q += self.num - 2
        res = self.ide_ele
        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 solve():

    N = int(input())
    S = list(input())
    Q = int(input())
    seg = [1 << (ord(s) - ord('a')) for s in S]

    segtree = []
    segfunc = lambda a, b: a | b

    segtree = SegTree(seg, segfunc, 0)

    ans = []
    for i in range(Q):
        a, b, c = input().split()
        a = int(a)

        if a == 1:
            b = int(b) - 1
            al = ord(c) - ord('a')
            segtree.update(b, al)
        elif a == 2:
            b, c = int(b) - 1, int(c)
            res = segtree.query(b, c)
            res = sum(list(map(int, bin(res)[2:])))
            ans.append(res)

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left,bisect_right
import string 

dic = {c:[] for c in string.ascii_lowercase}

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

for i,c in enumerate(s,start=1):
  dic[c].append(i)
print(dic)

for i in range(q):
  p,l,r = map(str,input().split())
  if p =='1':
    j = int(l)
    if r == s[j-1]:
      continue
    c = s[j-1]    
    dic[c].pop(bisect_left(dic[c],j))
    dic[r].insert(bisect_left(dic[r],j),j)
    s[j-1] = r
  else:
    ans = 0
    l = int(l)
    r = int(r)
    for c in string.ascii_lowercase:
      pl = bisect_left(dic[c],l)
      if pl < len(dic[c]):
        if dic[c][pl] <= r:
          ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
from sys import stdin

class SegmentTree:
    # 初期化処理
    # f : SegmentTreeにのせるモノイド
    # default : fに対する単位元
    def __init__(self, size, f=lambda x,y : x+y, default=0):
        self.size = 2**(size-1).bit_length() # 簡単のため要素数Nを2冪にする
        self.default = default
        self.dat = [default]*(self.size*2) # 要素を単位元で初期化
        self.f = f

    def update(self, i, x):
        i += self.size
        self.dat[i] = x
        while i > 0:
            i >>= 1
            self.dat[i] = self.f(self.dat[i*2], self.dat[i*2+1])

    def query(self, l, r):
        l += self.size
        r += self.size
        lres, rres = self.default, self.default
        while l < r:
            if l & 1:
                lres = self.f(lres, self.dat[l])
                l += 1

            if r & 1:
                r -= 1
                rres = self.f(self.dat[r], rres) # モノイドでは可換律は保証されていないので演算の方向に注意
            l >>= 1
            r >>= 1
        res = self.f(lres, rres)
        return res
def bc(x):
    return bin(x).count("1")

n = int(stdin.readline().rstrip())
s = stdin.readline().rstrip()
q = int(stdin.readline().rstrip())

lamb_or = lambda x,y : x|y
seg = SegmentTree(n,lamb_or,0)

for i,x in enumerate(s):
    seg.update(i,ord(x)-97)

for _ in range(q):
    c,x,y = [x for x in stdin.readline().rstrip().split()]
    if c == '1':
        x = int(x)
        seg.update(x-1,ord(y)-97)
    elif c == '2':
        x = int(x)
        y = int(y)
        print(bc(seg.query(x-1,y))+1)

Submission status: Wrong Answer

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,qtmpa,qtmpb = input().split()
	if q[0] == "1":
		qa = int(qtmpa)
		b[ord(qtmpb)-target].add(qa-1, 1)
		b[ord(s[qa-1])-target].add(qa-1, -1)
	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)

Submission status: Wrong Answer

Solution code:
class segtree:
    def __init__(self,N):
        self.n=(1<<len(bin(N-1)[2:]))
        self.x=[0 for _ in range(2*self.n)]
    def build(self,seq):
        for i, j in enumerate(seq, start=self.n):
            self.x[i]=1<<j
        for i in range(self.n-1, 0, -1):
            self.x[i]=self.x[i*2]|self.x[i*2+1]
    def update(self, i, c):
        j=i+self.n
        self.x[j]=1<<c
        while j>1:
            j//=2
            self.x[j]=self.x[j*2]|self.x[j*2+1]
    def get(self,l,r):
        ans=0
        l+=self.n
        r+=self.n
        while l<r:
            if l%2==1:
                ans|=self.x[l]
                l+=1
            if r%2==0:
                ans|=self.x[r]
                r-=1
            l//=2
            r//=2
        if l==r:
            ans|=self.x[r]
        cnt=sum(list(map(int, list(bin(ans)[2:]))))
        print(cnt)
        
n=int(input())
s=list(input())
s=[ord(i)-97 for i in s]
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]), ord(que[2])-97)
    elif que[0]=='2':
        seg.get(int(que[1])-1,int(que[2])-1)

Submission status: Wrong Answer

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

def init():
    #set_val
    #for j in range(26):
    #  for i in range(n):
    #    seg[j][i+num-1]=init_val[i]    
    #built
    for j in range(26):
      for i in range(num-2,-1,-1) :
        seg[j][i]=max(seg[j][2*i+1],seg[j][2*i+2]) 
    
def update(k,x):
    K =k+num-1
    seg[SS[k]][K] = 0
    while K:
        K = (K-1)//2
        seg[SS[k]][K] = max(seg[SS[k]][K*2+1],seg[SS[k]][K*2+2])
    K =k+num-1
    seg[x][K]=1
    while K:
      K=(K-1)//2
      seg[x][K]=max(seg[x][K*2+1],seg[x][K*2+2])
    
def query(p,q):
  a=0
  for i in range(26):
    P =p+ num-1
    Q =q+ num-1
    res=ide_ele
    while Q-P>1:
        if P&1 == 0:
            res = max(res,seg[i][P])
        if Q&1 == 1:
            res = max(res,seg[i][Q])
            Q -= 1
        P = P//2
        Q = (Q-1)//2
    if P == Q:
        res = max(res,seg[i][Q])
    else:
        res = max(max(res,seg[i][P]),seg[i][Q])
    a=a+res
  print(a)
  return a

n=int(input())
S=input()
q=int(input())


#####単位元######
ide_ele = 0

#num:n以上の最小の2のべき乗
num =2**(n-1).bit_length()
seg=[[ide_ele]*2*num for i in range(26)]


SS=[0]*num
for i in range(n):
  seg[ord(S[i])-97][i+num-1]=1
  SS[i]=ord(S[i])-97
#print(SS)
#print(seg)
init()
#print(seg)

for _ in range(q):
  SSS=list(input().split())
  #print(SSS)
  if SSS[0]=="1":
    #print(int(SSS[1])-1,ord(SSS[2])-97)
    update(int(SSS[1])-1,ord(SSS[2])-97)
  else:
    query(int(SSS[1])-1,int(SSS[2])-1)
#print(seg)

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
s = input()
q = int(input())
qry = [input().split() for j in range(q)]

moji = []

for i in range(n):
    moji.append(s[i])

dp = [[0 for i in range(26)] for j in range(n+1)]

for i in range(n):
    for j in range(26):
        dp[i+1][j] = dp[i][j]
    dp[i+1][ord(s[i])-ord('a')] += 1

li = []
#print(dp)
#exit()
        
for i in range(q):
    if qry[i][0] == '1':
        li.append([int(qry[i][1]),ord(qry[i][2])-ord('a')])
    else:
        ans = [0]*26
        for j in range(26):
            #print(qry[i][2],qry[i][1])
            ans[j] = dp[int(qry[i][2])][j] - dp[int(qry[i][1])-1][j]
        kt = 0
        #print(li)
        for j in range(len(li)):
            if li[j][0] >= int(qry[i][1]) and li[j][0] <= int(qry[i][2]):
                #print(moji[li[j][0]],li[j][0])
                ans[ord(moji[li[j][0]-1])-ord('a')] -= 1
                moji[li[j][0]-1] = chr(li[j][1]+ord('a'))
                ans[li[j][1]] += 1
        for j in range(26):
            #print(ans[j],j)
            if ans[j] > 0:
                kt += 1
        print(kt)
        #for i in range(len(li)):

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
s = input()
q = int(input())
qry = [input().split() for j in range(q)]

moji = []

for i in range(n):
    moji.append(s[i])

dp = [[0 for i in range(26)] for j in range(n+1)]

for i in range(n):
    for j in range(26):
        dp[i+1][j] = dp[i][j]
    #dp[i+1] = copy.deepcopy(dp[i])
    dp[i+1][ord(s[i])-ord('a')] += 1

li = []
exit()
#print(dp)
#exit()
        
for i in range(q):
    if qry[i][0] == '1':
        li.append([int(qry[i][1]),ord(qry[i][2])-ord('a')])
    else:
        ans = [0]*26
        for j in range(26):
            #print(qry[i][2],qry[i][1])
            ans[j] = dp[int(qry[i][2])][j] - dp[int(qry[i][1])-1][j]
        kt = 0
        #print(li)
        for j in range(len(li)):
            if li[j][0] >= int(qry[i][1]) and li[j][0] <= int(qry[i][2]):
                #print(moji[li[j][0]],li[j][0])
                ans[ord(moji[li[j][0]-1])-ord('a')] -= 1
                moji[li[j][0]-1] = chr(li[j][1]+ord('a'))
                ans[li[j][1]] += 1
        for j in range(26):
            #print(ans[j],j)
            if ans[j] > 0:
                kt += 1
        print(kt)
        #for i in range(len(li)):

Submission status: Wrong Answer

Solution code:
import copy
n = int(input())
s = input()
q = int(input())
qry = [input().split() for j in range(q)]

moji = []

for i in range(n):
    moji.append(s[i])

dp = [[0 for i in range(26)] for j in range(n+1)]

for i in range(n):
    dp[i+1] = copy.deepcopy(dp[i])
    dp[i+1][ord(s[i])-ord('a')] += 1

li = []
exit()
#print(dp)
#exit()
        
for i in range(q):
    if qry[i][0] == '1':
        li.append([int(qry[i][1]),ord(qry[i][2])-ord('a')])
    else:
        ans = [0]*26
        for j in range(26):
            #print(qry[i][2],qry[i][1])
            ans[j] = dp[int(qry[i][2])][j] - dp[int(qry[i][1])-1][j]
        kt = 0
        #print(li)
        for j in range(len(li)):
            if li[j][0] >= int(qry[i][1]) and li[j][0] <= int(qry[i][2]):
                #print(moji[li[j][0]],li[j][0])
                ans[ord(moji[li[j][0]-1])-ord('a')] -= 1
                moji[li[j][0]-1] = chr(li[j][1]+ord('a'))
                ans[li[j][1]] += 1
        for j in range(26):
            #print(ans[j],j)
            if ans[j] > 0:
                kt += 1
        print(kt)
        #for i in range(len(li)):

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from bisect import bisect_left
from collections import defaultdict


def read():
    N = int(input().strip())
    S = input().strip()
    Q = int(input().strip())
    return N, S, Q


def solve_online(N, S, Q):
    trees = defaultdict(set)
    base = ord("a")
    
    for i in range(N):
        trees[ord(S[i]) - base].add(i)

    for _ in range(Q):
        op, a, b = input().strip().split()
        if op == "1":
            i, c1 = int(a)-1, ord(b) - base
            for c0 in range(26):
                trees[c0].discard(i)
            trees[c1].add(i)
        elif op == "2":
            l, r = int(a)-1, int(b)-1
            ans = 0
            for c in range(26):
                low = bisect_left(list(trees[c]), l)
                high = bisect_left(list(trees[c]), r+1)
                if high - low > 0:
                    ans += 1
            print(ans)


if __name__ == '__main__':
    inputs = read()
    outputs = solve_online(*inputs)
    if outputs is not None:
        print("%s" % str(outputs))

Submission status: Wrong Answer

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[c], 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: Wrong Answer

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)
            if c not in q_add.keys():
                q_add[c] = [i]
            else:
                q_add[c].append(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: Wrong Answer

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 = [copy.copy(cnt)]

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

query = {}

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:
            key = d + "_" + c
            if key not in query:
                query[key] = [i]
            else:
                query[key].append(i)
    else:
        c = int(c)
        cnt_l = copy.copy(cumcnt[i - 1])
        cnt_r = copy.copy(cumcnt[c])
        for key, idx in query.items():
            m, n = key.split("_")
            x = bisect.bisect_right(idx, i)
            cnt_l[ord(m) - ord("a")] -= x
            cnt_l[ord(n) - ord("a")] += x
            y = bisect.bisect_right(idx, c)
            cnt_r[ord(m) - ord("a")] -= y
            cnt_r[ord(n) - ord("a")] += y
        ans = 0
        for l, r in zip(cnt_l, cnt_r):
            if r - l > 0:
                ans += 1
        print(ans)

Submission status: Wrong Answer

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

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
S = ns()
assert len(S) == N
Q = ni()
qs = []
for i in range(Q):
    q = ns().split()
    qs.append(q)


def main():
    orda = ord("a")
    ords = [ord(ch) for ch in S]
    bits = [BIT(N) for _ in range(26)]
    for i, ch in enumerate(ords):
        bits[ch - orda].add(i + 1, +1)  # 1-origin
    for q in qs:
        if q[0] == "1":
            j = int(q[1])  # 1-origin
            nch = ord(q[2]) - orda
            och = ords[j - 1] - orda
            if nch != och:
                bits[och].add(j, -1)
                bits[nch].add(j, +1)
        else:
            assert q[0] == "2"
            l, r = int(q[1]), int(q[2])  # 1-origin
            n = 0
            for i in range(26):
                b = bits[i]
                if b.sum(r) - b.sum(l - 1) > 0:
                    n += 1
            print(n)


# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


main()

Submission status: Wrong Answer

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

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N = ni()
S = ns()
assert len(S) == N
Q = ni()
qs = []
for i in range(Q):
    q = ns().split()
    qs.append(q)


def main():
    orda = ord("a")
    ords = [ord(ch) for ch in S]
    bits = [BIT(N + 1) for _ in range(26)]
    for i, ch in enumerate(ords):
        offset = ch - orda
        bits[offset].add(i + 1, +1)
    for q in qs:
        if q[0] == "1":
            j = int(q[1])  # 1-origin
            nch = ord(q[2]) - orda
            och = ords[j - 1] - orda
            if nch != och:
                bits[och].add(j, -1)
                bits[nch].add(j, +1)
        else:
            assert q[0] == "2"
            l, r = int(q[1]), int(q[2])  # 1-origin
            cardinality = 0
            for i in range(26):
                if bits[i].get(l - 1, r) > 0:
                    cardinality += 1
            print(cardinality)


# Binary Indexed Tree (Fenwick Tree)
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)


main()

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
x = {}
for i in range(26):
    x[chr(97+i)] = [0 for _j in range(n)]

for i in range(n):
    x[s[i]][i] = 1
q = int(input())

for _i in range(q):
    y = list(input().split())
    i = int(y[1])-1
    if y[0] == "1":
        x[s[i]][i] = 0
        x[y[2]][i] = 1
    else:
        c = 0
        for _j, j in x.items():
            if 1 in j[i:int(y[2])]:
                c += 1
        print(c)

Submission status: Wrong Answer

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

x = [[0 for _i in range(n)] for _j in range(26)]
for i in range(n):
    x[ord(s[i])-97][i] = 1
q = int(input())
r = []
for _i in range(q):
    y = list(input().split())
    i = int(y[1])-1
    if y[0] == "1":
        x[ord(s[i])-97][i] = 0
        x[ord(y[2])-97][i] = 1
    else:
        c = 0
        for j in range(26):
            if 1 in x[j][i:int(y[2])]:
                c += 1
        r.append(c)
print(*r)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
s = input()
q = int(input())
w = math.ceil(n ** 0.5)
h = (n + w - 1) // w
sq = [[] for i in range(h)]
cq = [[] for _ in range(h)]

for i in range(h):
    l = list(s[w*i:w*(i+1)])
    sq[i] = l
    cq[i] = list(set(l))
#print(sq,cq)
ansl = []
anss = []
for j in range(q):
    k,a,b = input().split()
    if k =='1':
        i = int(a)
        p,r = (i - 1) // w, (i - 1) % w
        if sq[p][r] != b:
            sq[p][r] = b
            cq[p] = list(set(sq[p]))
        #print(*sq)
        #print(cq)
    else:
        a,b = int(a),int(b)
        ap,ar = (a - 1) // w, (a - 1) % w
        bp,br = (b - 1) // w, (b - 1) % w
        ans = 0
        l = []
        if bp - ap >= 2:
            for i in range(ap,bp+1):
                l.extend(cq[i])
            l.extend(sq[ap][ar:])
            l.extend(sq[bp][:br+1])
            ansl.append(len(set(l)))
        elif bp - ap == 1:
            l.extend(sq[ap][ar:])
            l.extend(sq[bp][:br+1])
            ansl.append(len(set(l)))
        else:
            l.extend(sq[ap][ar:br+1])
            ansl.append(len(set(l)))
        anss.append(l)

for i in range(len(ansl)):
    print(ansl[i])

#print(sq)
#print(cq)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
s = input()
q = int(input())
w = math.ceil(n ** 0.5)
h = (n + w - 1) // w
sq = [[] for i in range(h)]
cq = [[] for _ in range(h)]

for i in range(h):
    l = list(s[w*i:w*(i+1)])
    sq[i] = l
    cq[i] = list(set(l))
#print(sq,cq)
ansl = []
anss = []
for j in range(q):
    k,a,b = input().split()
    if k =='1':
        i = int(a)
        p,r = (i - 1) // w, (i - 1) % w
        if sq[p][r] != b:
            sq[p][r] = b
            cq[p] = list(set(sq[p]))
        #print(*sq)
        #print(cq)
    else:
        a,b = int(a),int(b)
        ap,ar = (a - 1) // w, (a - 1) % w
        bp,br = (b - 1) // w, (b - 1) % w
        ans = 0
        l = []
        if bp - ap >= 2:
            for i in range(ap,bp+1):
                l.extend(cq[i])
            l.extend(sq[ap][ar:])
            l.extend(sq[bp][:br+1])
            ansl.append(len(set(l)))
        elif bp - ap == 1:
            l.extend(sq[ap][ar:])
            l.extend(sq[bp][:br+1])
            ansl.append(len(set(l)))
        else:
            l.extend(sq[ap][ar:br+1])
            ansl.append(len(set(l)))
        anss.append(l)

for i in range(len(ansl)):
    print(ansl[i])

#print(sq)
#print(cq)

Submission status: Wrong Answer

Solution code:
def main():
  n=int(input())
  s=list(input())
  q_=int(input())
  q=[input().split() for _ in range(q_)]
  """
  n=500000
  s=list('abcdfghijk'*(n//10))
  q_=2000
  q=[]
  n2a = lambda c: chr(c%26+1+64).lower()
  for i in range(q_):
    if i%2==0:
      q.append(['1',str(i*11),n2a(i)])
    else:
      q.append(['2',str(i),str(i*11)])
  """
  import numpy as np
  a2n = lambda c: ord(c) - ord('a')
  d=[[0]*26]
  di=[0]*26
  for si in s:
    di[a2n(si)]+=1
    d.append(di.copy())
  d=np.array(d)
  for qi in q:
    if qi[0]=='1':
      if s[int(qi[1])-1]==qi[2]:
        pass
      else:
        d[int(qi[1]):,a2n(qi[2])]+=1
        d[int(qi[1]):,a2n(s[int(qi[1])-1])]-=1
    else:
      l,r=int(qi[1]),int(qi[2])
      ld=d[l-1]
      rd=d[r]
      print(len([i for i in range(26) if rd[i]-ld[i]>0]))

if __name__=='__main__':
  #import datetime
  #print(datetime.datetime.now())
  main()
  #print(datetime.datetime.now())