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:
#!/usr/bin/env python3

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

tmp = 'abcdefghijklmnopqrstuvwxyz'
n = I()
s = list(input())
cnt = [0]*n
alpha = defaultdict(list)
for i in range(n):
    alpha[s[i]].append(i)

q = I()
f = defaultdict(list)
for _ in range(q):
    num, i, c = input().split()
    if int(num) == 1:
        if s[int(i)-1] == c:
            continue
        f[s[int(i)-1]].append(int(i)-1)
        f[s[int(i)-1]].sort()
        alpha[c].append(int(i)-1)
        alpha[c].sort()
    else:
        cnt = 0
        for j in range(26):
            l = bl(alpha[tmp[j]],int(i)-1)
            r = br(alpha[tmp[j]],int(c)-1)
            L = bl(f[tmp[j]],int(i)-1)
            R = br(f[tmp[j]],int(c)-1)
            if r - l - (max(0,R - L -1)) > 0:
                cnt += 1
            #print(tmp[j],alpha[tmp[j]],f[tmp[j]],int(i),int(c),l,r,L,R)
        print(cnt)

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

tmp = 'abcdefghijklmnopqrstuvwxyz'
n = I()
s = list(input())
cnt = [0]*n
alpha = defaultdict(list)
for i in range(n):
    alpha[s[i]].append(i)

q = I()
f = defaultdict(list)
for _ in range(q):
    num, i, c = input().split()
    if int(num) == 1:
        if s[int(i)-1] == c:
            continue
        f[s[int(i)-1]].append(int(i)-1)
        f[s[int(i)-1]].sort()
        alpha[c].append(int(i)-1)
        alpha[c].sort()
    else:
        cnt = 0
        for j in range(26):
            l = bl(alpha[tmp[j]],int(i)-2)
            r = br(alpha[tmp[j]],int(c)-1)
            L = bl(f[tmp[j]],int(i)-2)
            R = br(f[tmp[j]],int(c)-1)
            if r - l - (R-L) > 0:
                cnt += 1
            #print(tmp[j],alpha[tmp[j]],f[tmp[j]],int(i),int(c),l,r,L,R)
        print(cnt)

Submission status: Wrong Answer

Solution code:
from collections import Counter

n = int(input())
s = input()
q = int(input())
Q = [list(map(str,input().split())) for _ in range(q)]

judge = 0
for x,y,z in Q:
    if int(x) == 1:
        judge = 0
        s = s[:int(y)-1]+z+s[int(y):]
    else:
        if judge == 0:
            judge = 1
            c = Counter(s[int(y)-1:int(z)])
            print(len(c.keys()))

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
import copy
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n=int(input())
s=input()
q=int(input())
query=[list(input().split()) for i in range(q)]


lst={}
for i in range(n):
    if not s[i] in lst:
        lst[s[i]]=[i]
    else:
        lst[s[i]].append(i)
erase={}
insert={}
# print(lst)
al=[chr(ord('a') + i) for i in range(26)]
for i in range(q):
    if query[i][0]=="1":
        one,j,c=query[i]
        j=int(j)
        if not s[j-1] in erase:
            erase[s[j-1]]=[j-1]
        else:
            erase[s[j-1]].append(j-1)
        erase[s[j-1]].sort()
        
        if not c in insert:
            insert[c]=[j-1]
        else:
            insert[c].append(j-1)
        insert[c].sort()

    else:
        two,l,r=query[i]
        ans=0
        l=int(l)
        r=int(r)
        for i in range(26):
            tmp=0
            if al[i] in lst:
                tmp+=bisect.bisect_right(lst[al[i]],r-1)-bisect.bisect_left(lst[al[i]],l-1)
            if al[i] in erase:
                tmp-=bisect.bisect_right(erase[al[i]],r-1)-bisect.bisect_left(erase[al[i]],l-1)
            if al[i] in insert:
                tmp+=bisect.bisect_right(insert[al[i]],r-1)-bisect.bisect_left(insert[al[i]],l-1)
            if tmp>0:
                ans+=1
        print(ans)
    # print(erase)
    # print(insert)

Submission status: Wrong Answer

Solution code:
import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def f(s):
    return ord(s)-97

