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

Solution code:
class BIT:
    def __init__(self, n):
        """
            data : BIT木データ
            el : 元配列
        """
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    
    """A1 ~ Aiまでの累積和"""
    def Sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & (-i)   #LSB(Least Significant Bit)の獲得:i&(-i)
        return s
    
    """Ai += x"""
    def Add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    
    """Ai ~ Ajまでの累積和"""
    def Get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.Sum(j) - self.Sum(i)

def ctoi(c):
    return ord(c) - 97

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

bits = [BIT(n) for _ in range(26)]
ans = []
for i in range(n):
    bits[ctoi(s[i])].Add(i+1, 1)
for _ in range(q):
    line = list(input().split())
    if line[0] == '1':
        idx = int(line[1])
        bits[ctoi(s[idx-1])].Add(idx, -1)
        bits[ctoi(line[2])].Add(idx, 1) 
    else:
        l,r = int(line[1]), int(line[2])
        cnt = 0
        for i in range(26):
            if bits[i].Get(l-1,r)!=0:
                cnt += 1
        ans.append(cnt)
for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:
from string import ascii_lowercase

def ctoi(c):
    return ord(c)-97

class BIT:
    def __init__(self, n):
        """
            data : BIT木データ
            el : 元配列
        """
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)    
    """A1 ~ Aiまでの累積和"""
    def Sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & (-i)   #LSB(Least Significant Bit)の獲得:i&(-i)
        return s    
    """Ai += x"""
    def Add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i    
    """Ai ~ Ajまでの累積和"""
    def Get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.Sum(j) - self.Sum(i)

n = int(input())
s = input()
q = int(input())
bits = []
res = []
for char in ascii_lowercase:
    A = [0]*n
    for i in range(n):
        if s[i]==char:
            A[i] = 1
    bit = BIT(n)
    for i, a in enumerate(A):
        bit.Add(i+1, a)
    bits.append(bit)
for query in range(q):
    line = list(input().split())    
    if line[0]=='1':
        idx = int(line[1])
        bits[ctoi(s[idx-1])].Add(idx, -1)
        bits[ctoi(line[2])].Add(idx, 1)
    else:
        l,r = int(line[1]), int(line[2])
        cnt = 0
        for i in range(26):
            if bits[i].Get(l-1,r)!=0:
                cnt += 1
        res.append(cnt)
for r in res:
    print(r)

Submission status: Wrong Answer

Solution code:
import collections

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

Submission status: Wrong Answer

Solution code:
N=int(input())
S=list(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: Wrong Answer

Solution code:
#import math
import time
#from collections import deque
from collections import defaultdict
from copy import deepcopy
#import heapq
import cProfile
import pstats

Test = False
if Test:
    import random
    import string



mod = 10 ** 9 + 7
t = time.time()

def randomname(n):
   randlst = [random.choice(string.ascii_letters) for i in range(n)]
   return ''.join(randlst).lower()

def iip():
    ret = [int(i) for i in input().split()]
    if len(ret) == 1:
        return ret[0]
    return ret

def main():
    if Test:
        S = randomname(10**5)
        N = len(S)
        Q = 10000
    else:
        N = iip()
        S = input()
        Q = iip()
    rw = ruisekiwa(S, N)
    query_list = []
    #print(ruisekiwa(S, N))

    for i in range(Q):
        if Test:
            query_list.append(" ".join(("1", str(random.randint(0, 10 ** 5)), randomname(1))))
            query_list.append(" ".join(("2", str(random.randint(0, 10 ** 4)), str(random.randint(10 ** 4 + 1, 10 ** 5)))))
        else:
            query_list.append(input())


    changelist = []
    changedict = {}
    outlist = []
    t = time.time()
    for k, query in enumerate(query_list):

        if k % 1000 == 0:
            if Test:
                print(k)
            #print(time.time()-t)
            #t = time.time()

        if query[0] == "1":
            position = int(query[2:-2])
            char = query[-1]
            changedict[position] = char
            changelist.append(position)

        if query[0] == "2":
            query = query.split(" ")
            left = int(query[1])-1
            right = int(query[2])-1

            if left == 0:
                leftitem = defaultdict(int)
            else:
                leftitem = rw[left-1]

            item = defaultdict(int)
            for char, value in  rw[right].items():
                item[char] = value - leftitem[char]

            for position in changelist:
                if left <= position and position <= right:
                    value = changedict[position]
                    item[value] += 1
                    item[S[position]] -=1

            result = 0
            for value in item.values():
                if value>=1:
                    result += 1
            outlist.append(str(result))
    print("\n".join(outlist))

            #print(item)


def ruisekiwa(S, N):
    ret = []
    inner = defaultdict(int)
    for i in range(N):
        inner[S[i]] += 1
        ret.append(inner.copy())
    return ret


#main()
#pr = cProfile.Profile()
#pr.enable()
main()
#pr.disable()
#pr.print_stats(sort="cumtime")
#cProfile.run("main()", filename="test.prof")

Submission status: Wrong Answer

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]
        dic = {c:li for c, li in dic.items() if len(li)>0}
    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: Wrong Answer

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]
        dic = {c:li for c, li in dic.items() if li}
    else:
        b = int(b)-1
        tmp = 0
        for li in dic.values():
            if min(li)<=b and max(li)>=a:
                tmp += 1
        print(tmp)

