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:
import sys
# input = sys.stdin.buffer.readline
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getlist():
    return list(map(int, input().split()))
import math
import heapq
import bisect
from collections import defaultdict, Counter, deque
MOD = 10**9 + 7
INF = 10**21


class Segtree_op():
    def __init__(self, n):
        self.size = 1
        while (n >= 1):
            self.size = self.size << 1
            n = n // 2

        self.arr = [self.unit() for i in range(self.size * 2)]

    def op(self, lch, rch):
        # sum
        return lch + rch

        # update min with holding index
        # if lch[0] <= rch[0]:
        #     return lch
        # else:
        #     return rch

    def unit(self):
        return 0

    def update(self, k, val):
        k += self.size - 1
        self.arr[k] = val
        while (k):
            k = (k - 1) // 2
            self.arr[k] = self.op(self.arr[k * 2 + 1], self.arr[k * 2 + 2])

    def query(self, l, r):
        L = l + self.size
        R = r + self.size
        s = self.unit()
        while L < R:
            if R & 1:
                R -= 1
                s = self.op(s, self.arr[R - 1])

            if L & 1:
                s = self.op(s, self.arr[L - 1])
                L += 1
            L >>= 1
            R >>= 1
        return s

    # def show(self):
    #     idx = 1
    #     while (idx <= self.size):
    #         print(self.arr[idx - 1:idx * 2 - 1])
    #         idx *= 2


def main():
    n = getN()
    s = input().strip()
    q = getN()
    segs = [Segtree_op(n) for i in range(26)]
    for i, c in enumerate(s):
        segs[ord(c) - ord("a")].update(i, 1)

    for query in range(q):
        operand, a, b = input().split()
        if operand == "1":
            a = int(a) - 1
            segs[ord(s[a]) - ord("a")].update(a, 0)
            segs[ord(b) - ord("a")].update(a, 1)
        else:
            tmp = 0
            a, b = int(a) - 1, int(b) - 1
            for se in segs:
                # print(se.arr)
                if se.query(a, b+1) > 0:
                    tmp += 1
            print(tmp)

    # print(segs[0].arr)

if __name__ == '__main__':
    main()

"""
7 
aaaabbb
3
1 7 c
2 1 5
2 1 7

26 
abcdefghijklmnopqrstuvwxyz
11
2 1 26
2 2 26
2 5 5
2 11 20
2 25 26 
1 1 z
2 1 26
2 2 26
2 5 5
2 11 20
2 25 26 

"""

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

#################

#Binary Indexed Tree（１点加算）
#1-indexed
class BIT:
    """
    a[1]~a[n]の数列を想定
    """

    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def add(self, index, x):
        """
        a[index]にxを加算
        """
        while index <= self.size:
            self.tree[index] += x
            index += index & (-index)
 
    def sum(self, index):
        """
        a[1]~a[index]の和
        """
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s
 
    def search(self, value):
        """
        sum(index) >= value を満たす最小のindex
        sum(n) < value のとき n+1 を返す
        """
        i = 0
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.tree[i + step] < value:
                i += step
                s += self.tree[i]
            step >>= 1
        return i + 1

N = I()
S = list(str(input()))
Q = I()

def calc(c):
    return int(ord(c)-ord('a'))

cum = [BIT(N) for _ in range(26)]
for i in range(N):
    cum[calc(S[i])].add(i+1,1)

for i in range(Q):
    now = list(input().split())
    if now[0]=='1':
        iq = int(now[1])
        cq = str(now[2])
        cum[calc(S[iq-1])].add(iq,-1)
        cum[calc(cq)].add(iq,1)
    else:
        lq = int(now[1])
        rq = int(now[2])
        ans = 0
        for j in range(26):
            ans += cum[j].sum(rq)
            if lq-1 >= 0:
                ans -= cum[j].sum(lq-1)
        print(ans)

Submission status: Wrong Answer

Solution code:
import collections
def type2(s):
    return collections.Counter(s)