def main():
    n = int(input())
    s = list(input())
    q = int(input())
    dp = [[0 for _ in range(26)] for _ in range(n+1)]
    for i in range(1,n+1):
        dp[i] = copy.copy(dp[i-1])
        dp[i][f(s[i-1])] += 1
    new = [[0 for _ in range(26)] for _ in range(n+1)]
    min_index = n 
    for _ in range(q):
        query = inpls()
        if query[0] == '1':
            index = int(query[1])-1
            if s[index] != query[2]:
                x,y = f(s[index]),f(query[2])
                dp[index+1][x] -= 1
                dp[index+1][y] += 1
                new[index][x] -= 1
                new[index][y] += 1
                min_index = min(min_index,index)
        else:
            l,r = int(query[1])-1,int(query[2])
            if r > min_index:
                for i in range(min_index+1,r):
                    for j in range(26):
                        dp[i+1][j] = dp[i+1][j] + new[i][j]
                        new[i+1][j] += new[i][j]
                        new[i][j] = 0
                min_index = r
            ans = 0
            for i in range(26):
                if dp[r][i]-dp[l][i]>0:
                    ans += 1
            print(ans)
            
if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from string import ascii_lowercase

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():
    n=int(input())
    S=input().strip()
    L=[BIT(n) for _ in range(26)]
    for i,s in enumerate(S):
        L[ord(s)-97].add(i+1,1)
    q=int(input())
    for _ in range(q):
        k,a,b=input().split()
        if k=='1':
            i=int(a)-1
            s=S[i]
            L[ord(b)-97].add(i+1,1)
            L[ord(s)-97].add(i+1,-1)
        else:
            l=int(a); r=int(b)
            ans=0
            for i in range(26):
                ans+=L[i].sum_i_to_j(l,r)>0
            print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

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



def main():

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

    #print(query)

    query2 = []
    
    for q in query:
        q = q.split()
        #print(q)
        if q[0] == "1":
            q2 = [int(i) for i in q[:2]]
            q2.append(q[2])
        else:
            q2 = [int(i) for i in q]
        query2.append(q2)

    Scp = S[:]

    for r in query2:
        #print(r)
        if r[0] == 1:
            if S[r[1]- 1] != r[2]:
                Scp = Scp[:r[1]] + r[2] + Scp[r[1]+1:]
        else:
            Slist = set(list(Scp[(r[1]-1) : r[2]]))
            print(len(Slist))

    

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations,accumulate,combinations,product
from fractions import gcd
import copy
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
mod=pow(10,9)+7

n=int(input())
s=input()
q=int(input())
query=[list(input().split()) for i in range(q)]


lst={}
for i in range(n):
    if not s[i] in lst:
        lst[s[i]]=[i]
    else:
        lst[s[i]].append(i)
erase={}
insert={}
# print(lst)
al=[chr(ord('a') + i) for i in range(26)]
for i in range(q):
    if query[i][0]=="1":
        one,j,c=query[i]
        j=int(j)
        if not s[j-1] in erase:
            erase[s[j-1]]=[j-1]
        else:
            erase[s[j-1]].append(j-1)
        
        if not c in insert:
            insert[c]=[j-1]
        else:
            insert[c].append(j-1)

    else:
        two,l,r=query[i]
        ans=0
        l=int(l)
        r=int(r)
        for i in range(26):
            tmp=0
            if al[i] in lst:
                tmp+=bisect.bisect_right(lst[al[i]],r-1)-bisect.bisect_left(lst[al[i]],l-1)
            if al[i] in erase:
                tmp-=bisect.bisect_right(erase[al[i]],r-1)-bisect.bisect_left(erase[al[i]],l-1)
            if al[i] in insert:
                tmp+=bisect.bisect_right(insert[al[i]],r-1)-bisect.bisect_left(insert[al[i]],l-1)
            if tmp>0:
                ans+=1
        print(ans)
    # print(erase)
    # print(insert)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from string import ascii_lowercase

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=ascii_lowercase
    D=dict()
    for i,a in enumerate(A):
        D[a]=i
    n=int(input())
    S=input().strip()
    L=[BIT(n+1) 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().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):
                ans+=L[i].sum_i_to_j(l,r)>0
            print(ans)
    
if __name__=='__main__':
    main()

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')


class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self.bit = [0 for _ in range(size)]
        self.size = size

    def add(self, i, w):
        """
        i番目にwを加える
        :param int i:
        :param int w:
        :return:
        """
        x = i + 1
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        """
        [0,i]の合計
        :param int i:
        :return:
        """
        res = 0
        x = i + 1
        while x > 0:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def search(self, x):
        """
        二分探索。和がx以上となる最小のインデックス(>= 1)を返す
        :param int x:
        :return :
        """
        i = 1
        s = 0
        step = 1 << (self.size.bit_length() - 1)
        while step:
            if i + step <= self.size and s + self.bit[i + step - 1] < x:
                i += step
                s += self.bit[i - 1]
            step >>= 1
        return i

    def __len__(self):
        return self.size