Submission status: Wrong Answer

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]
        dic = {x:y for x, y in dic.items() if y}
    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: Wrong Answer

Solution code:
import bisect
from collections import defaultdict

N = int(input())
S = list(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)
            S[m] = n
    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: Wrong Answer

Solution code:
def insert_pos(c, n):
    for i in range(len(pos[c])):
        if n > pos[c][i]:
            pos[c].insert(i+1, n)
            return
    pos[c].insert(0, n)
    
def search_pos(l, r):
    cnt = 0
    for i in range(26):
        for j in pos[i]:
            if j >= l:
                if j <= r:
                    cnt += 1
                break
    return cnt

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

pos = [[] for i in range(26)]
alp = "abcdefghijklmnopqrstuvwxyz"
atoi = {}
for i in range(26):
    atoi[alp[i]] = i
for i in range(n):
    pos[atoi[s[i]]].append(i)

for i in range(q):
    a, b, c = input().split()
    if a == "1":
        b = int(b)-1
        pos[atoi[s[b]]].remove(b)
        insert_pos(atoi[c], b)
        s[b] = c
    else:
        b, c = int(b)-1, int(c)-1
        print(search_pos(b, c))

Submission status: Wrong Answer

Solution code:
# import bisect
from collections import Counter, deque
# import copy
# from heapq import heappush, heappop, heapify
# from fractions import gcd
import itertools
# from operator import attrgetter, itemgetter
# import math

import sys

# import numpy as np

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


class Node:

    def __init__(self, nid):
        self.node_id = nid
        self.color = -1
        self.next = []


def main():
    n = int(input())
    s = input()
    q = int(input())

    l = len(s)
    l_sqrt = int(l ** 0.5)

    s_str = list()
    s_set = list()
    i = 0

    while i < l:
        begin = i
        end = i + l_sqrt
        if end > l:
            end = l

        s_part = s[begin:end]
        s_str.append(s_part)
        s_set.append(set(s_part))
        i = end

    for i in range(q):
        a, b, c = input().split()
        a = int(a)

        if a == 1:
            b = int(b) - 1

            bidx = b // l_sqrt
            bpidx = b % l_sqrt

            before = s_str[bidx][bpidx]

            temp = list(s_str[bidx])
            temp[bpidx] = c
            s_str[bidx] = "".join(temp)
            s_set[bidx] = set(s_str[bidx])
        else:
            b = int(b) - 1
            c = int(c) - 1

            bidx = b // l_sqrt
            bpidx = b % l_sqrt
            cidx = c // l_sqrt
            cpidx = c % l_sqrt

            temp = set()

            if cidx - bidx > 0:
                for j in range(bidx + 1, cidx):
                    temp = temp.union(s_set[j])
                temp = temp.union(set(s_str[cidx][0:cpidx + 1]))
                temp = temp.union(set(s_str[bidx][bpidx:]))
            else:
                temp = s_str[bidx][bidx:cidx + 1]

            print(len(temp))


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
import sys

N=input()
S=raw_input()
Q=input()
query=[ sys.stdin.readline().split() for _ in range(Q) ]

#BIT
bit=[ [ 0 for _ in range(N+1) ] for _ in range(27) ]  #中も外も1-indexed bit[1]:aのbit, bit[2]:bのbit ...

def add(idx,a,w):
    while a<=N:
        bit[idx][a]+=w
        a+=a&-a

def sum(idx,a):
    ret=0
    while 0<a:
        ret+=bit[idx][a]
        a-=a&-a
    return ret

for i,x in enumerate(S):
    add(ord(x)-96,i+1,1)  #a~zのどのbit配列か,特定文字のbit配列の何番目,bitに代入する値