n = int(input())
S = input()
Q = int(input())
for _ in range(Q):
    a,b,c = input().split()
    a,b = int(a),int(b)
    if a==2:
        c = int(c)
        print(type2(S[b-1:c]))
    else:
        S = S[:b-1] + c + S[b:]

Submission status: Wrong Answer

Solution code:
from collections import Counter, defaultdict
N = int(input())
S = list(input())
Q = int(input())

l = 2**((N-1).bit_length())
data = [Counter([]) for i in range(2*l)]
for i in range(N):
    data[l+i][S[i]] = 1
for i in range(l-1,0,-1):
    data[i] = data[2*i] + data[2*i+1]

for cnt in range(Q):
    a,b,c = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        if S[b-1] == c:
            continue
        oldc = S[b-1]
        S[b-1] = c
        n = l + b - 1
        while n > 0:
            data[n][oldc] -= 1
            data[n][c] += 1
            n = n // 2
    else:
        c = int(c)
        i = b + l -1
        j = c + l
        #temp = Counter()
        temp = set([])
        while j-i > 0:
            if i & 1:
                #temp += data[i]
                temp = temp.union(data[i].keys())
                i += 1
            if j & 1:
                #temp += data[j-1]
                temp = temp.union(data[j-1].keys())
                j -= 1
            i //= 2
            j //= 2
        print(len(temp))

Submission status: Wrong Answer

Solution code:
from collections import Counter

class Bit:
    def __init__(self, n,ls):
        self.size=n
        self.tree=[Counter() for _ in range(n+1)]
        self.ls=['']*(n+1)

    def sum(self, i, j):
        i-=1
        res=Counter()
        while j>0:
            res += self.tree[j]
            j -= j&-j
        while i>0:
            res -= self.tree[i]
            i -= i&-i
        return len(res)
    
    def add(self, i, x):
        self.ls[i] = x
        while i <= self.size:
            self.tree[i][x]+=1
            i += i & -i

    def change(self, i, x):
        original = self.ls[i]
        self.ls[i]=x
        while i <= self.size:
            self.tree[i] += Counter({original:-1, x:1})
            i += i & -i
        

n = int(input())
s = list(input())
bit=Bit(n,s)

for i in range(n):
    bit.add(i+1, s[i])