#solve
def solve():
    n = II()
    s = S()
    q = II()
    ans = [BinaryIndexedTree(n + 1) for i in range(27)]
    lis = [ord(si) - ord("a") for si in s]
    for i in range(n):
        ans[lis[i]].add(i+1, 1)
    for _ in range(q):
        t, i, c = LS()
        i = int(i)
        if t == "1":
            ans[lis[i-1]].add(i, -1)
            ans[ord(c) - ord("a")].add(i, 1)
        else:
            l = i - 1
            r = int(c)
            res = 0
            for i in range(27):
                res += ans[i].sum(r) - ans[i].sum(l) > 0
            print(res)
    


    return


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

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Fri Jan 24 14:37:00 2020

@author: matsui
"""

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

L=0
query=[]
for i in range(Q):
    q=input().split()
    L+=int(q[0])
    query.append(q)


abc=[chr(i) for i in range(97,123) ]

if L<N*1.5:
    for i in range(Q):
        #q=input().split()
        q=query[i]
        if int(q[0])==1:
            S=S[:int(q[1])-1]+q[2]+S[int(q[1]):]
            #print(S)
        if int(q[0])==2:
            txt=S[int(q[1])-1:int(q[2])]
            dp=[0]*26
            for s in txt:
                index=abc.index(s)
                dp[index]+=1
            ans=0
            for a in dp:
                if a!=0: ans+=1
            #print(dp)
            print(ans)


else:
    import numpy as np
    dp=np.zeros([N+1,26])

    for i in range(1,N+1):
        index=abc.index(S[i-1])
        dp[i,:]=dp[i-1,:]
        dp[i,index]+=1

    for i in range(Q):
        #q=input().split()
        q=query[i]
        if int(q[0])==1:
            if S[int(q[1])-1] != q[2]:
                index1=abc.index(S[int(q[1])-1])
                index2=abc.index(q[2])
                for j in range(int(q[1]),N+1): 
                    dp[j,index1]-=1
                    dp[j,index2]+=1

        if int(q[0])==2:
            res=dp[int(q[2]),:]-dp[int(q[1])-1,:]
            ans=0
            for a in res:
                if a!=0: ans+=1
            print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from string import ascii_lowercase

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=ascii_lowercase
    D=dict()
    for i,a in enumerate(A):
        D[a]=i
    n=int(input())
    S=list(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().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):
                ans+=L[i].sum_i_to_j(l,r)>0
            print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from string import ascii_lowercase

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=ascii_lowercase
    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().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):
                ans+=L[i].sum_i_to_j(l,r)>0
            print(ans)
    
if __name__=='__main__':
    main()

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()

    # SegTreeをa-zぶん用意する 3文字目がbならsegs[b]の3番目にフラグ1が立つ
    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":
            # 0-indexed
            a = int(a) - 1
            segs[ord(s[a]) - ord("a")].update(a, 0)
            segs[ord(b) - ord("a")].update(a, 1)

        else:  # operand == "2"
            tmp = 0
            # 0-indexed
            a, b = int(a) - 1, int(b) - 1
            for se in segs:
                # a-zそれぞれのSegTreeについて、区間内にフラグが立っていれば tmp += 1
                # 文字自体ではなくその間にindexが降られているので、右側を+1
                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
>> 2
>> 3


26 
abcdefghijklmnopqrstuvwxyz
7
2 1 26
2 2 26
2 5 5
2 11 20
2 25 26 
1 1 z
2 1 26
>> 26
>> 25
>> 1
>> 10
>> 2
>> 25
"""

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):
                ans+=L[i].sum_i_to_j(l,r)>0
            print(ans)
    
if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N = int(input())
S = list(input())
Q = int(input())
for i in range(Q):
    a, b, c = input().split()
    a = int(a)
    b = int(b)
    if a == 1:
        S[b-1] = c
    elif int(c) == len(S):
        print(len(set(S[b-1:])))
    elif b == int(c):
        print(1)
    else:
        print(len(set(S[b-1:int(c)-1])))

Submission status: Wrong Answer

Solution code:
N = int(input())
ALPHAS = [[0] * 26 for i in range(N+1)]
S = input()
alpha2num = lambda c: ord(c) - ord('a')

for i in range(N):
    for j in range(26):
        ALPHAS[i+1][j] = ALPHAS[i][j]
    ALPHAS[i+1][alpha2num(S[i])] += 1

K = int(input())
for _ in range(K):
    q,a,b = map(lambda c:c,input().split())
    if q == '2':
        l = int(a)
        r = int(b)
        ans = 0
        for i in range(26):
            if ALPHAS[r][i] - ALPHAS[l-1][i] > 0:
                ans += 1
        print(ans)
    if q == '1':
        i = int(a)
        p_s = S[i-1]
        s = b
        for j in range(i,N+1):
            ALPHAS[j][alpha2num(p_s)] -= 1
            ALPHAS[j][alpha2num(s)] += 1