for q1,q2,q3 in query:
    q1=int(q1)
    q2=int(q2)
    if q1==1:
        q3=ord(q3)-96
        add(q3,q2,1)  #a~zのどのbit配列か,特定文字のbit配列の何番目,bitに代入する値
    elif q1==2:
        q3=int(q3)
        cnt=0
        for i in range(1,27):
            if 0<sum(i,q3)-sum(i,q2-1):
                cnt+=1
        print cnt

Submission status: Wrong Answer

Solution code:
#単位元を設定
ide = 0

class SegmentTree:
	def __init__(self,n):
		self.n = n
		tmp = 0
		while True:
			if 2 ** tmp >= self.n:
				break
			tmp += 1
		self.STtable = [ide] * (2*2**tmp)
		self.STtable_size = len(self.STtable)

	def update(self,i,a):
		i += self.STtable_size//2
		self.STtable[i] = a
		while i > 0:
			i //= 2
			self.STtable[i] = self.STtable[i*2] | self.STtable[i*2+1]

	def find(self,a,b,k,l,r):
		#[a,b)の最小を返す。
		#[l,r)からです。
		if a >= r or b <= l:
			return ide
		elif b <= (l+r)/2:
			return self.find(a,b,2*k,l,(l+r)/2)
		elif a >= (l+r)/2:
			return self.find(a,b,2*k+1,(l+r)/2,r)
		elif a == l and b == r:
			return self.STtable[k]
		else:
			v1 = self.find(a,(l+r)/2,2*k,l,(l+r)/2)
			v2 = self.find((l+r)/2,b,2*k+1,(l+r)/2,r)
			return v1 | v2

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

def CharTo2Base(c):
	return 1 << ord(c)-97

solve = SegmentTree(N)
for i in range(N):
	solve.update(i,CharTo2Base(S[i]))