q = int(input())
for _ in range(q):
    query, a, b = input().split()
    if query=='1':
        bit.change(int(a),b)
    else:
        print(bit.sum(int(a), int(b)))

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def LS(): return input().split()
def S(): return list(input().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n = II()
    s = S()
    sqrtn = int(sqrt(n))
    sq = [defaultdict(int)  for i in range(n // int(sqrtn) + 1)]
    lis = [0] * n
    for i in range(n):
        lis[i] = ord(s[i])-ord("a")
        sq[i // sqrtn][ord(s[i]) - ord("a")] += 1
    # print(lis,sq)
    for _ in range(II()):
        t, i, c = LS()
        i = int(i) - 1
        if t == "1":
            sq[i//sqrtn][lis[i]] -= 1
            lis[i] = ord(c) - ord("a")
            sq[i // sqrtn][ord(c) - ord("a")] += 1
        else:
            res = 0
            c = int(c) - 1
            ix = i // sqrtn
            cx = c // sqrtn
            for x in range((c - i - 2) // sqrtn):
                for key, value in sq[x + ix + 1].items():
                    if value:
                        res |= 1 << key
            if (c - i - 2) // sqrtn > 0:
                for x in range(c, (ix + 1) * sqrtn):
                    res |= 1 << lis[x]
                for x in range(cx * sqrtn, c + 1):
                    res |= 1 << lis[x]
            else:
                for x in range(i, c + 1):
                    res |= 1 << lis[x]
            ans = 0
            # print(bin(res))
            while res:
                ans += res & 1
                res >>= 1
            print(ans)
        # print(sq, lis)
        


    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
import string


def resolve():
    N = int(input())
    S = input()
    Q = int(input())
    rq = []
    for _ in range(Q):
        a, x, y = input().split()
        if a == '1':
            rq.append((int(x), y))
        if a == '2':
            l, r = int(x), int(y)
            subs = S[l-1:r]
            flag = {s: False for s in string.ascii_lowercase}
            for s in subs:
                flag[s] = True
            ans = 0
            for s in flag:
                if flag[s]:
                    ans += 1
            for (i, c) in rq:
                if i < l-1 or r-1 < i:
                    continue
                if not flag[c]:
                    flag[c] = True
                    ans += 1
            print(ans)


if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
Q = int(input())
QL = [list(input().split()) for _ in range(Q)]

c = {}

for ql in QL:
    if ql[0] == '1':
        c[ql[1]] = ql[2]
    else:
        l = int(ql[1])
        r = int(ql[2])
        s = S[l-1:r]
        del_l = []
        for j in c:
            t = int(j)-l
            if 0 <= t <= r:
                s = s[:t] + c[j] + s[t+1:]
        print(len(''.join(set(s))))

        S = S[:l-1] + s + S[r:]

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
N=int(input())
S=input()
Q=int(input())

d={}
A=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
for i in range(26):
    d[A[i]]=i

D={}
for i in range(26):
    D[i]=[-1]

for i in range(N):
    D[d[S[i]]].append(i)
for i in range(26):
    D[d[A[i]]].append(10**9)
#print(D)

import bisect

for i in range(Q):
    a,b,c=list(input().split())
    if a=="2":
        cnt=0
        for j in range(26):
            if bisect.bisect_right(D[j],int(c)-1) - bisect.bisect_left(D[j],int(b)-1)>0:
                cnt+=1
        print(cnt)
    else:
        D[d[c]].append(int(b)-1)
        D[d[c]].sort()

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import bisect

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

dictList=[defaultdict(int) for _ in range(n+1)]

for i in range(n):
    dictList[i+1]=dictList[i].copy()
    dictList[i+1][s[i]]+=1

ans_list=[]
change={}

#print(dictList)

for g in range(q):
    a,b,c=map(str,input().split())
    a=int(a)
    b=int(b)
    if a==1:
        if s[b-1]!=c:
            change[b]=[s[b-1],c] #[before,after]
    else:
        ans=0
        c=int(c)
        Judge = defaultdict(int)
        lDict = dictList[b-1].copy()
        rDict = dictList[c].copy()
        #print(lDict,rDict)
        for i,m in lDict.items():
            Judge[i]-=m
        for i,m in rDict.items():
            Judge[i]+=m
        for i,m in change.items():
            if b<=i and i<=c:
                Judge[m[0]]-=1
                Judge[m[1]]+=1
        #print(Judge)
        for i,m in Judge.items():
            if m>0:
                ans+=1
        ans_list.append(ans)

#print(change)
for i in range(len(ans_list)):
    print(ans_list[i])

Submission status: Wrong Answer

Solution code:
def solve():
    N = int(input())
    S = input()
    Q = int(input())
    
    st = list(S)
    
    for _ in range(Q):
        a, b, c = input().split()
        if a == '2':
            b = int(b)
            c = int(c)
            z = st[b-1:c]
            l = len(set(list(z)))
            print(l)
        else:
            b = int(b) -1
            st[b] = c

print(solve())

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
Q = int(input())
import numpy as np
lis = np.array([[0]*26 for _ in range(N+1)])
for i,s in enumerate(S):
  k = ord(s)-97
  lis[i+1:,k]+=1
  
for _ in range(Q):
  a,b,c = input().split()
  a = int(a)
  b = int(b)
  if a==1:
    x = S[b-1]
    x = ord(x)-97
    y = ord(c)-97
    if x!=y:
      for i in range(b,N+1):
        lis[i:,x]-=1
        lis[i:,y]+=1
  elif a==2:
    c = int(c)
    print(sum((lis[c]-lis[b-1])>0))

Submission status: Wrong Answer

Solution code:
N=int(input())
S=input()
Q=int(input())
query=[input().split() for _ in range(Q)]
s=[0 for _ in range(N+1)]
dp=[[0 for _ in range(26)] for _ in range(N+1)]
for i in range(1, N+1):
    c=S[i-1]
    for j in range(26):
        dp[i][j]=dp[i-1][j]
    dp[i][ord(c)-ord("a")]+=1
for q in query:
    if q[0]=="1":
        i, c = int(q[1]), q[2]
        for i_ in range(i, N+1):
            dp[i_][ord(c)-ord("a")]+=1
            dp[i_][ord(S[i-1])-ord("a")]-=1
    else:
        l, r = map(int, q[1:3])
        ans=0
        for j in range(26):
            if dp[r][j]-dp[l-1][j]>0:
                ans+=1
        print(ans)

Submission status: Wrong Answer

Solution code:
from collections import Counter

class Bit:
    def __init__(self, n,ls):
        self.size=n
        self.tree=[Counter() for _ in range(n+1)]
        self.ls=['']*(n+1)

    def sum(self, i, j):
        i-=1
        res=Counter()
        while j>0:
            res += self.tree[j]
            j -= j&-j
        while i>0:
            res -= self.tree[i]
            i -= i&-i
        return len(res)
    
    def add(self, i, x):
        self.ls[i] = x
        while i <= self.size:
            self.tree[i][x]+=1
            i += i & -i

    def change(self, i, x):
        original,self.ls[i] = self.ls[i],x
        while i <= self.size:
            self.tree[i] += Counter(original=-1, x=1)
            i += i & -i
        

n = int(input())
s = list(input())
bit=Bit(n,s)

for i in range(n):
    bit.add(i+1, s[i])

q = int(input())
for _ in range(q):
    query, a, b = input().split()
    if query=='1':
        bit.change(int(a),b)
    else:
        print(bit.sum(int(a), int(b)))

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']
Yn=['Yes','No']
 
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
#ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value
# Bit.l_bound(w)  : get lower bound of index where w can be inserted

class Bit:
    def __init__(self,n):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        
    def __str__(self):
        a=[self.sum(i+1)-self.sum(i) for i in range(self.size)]
        return str(a)
        
    def add(self,i,x):
        k=0
        while i<=self.size:
            k+=1
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
class Bit0(Bit):
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

class Multiset(Bit0):
    def __init__(self,max_v):
        super().__init__(max_v)
    def insert(self,x):
        super().add(x,1)
    def find(self,x):
        return super().l_bound(super().sum(x))
    def __str__(self):
        return str(self.arr)


show_flg=False
show_flg=True


n=I()
s=StoI()
q=I()

bt=[Bit0(n) for i in range(26)]


for i in range(n):
    bt[s[i]].add(i,1)

for _ in range(q):
    t,a,b=input().split()
    if t=='1':
        i,c=int(a)-1,ord(b)-97
        old=s[i]
        s[i]=c
        bt[c].add(i,1)
        bt[old].add(i,-1)
    else:
        l,r=int(a)-1,int(b)-1
        ans=0
        for i in range(26):
            if bt[i].sum(r+1)-bt[i].sum(l)>0:
                ans+=1
        print(ans)    


for i in bt:
    show(i)        
    

#print((5*10**5//13)**0.5)

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy

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

a = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t',
     'u','v','w','x','y','z']
md = {a[i]:i for i in range(26)}
cuma = [0]*26
cums = [[0]*26 for i in range(n+1)]

for i in range(len(s)):
  cuma[md[s[i]]] += 1
  cums[i+1] = copy.copy(cuma)

cums = np.array(cums)

for i in range(q):
  a, b, c = input().split()
  if int(a)==1:
    b = int(b)
    if c!=s[b-1]:
      cums[b:,md[s[b-1]]] -= 1
      cums[b:,md[c]] += 1
  elif int(a)==2:
    b = int(b)
    c = int(c)
    sub = np.array(cums[c]) - np.array(cums[b-1])
    sub = np.where(sub>0, 1, 0)
    print(sum(sub))

Submission status: Wrong Answer

Solution code:
N = int(input())
S = input()
Q = int(input())
import numpy as np
lis = np.array([[0]*26 for _ in range(N+1)])
for i,s in enumerate(S):
  k = ord(s)-97
  lis[i+1:,k]+=1
  
for _ in range(Q):
  a,b,c = input().split()
  a = int(a)
  b = int(b)
  if a==1:
    x = S[b-1]
    x = ord(x)-97
    y = ord(c)-97
    if x!=y:
      for i in range(b,N+1):
        lis[i][x]-=1
        lis[i][y]+=1
  elif a==2:
    c = int(c)
    ans = 0
    for i,j in zip(lis[b-1],lis[c]):
      if j-i>0:
        ans+=1
    print(ans)

Submission status: Wrong Answer

Solution code:
from heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from functools import *
from itertools import permutations,combinations,groupby
import sys
import bisect
import string
import math
import time
import random
def Golf():
    *a,=map(int,open(0))
def S_():
    return input()
def IS():
    return input().split()
def LS():
    return [i for i in input().split()]
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def NI(n):
    return [int(input()) for i in range(n)]
def NI_(n):
    return [int(input())-1 for i in range(n)]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join([chr(i+97) for i in ls])
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def GGI(h,w,search=None,replacement_of_found='.',mp_def={'#':1,'.':0}):
#h,w,g,sg=GGI(h,w,search=['S','G'],replacement_of_found='.',mp_def={'#':1,'.':0}) # sample usage
    mp=[1]*(w+2)
    found={}
    for i in range(h):
        s=input()
        for char in search:
            if char in s:
                found[char]=((i+1)*(w+2)+s.index(char)+1)
                mp_def[char]=mp_def[replacement_of_found]
        mp+=[1]+[mp_def[j] for j in s]+[1]
    mp+=[1]*(w+2)
    return h+2,w+2,mp,found
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['YES','NO']
Yn=['Yes','No']
 
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
#ts=time.time()
#sys.setrecursionlimit(10**7)
input=lambda: sys.stdin.readline().rstrip()
 
def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

# Binary Indexed Tree
# Bit.add(i,x)    : add x at i-th value
# Bit.sum(i)      : get sum up to i-th value
# Bit.l_bound(w)  : get lower bound of index where w can be inserted

class Bit:
    def __init__(self,n):
        self.size=n
        self.m=len(bin(self.size))-2
        self.arr=[0]*(2**self.m+1)
        
    def __str__(self):
        a=[self.sum(i+1)-self.sum(i) for i in range(self.size)]
        return str(a)
        
    def add(self,i,x):
        k=0
        while i<=self.size:
            k+=1
            self.arr[i]+=x
            i+=i&(-i)
        return
    
    def sum(self,i):
        rt=0
        while i>0:
            rt+=self.arr[i]
            i-=i&(-i)
        return rt
    
    def l_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
    def u_bound(self,w):
        if w<=0:
            return 0
        x=0
        k=2**self.m
        while k>0:
            if x+k<self.size and self.arr[x+k]<=w:
                w-=self.arr[x+k]
                x+=k
            k//=2
        return x+1
        
class Bit0(Bit):
    def add(self,j,x):
        super().add(j+1,x)
    def l_bound(self,w):
        return max(super().l_bound(w)-1,0)
    def u_bound(self,w):
        return max(super().u_bound(w)-1,0)

class Multiset(Bit0):
    def __init__(self,max_v):
        super().__init__(max_v)
    def insert(self,x):
        super().add(x,1)
    def find(self,x):
        return super().l_bound(super().sum(x))
    def __str__(self):
        return str(self.arr)


show_flg=False
show_flg=True


n=I()
s=StoI()
q=I()

bt=[Bit0(n) for i in range(26)]


for i in range(n):
    bt[s[i]].add(i,1)

for _ in range(q):
    t,a,b=input().split()
    if t=='1':
        i,c=int(a)-1,ord(b)-97
        old=s[i]
        bt[c].add(i,1)
        bt[old].add(i,-1)
    else:
        l,r=int(a)-1,int(b)-1
        ans=0
        for i in range(26):
            if bt[i].sum(r+1)-bt[i].sum(l)>0:
                ans+=1
        print(ans)

Submission status: Wrong Answer

Solution code:


class segtree:

    def __init__(self, n,operator,identity):
        nb = bin(n)[2:]
        bc = sum([int(digit) for digit in nb])
        if bc == 1:
            self.num_end_leaves = 2**(len(nb)-1)
        else:
            self.num_end_leaves = 2**(len(nb))

        self.array = [identity for i in range(self.num_end_leaves * 2)]
        self.identity = identity
        self.operator =operator

    def update(self,x,val):
        actual_x = x+self.num_end_leaves
        self.array[actual_x] = val
        while actual_x > 0 :
            actual_x = actual_x//2
            self.array[actual_x] = self.operator(self.array[actual_x*2],self.array[actual_x*2+1])

    def get(self,q_left,q_right,arr_ind=1,leaf_left=0,depth=0):
        width_of_floor = self.num_end_leaves//(2**depth)
        leaf_right = leaf_left+width_of_floor-1

        if leaf_left > q_right or leaf_right < q_left:
            return  self.identity

        elif leaf_left >= q_left and leaf_right <= q_right:
            return self.array[arr_ind]

        else:
            val_l = self.get(q_left,q_right,2*arr_ind,leaf_left,depth+1)
            val_r = self.get(q_left,q_right,2*arr_ind+1,leaf_left+width_of_floor//2,depth+1)
            return self.operator(val_l,val_r)



N=int(input())
S=[i for i in input()]
Q=int(input())

s_tree = segtree(N,(lambda x,y:set(list(x)+list(y))),set([])) 
for i in range(N):
    s_tree.update(i, set([S[i]]))



for _ in range(Q):
    f, a, b =(i for i in input().split())
    if int(f)==1:
        s_tree.update(int(a)-1,set([b]))
    else:
        print(len(s_tree.get(int(a)-1, int(b))))

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
class BIT(): #1-indexed
    def __init__(self,n): #n: 要素数
        self.size=n
        self.bit=[0]*(n+1)
    def add(self,i,x): #i番目(1-indexed)にxを加算
        while i<=self.size:
            self.bit[i]+=x
            i+=i&-i
    def sum_1_to_i(self,i): #1番目からi番目(含む)までの総和(1-indexed)
        s=0
        while i>0:
            s+=self.bit[i]
            i-=i&-i
        return s
    def sum_i_to_j(self,i,j): #i番目からj番目(含む)までの総和(1-indexed)
        return self.sum_1_to_i(j)-self.sum_1_to_i(i-1)
    def reset(self): #初期化
        self.bit=[0]*(self.size+1)

def main():
    A='abcdefghijklmnopqrstuvwxyz'
    D=dict()
    for i,a in enumerate(A):
        D[a]=i
    n=int(input())
    S=input().strip()
    L=[BIT(n) for _ in range(26)]
    for i,s in enumerate(S):
        k=D[s]
        L[k].add(i+1,1)
    q=int(input())
    for _ in range(q):
        k,a,b=input().strip().split()
        if k=='1':
            i=int(a)-1
            s=S[i]
            l1=D[s]
            l2=D[b]
            L[l2].add(i+1,1)
            L[l1].add(i+1,-1)
        else:
            l=int(a)
            r=int(b)
            ans=0
            for i in range(26):
                if L[i].sum_i_to_j(l,r)!=0:
                    ans+=1
            print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import collections

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

answer = []


for i in range(Q):
    
    q, i, x = input().split()
    
    if (q == '1'):
        tmp = int(i) - 1
        S[tmp] = x
        
    
    else:
        l = int(i) - 1
        r = int(x)
        string = S[l - 1 : r]
    
        CTR = collections.Counter(string).most_common()
        ans = len(CTR)

        answer.append(ans)


for i in answer:
    print(i)