Submission status: Wrong Answer

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

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

tmp = 'abcdefghijklmnopqrstuvwxyz'
n = I()
s = list(input())
cnt = [0]*n
alpha = defaultdict(list)
for i in range(n):
    alpha[s[i]].append(i)

q = I()
f = defaultdict(list)
for _ in range(q):
    num, i, c = input().split()
    if int(num) == 1:
        if s[int(i)-1] == c:
            continue
        f[s[int(i)-1]].append(int(i)-1)
        f[s[int(i)-1]].sort()
        alpha[c].append(int(i)-1)
        alpha[c].sort()
    else:
        cnt = 0
        for j in range(26):
            l = bl(alpha[tmp[j]],int(i)-1)
            r = br(alpha[tmp[j]],int(c)-1)
            L = bl(f[tmp[j]],int(i)-1)
            R = br(f[tmp[j]],int(c)-1)
            if r - l - (R-L) > 0:
                cnt += 1
            #print(tmp[j],alpha[tmp[j]],f[tmp[j]],int(i),int(c),l,r,L,R)
        print(cnt)

Submission status: Wrong Answer

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


class segment_tree:
    n = 0
    segtree = []
    max_v = 10**9

    def __init__(self, A, max_n=10**9 + 1):
        N = len(A)
        self.max_v = max_n
        self.n = (N-1).bit_length()
        self.n = 2 ** self.n
        self.segtree = [set() for i in range(2*self.n)]
        for i in range(N):
            self.segtree[self.n+i].add(A[i])
        for i in range(self.n - 1, -1, -1):
            if i == self.n-1:
                self.segtree[i] |= self.segtree[i*2 + 1]
            else:
                self.segtree[i] = self.segtree[i*2 + 1] | self.segtree[i*2 + 2]

    def update(self, i, x):
        id = self.n+i
        while(id >= 0):
            if id >= self.n:
                self.segtree[id] = set(x)
                # print(self.segtree)
            else:
                self.segtree[id] = self.segtree[id *
                                                2 + 1] | self.segtree[id*2 + 2]
                # print(self.segtree[id*2 + 1], self.segtree[id*2+2])
            id = (id - 1) // 2

    def query(self, a, b, k, l, r):
        if r <= a or l >= b:
            return(set())
        if a <= l and r <= b:
            return(self.segtree[k])
        else:
            vl = self.query(a, b, k*2+1, l, (l+r)//2)
            vr = self.query(a, b, k*2+2, (l+r)//2, r)
            return(vl | vr)


ST = segment_tree(S[:-1])

for _ in range(Q):
    t, a, b = input().split()

    if t == "1":
        a = int(a)
        ST.update(a-1, b)
    elif t == "2":
        a = int(a)
        b = int(b)
        ret = ST.query(a-1, b, 0, 0, N)
        # print(ST.segtree)
        print(len(ret))

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(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())

query = list(input().split() for _ in range(Q))

one = '1'
two = '2'


for q in query:
    if q[0] == one:
        continue
    print(S.count(S[int(q[1])-1:int(q[2])-1]))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = list(input())
q = int(input())
query = []
a = []
for _ in range(q):
    method, i, c = input().split()
    if method == "1":
        a.append([i, c])
    else:
        a.append([i, c])
        query.append(a)
        a = []
string = []
now = s
for qq in query:
    if len(qq) == 1:
        string.append(now)
        continue
    for i, c in qq[:-1]:
        i = int(i)
        now[i-1] = c
    string.append(now)

for qq, ss in zip(query, string):
    l, r = map(int, qq[-1])
    print(len(set(ss[l:r+1])))

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]

def main():
    N = int(input())
    S = input()
    Q = int(input())
    query = [list(input().split()) for _ in range(Q)]
    # print(query)
    S_list = list(S)
    # i文字目までの種類を計算
    tmp = set()
    cum_sum = []
    cum_sum.append(0)
    for i in range(N):
        tmp.add(S_list[i])
        cum_sum.append(len(tmp))
    # cum_sum = [0] + [ for i in range(N)]
    # print(cum_sum)
    for q in query:
        # print(q)
        if q[0] == '1':
            j = int(q[1])-1
            S_list[j] = q[2]
            # print(S_list[0:j])
            tmp2 = set(S_list[0:j])
            if cum_sum[j] != len(tmp2):
                for k in range(j,N):
                    cum_sum[k] -= 1
        else:
            q1 = int(q[1])-1
            q2 = int(q[2])
            # print(q)
            # sub_list = S_list[int(q[1])-1:int(q[2])]
            # print(sub_list)
            print(cum_sum[q2] - cum_sum[q1]+1)

if __name__ == "__main__":
    main()