#print(solve.STtable)
ans = []
Q = int(input())
for _ in range(Q):
	c,a,b = map(str,input().split())
	if c == '1':
		a = int(a)
		solve.update(a,CharTo2Base(b))
		#print(solve.STtable)
	else:
		a,b = int(a), int(b)
		a -= 1
		val = solve.find(a,b,1,0,solve.STtable_size//2)
		cnt = 0
		for i in range(26):
			if val >> i & 1 == 1:
				cnt += 1

		ans.append(cnt)

for a in ans:
	print(a)

Submission status: Wrong Answer

Solution code:
class SegmentTree(object):  # 1-indexed
    def __init__(self, size, S):
        self.len = 1 << size.bit_length()

        self.array = [0] * (2 * self.len)
        for i, s in enumerate(S):
            self.array[i + self.len] = 1 << (ord(s) - ord('a'))
        for i in range(self.len - 1, 0, -1):
            self.array[i] = self.array[i * 2] | self.array[i * 2 + 1]

    def query1(self, i, x):
        i += self.len
        self.array[i] = 1 << (ord(x) - ord('a'))
        i >>= 1
        while i > 0:
            self.array[i] = self.array[i * 2] | self.array[i * 2 + 1]
            i >>= 1

    def get(self, i):
        return self.array[i + self.len]

    def query(self, l, r, i, a, b):
        if l == a and r == b:
            return self.array[i]
        center = (a + b) // 2
        if center >= r:
            return self.query(l, r, i * 2, a, center)
        elif center <= l:
            return self.query(l, r, i * 2 + 1, center, b)
        else:
            return self.query(l, center, i * 2, a, center) | self.query(center, r, i * 2 + 1, center, b)

    def query2(self, l, r):
        ans = self.query(l - 1, r, 1, 0, self.len)
        print(bin(ans).count('1'))


N = int(input())
S = input()
tree = SegmentTree(N, S)
Q = int(input())

for _ in range(Q):
    a, b, c = map(str, input().split())
    if a == "1":
        b = int(b)
        tree.query1(b, c)
    else:
        b = int(b)
        c = int(c)
        tree.query2(b, c)

Submission status: Wrong Answer

Solution code:
class SegmentTree(object):  # 1-indexed
    def __init__(self, size, S):
        self.len = 1 << size.bit_length()

        self.array = [0] * (2 * self.len)
        for i, s in enumerate(S):
            self.array[i + self.len] = 1 << (ord(s) - ord('a'))
        for i in range(self.len - 1, 0, -1):
            self.array[i] = self.array[i * 2] | self.array[i * 2 + 1]

    def query1(self, i, x):
        i += self.len
        self.array[i] = 1 << (ord(x) - ord('a'))
        i >>= 1
        while i > 0:
            self.array[i] = self.array[i * 2] | self.array[i * 2 + 1]
            i >>= 1

    def get(self, i):
        return self.array[i + self.len]

    def count_letter(self, l, r, i, a, b):
        if l == a and r == b:
            return self.array[i]
        center = (a + b) // 2
        if center >= r:
            return self.count_letter(l, r, i * 2, a, center)
        elif center < l:
            return self.count_letter(l, r, i * 2 + 1, center + 1, b)
        else:
            left = self.count_letter(l, center, i * 2, a, center)
            right = self.count_letter(center + 1, r, i * 2 + 1, center + 1, b)
            return left | right

    def query2(self, l, r):
        ans = self.count_letter(l - 1, r - 1, 1, 0, self.len - 1)
        print(bin(ans).count('1'))


N = int(input())
S = input()
tree = SegmentTree(N, S)
Q = int(input())

for _ in range(Q):
    a, b, c = map(str, input().split())
    if a == "1":
        b = int(b)
        tree.query1(b, c)
    else:
        b = int(b)
        c = int(c)
        tree.query2(b, c)

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
s=[]
for c in S:
    s.append(c)
Q=int(input())
import bisect
d=[[] for i in range(26)]
for i in range(N):
    c=ord(s[i])-ord('a')
    bisect.insort(d[c],i)
for _ in range(Q):
    q=list(input().split())
    if int(q[0])==1:
        a=int(q[1])-1
        c=ord(q[2])-ord('a')
        if a in d[c]:
            continue
        else:
            e=ord(s[a])-ord('a')
            d[e].remove(a)
            bisect.insort_right(d[c], a)
            s[a]=q[2]
    elif int(q[0])==2:
        n=0
        a=int(q[1])-1
        b=int(q[2])-1
        for i in range(26):
            #print(a,b,i,d[i],bisect.bisect_right(d[i],a),bisect.bisect_right(d[i],b))
            if bisect.bisect_left(d[i],a)<len(d[i]) and bisect.bisect_right(d[i],b)>0:
                n+=1
        print(n)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():

    class BinaryIndexedTree():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        def add(self, item, pos):
            index = pos
            while index < self.n+1:
                self.bit[index] += item
                index += index & (-index)

        def sum(self, pos):
            ret = 0
            index = pos
            while index > 0:
                ret += self.bit[index]
                index -= index & -index
            return ret

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

    pos_bit_list = [BinaryIndexedTree(len(S)) for _ in range(26)]

    for i, c in enumerate(S):
        pos_bit_list[ord(c)-ord('a')].add(1, i+1)

    for q in Query:
        if q[0] == '1':
            pos_bit_list[ord(S[int(q[1])-1])-ord('a')].add(-1, int(q[1])+1)
            pos_bit_list[ord(q[2])-ord('a')].add(1, int(q[1])+1)
            S[int(q[1])-1] = q[2]
        else:
            print(len([p for p in pos_bit_list if p.sum(int(q[2])) - p.sum(int(q[1])-1) > 0]))

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():

    class BinaryIndexedTree():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        def add(self, item, pos):
            index = pos
            while index < self.n+1:
                self.bit[index] += item
                index += index & (-index)

        def sum(self, pos):
            ret = 0
            index = pos
            while index > 0:
                ret += self.bit[index]
                index -= index & -index
            return ret

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

    pos_bit_list = [BinaryIndexedTree(len(S)) for _ in range(26)]

    for i, c in enumerate(S):
        pos_bit_list[ord(c)-ord('a')].add(1, i+1)

    for q in Query:
        if q[0] == '1':
            pos_bit_list[ord(S[int(q[1])-1])-ord('a')].add(-1, int(q[1])+1)
            pos_bit_list[ord(q[2])-ord('a')].add(1, int(q[1])+1)
        else:
            print(len([p for p in pos_bit_list if p.sum(int(q[2])) - p.sum(int(q[1])-1) > 0]))

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():

    class BinaryIndexedTree():
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(n+1)

        def add(self, item, pos):
            index = pos
            while index < self.n+1:
                self.bit[index] += item
                index += index & (-index)

        def sum(self, pos):
            ret = 0
            index = pos
            while index > 0:
                ret += self.bit[index]
                index -= index & -index
            return ret

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

    pos_bit_list = [BinaryIndexedTree(len(S)) for _ in range(26)]

    for i, c in enumerate(S):
        pos_bit_list[ord(c)-ord('a')].add(1, i+1)

    for q in Query:
        if q[0] == '1':
            for p in pos_bit_list:
                p.add(0, int(q[1])+1)
            pos_bit_list[ord(q[2])-ord('a')].add(1, int(q[1])+1)
        else:
            print(len([p for p in pos_bit_list if p.sum(int(q[2])) - p.sum(int(q[1])-1) > 0]))

if __name__ == '__main__':
    resolve()

Submission status: Wrong Answer

Solution code:
class BinaryIndexTree:  # 1-indexed
    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


def Alp(s):
    return ord(s)-ord("a")


if __name__ == "__main__":
    N = int(input())
    S = list(input())
    Q = int(input())

    bit = [BinaryIndexTree(N) for _ in range(26)]
    for i, s in enumerate(S, start=1):
        bit[Alp(s)].add(i, 1)

    ans = []
    for _ in range(Q):
        q = input().split()
        if q[0] == "1":
            i = int(q[1]) - 1
            c = q[2]

            bit[Alp(c)].add(i+1, 1)
            bit[Alp(S[i])].add(i+1, -1)
        else:
            l = int(q[1])
            r = int(q[2])
            tmp = 0
            for i in range(26):
                b = bit[i]
                if b.sum(r) - b.sum(l - 1) > 0:
                    tmp += 1
            ans.append(tmp)

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

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
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
x = "abcdefghijklmnopqrstuvwxyz"
N, = map(int, input().split())
d = dict()
for c in x:
    d[c] = Bit(N+1)

S = input().strip()
for i, c in enumerate(S):
    d[c].add(i+1, 1)

Q = int(input())
for _ in range(Q):
    t, a, b = input().split()
    if t == '1':
        i, c = int(a), b
        b = S[i-1]
        d[b].add(i, -1)
        d[c].add(i, 1)
    else:
        l, r = int(a), int(b)
        rr = 0
        for c in x:
            if d[c].sum(r) - d[c].sum(l-1) > 0:
                rr += 1
        print(rr)

Submission status: Wrong Answer

Solution code:
import sys

stdin = sys.stdin

ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

class SegTree:
    def __init__(self, N):
        self.N = N
        self._N = 1<<((N-1).bit_length())
        self.node = [0]*2*self._N

    def build(self,lis):
        for i in range(self.N):
            self.node[i+self._N-1] = lis[i]
        for i in range(self._N-2,-1,-1):
            self.node[i] = self.node[i*2+1] | self.node[i*2+2]
        return

    def update(self,i,x):
        i += self._N-1
        self.node[i] = x
        while i:
            i >>= 1
            self.node[i] = self.node[i*2+1] | self.node[i*2+2]

    def query(self,p,q,idx=0,a=0,b=None):
        if b is None:
            b = self._N
        if q <= p or b <= p or q <= a:
            return 0
        elif p <= a and b <= q:
            return self.node[idx]
        else:
            res1 = self.query(p,q,idx*2+1,a,(a+b)//2)
            res2 = self.query(p,q,idx*2+2,(a+b)//2,b)
            return res1 | res2

n = ni()
oa = ord('a')
s = list(map(lambda x: 1<<(ord(x)-oa), list(input())))
q = ni()
S = SegTree(n)
S.build(s)
for _ in range(q):
    x,y,z = input().split()
    if x == '1':
        y = int(y)
        S.update(y-1, 1<<(ord(z)-oa))
    else:
        y = int(y)
        z = int(z)
        v = S.query(y-1,z)
        print(str(v).count('1'))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

count = np.zeros((26,(n+1)))

for i in range(26):
    s1 = chr(97+i)
    for j in range(n):
        if s[j] == s1:
            count[i][j+1] = count[i][j] + 1
        else:
            count[i][j+1] = count[i][j]

q = int(input())

for _ in range(q):
    li = list(input().split())
    if li[0] == '1':
        t1 = ord(li[2]) - 97
        t2 = ord(s[int(li[1])-1]) - 97
        li1 = int(li[1])
        if count[t1][li1] - count[t1][li1-1] == 1:
            pass
        else:
            count[t1][li1:] += 1
            count[t2][li1:] -= 1

    else:
        l = int(li[1])
        r = int(li[2])
        ans = 0

        for i in range(26):
            if count[i][r] - count[i][l-1] > 0:
                ans += 1

        print(ans)

Submission status: Wrong Answer

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


for i in range(int(q)):
  query = input().split(' ')
  a = int(query[1])
  b = query[2]
  
  if query[0] == '1':
    s = s[:(a-1)] + b + s[(a+1):]
    
  else:
    count = 0
    c = s[(a-1):(int(b))]
    while not c == '':
      c = c.strip(c[0])
      count += 1
    print(count, end=' ')