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:
class my_segment_tree:
    def __init__(self, base_array, size, f=lambda a, b: a + b, default_value = 0):
        self.f = f
        self._seg_size = 2 ** (size.bit_length() + 1) - 1
        self._default_value = default_value
        self._array = [default_value] * (self._seg_size)
        k = 2 ** size.bit_length() - 1  # 一番下の最初のindex

        for i in range(size):
            self._array[k + i] = base_array[i]

        while k > 0:
            for i in range((k + 1) // 2):
                self._array[(k + 2 * i) // 2] = f(self._array[k + 2 * i], self._array[k + 2 * i + 1])
            k //= 2
    def update(self, i, v):
        i += (self._seg_size // 2)
        self._array[i] = v
        while i > 0:
            i = (i - 1) >> 1
            self._array[i] = self.f(self._array[2 * i + 1], self._array[2 * i + 2])

    def get(self, left, right):
        return self._get(left, right, 0, self._seg_size // 2, 0) #どちらも閉空間

    def _get(self, left, right, l, r, i):
        if left <= l and r <= right:
            return self._array[i]

        a = 0
        if left <= (l + r) // 2:
            a = self._get(left, min(right, (l + r) // 2), l, (l + r) // 2, 2 * i + 1)
        b = 0
        if (l + r) // 2 + 1 <= right:
            b= self._get(max(left, (l + r) // 2 + 1), right, (l + r) // 2 + 1, r, 2 * i + 2)

        return self.f(a, b)

def main():
    N = int(input())
    S = [c for c in input()]
    M = int(input())
    dic = {c: i for i, c in enumerate('abcdefghijklmnopqrstuvwxyz')}
    Arrays = [[0 for j in range(N)] for i in range(26)]

    for i, c in enumerate(S):
        Arrays[dic[c]][i] = 1

    segs = []
    for i in range(26):
        segs.append(my_segment_tree(Arrays[i], N))

    for i in range(M):
        p, a, b = input().split()
        a  = int(a) - 1
        b = int(b) - 1 if p == '2' else b
        if p == '1':
            before = S[a]
            segs[dic[before]].update(a, 0)
            segs[dic[b]].update(a, 1)

        if p == '2':
            s = 0
            for j in range(26):
                if segs[j].get(a, b) > 0:
                    s += 1
            print(s)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:




class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return max(x,y)

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

alphalist = [[0]*N for _ in range(26)]
atmp = ord('a')
for i,s in enumerate(S):
    alphalist[ord(s)-atmp][i] = 1

seglist = [None]*26
for i in range(26):
    seglist[i] = SegTree(N,alphalist[i],segfunc,0)

ans = []
for i in range(Q):
    t,l,r = map(str,input().split())
    if t=='1':
        i = int(l)-1
        c = r
        if S[i]==c:
            continue
        
        org_idx = ord(S[i])-atmp
        seglist[org_idx].update(i,0)
        upt_idx = ord(c) - atmp
        seglist[upt_idx].update(i,1)
                
        
    else:
        l,r = int(l)-1,int(r)
        cnt = 0
        for i in range(26):
            cnt += seglist[i].query(l,r)
        ans.append(cnt)

for a in ans:
    print(a)

Submission status: Wrong Answer

Solution code:




class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return max(x,y)

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

alphalist = [[0]*N for _ in range(26)]
atmp = ord('a')
for i,s in enumerate(S):
    alphalist[ord(s)-atmp][i] = 1

seglist = [None]*26
for i in range(26):
    seglist[i] = SegTree(N,alphalist[i],segfunc,0)

    
for i in range(Q):
    t,l,r = map(str,input().split())
    if t=='1':
        i = int(l)-1
        c = r
        
        org_idx = ord(S[i])-atmp
        seglist[org_idx].update(i,0)
        upt_idx = ord(c) - atmp
        seglist[upt_idx].update(i,1)
                
        
    else:
        l,r = int(l)-1,int(r)
        ans = 0
        for i in range(26):
            ans += seglist[i].query(l,r)
        print(ans)

Submission status: Wrong Answer

Solution code:




class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return x or y        

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

alphalist = [[0]*N for _ in range(26)]
atmp = ord('a')
for i,s in enumerate(S):
    alphalist[ord(s)-atmp][i] = 1

seglist = [None]*26
for i in range(26):
    seglist[i] = SegTree(N,alphalist[i],segfunc,0)

    
for i in range(Q):
    t,l,r = map(str,input().split())
    if t=='1':
        i = int(l)-1
        c = r
        
        org_idx = ord(S[i])-atmp
        seglist[org_idx].update(i,0)
        upt_idx = ord(c) - atmp
        seglist[upt_idx].update(i,1)
                
        
    else:
        l,r = int(l)-1,int(r)
        ans = 0
        for i in range(26):
            ans += seglist[i].query(l,r)
        print(ans)

Submission status: Wrong Answer

Solution code:




class SegTree:
    # n : 元の配列の長さ
    # init_list: 元の配列
    # segfunc : 載せる関数（演算）
    # ide_ele : segfuncの単位元
        
    def __init__(self, n, init_list ,segfunc, ide_ele):
        #　num : 2**num >= n となる最小の整数 （葉の数）
        # seg : segtreeのリスト
        self.num = 2**((n-1).bit_length())
        self.seg = [ide_ele]*(2*self.num)
        self.segfunc = segfunc
        self.ide_ele = ide_ele
        # 葉の要素をセット
        for i in range(n):
            self.seg[i+self.num-1] = init_list[i]        
        # segtreeの構築
        for i in range(self.num-2, -1, -1):
            self.seg[i] = segfunc(self.seg[2*i+1],self.seg[2*i+2])
        
        #memo: 要素iの子ノードは要素2*i+1, 2*i+2
        #    : 要素iの親ノードは要素(i-1)//2
        
    # 要素の更新 (init_list[k]=x)
    def update(self,k,x):
        k += self.num-1 #葉のノードのインデックス
        self.seg[k] = x
        #末端から頂点まで更新
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[2*k+1], self.seg[2*k+2])
     
    # 区間クエリ （区間[l,r)に対する演算結果）
    def query(self, l,r):
        if r<=l:
            return self.ide_ele
        
        l += self.num-1 #葉のノードのインデックス
        r += self.num-2 #半開区間から閉区間へ
        ret = self.ide_ele
        
        while r-l>1:
            if l&1 == 0:
                ret = self.segfunc(ret,self.seg[l])
            
            if r&1 == 1:
                ret = self.segfunc(ret,self.seg[r])
                r -= 1
            # 親ノードへ遷移
            l = l//2
            r = (r-1)//2
        if r==l:
            ret = self.segfunc(ret, self.seg[r])
        else:
            ret = self.segfunc(ret, self.seg[l])
            ret = self.segfunc(ret, self.seg[r])
        
        return ret
            
def segfunc(x,y):
    return x or y        

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

alphalist = [[0]*N for _ in range(26)]
atmp = ord('a')
for i,s in enumerate(S):
    alphalist[ord(s)-atmp][i] = 1

seglist = [None]*26
for i in range(26):
    seglist[i] = SegTree(N,alphalist[i],segfunc,0)

    
for i in range(Q):
    t,l,r = map(str,input().split())
    if t=='1':
        i = int(l)-1
        c = r
        
        org_idx = ord(S[i])-atmp
        seglist[org_idx].update(i,0)
        upt_idx = ord(c) - atmp
        seglist[upt_idx].update(i,1)
                
        
    else:
        l,r = int(l)-1,int(r)
        ans = 0
        for i in range(26):
            ans += seglist[i].query(l,r)
        print(ans)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        if i < 0:
            return 0
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1)


n = I()
s = list(S())
D = defaultdict(lambda:BIT(n))
for i in range(n):
    D[ord(s[i])].add(i, 1)

q = I()
for j in range(q):
    qi, i, c = LS()
    i = int(i) - 1
    if qi == '1':
        D[ord(s[i])].add(i, -1)
        D[ord(c)].add(i, 1)
        s[i] = c
    else:
        l, r = i, int(c)
        ret = 0
        for k in range(97, 123):
            if D[k].sum(r - 1) > D[k].sum(l - 2):
                ret += 1
        print(ret)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        if i < 0:
            return 0
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1)


n = I()
s = list(S())
D = defaultdict(lambda:BIT(n))
for i in range(n):
    D[ord(s[i])].add(i, 1)

q = I()
for j in range(q):
    qi, i, c = LS()
    i = int(i) - 1
    if qi == '1':
        D[ord(s[i])].add(i, -1)
        D[ord(c)].add(i, 1)
        s[i] = c
    else:
        l, r = i, int(c)
        ret = 0
        for i in range(97, 123):
            if D[i].sum(r-1) > D[i].sum(l-2):
                ret += 1
        print(ret)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        if i < 0:
            return 0
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1)


n = I()
s = list(S())
D = defaultdict(lambda:BIT(n))
for i in range(n):
    D[ord(s[i])].add(i, 1)

q = I()
for j in range(q):
    qi, i, c = LS()
    i = int(i)
    if qi == '1':
        D[ord(s[i - 1])].add(i, -1)
        D[ord(c)].add(i, 1)
        s[i - 1] = c
    else:
        l, r = i, c
        ret = 0
        for i in range(97, 123):
            if D[i].sum(int(r)-1) > D[i].sum(l-2):
                ret += 1
        print(ret)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1)


n = I()
s = list(S())
D = defaultdict(lambda:BIT(n))
for i in range(n):
    D[ord(s[i])].add(i, 1)

q = I()
for j in range(q):
    qi, i, c = LS()
    i = int(i)
    if qi == '1':
        D[ord(s[i - 1])].add(i, -1)
        D[ord(c)].add(i, 1)
        s[i - 1] = c
    else:
        l, r = i, c
        ret = 0
        for i in range(97, 123):
            if D[i].interval_sum(l - 1, int(r)):
                ret += 1
        print(ret)

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
import pprint
sys.setrecursionlimit(10 ** 9)


INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007


class BIT:
    def __init__(self, size):
        self.bit = [0] * size
        self.size = size
        self.total = 0

    def add(self, i, w):
        x = i + 1
        self.total += w
        while x <= self.size:
            self.bit[x - 1] += w
            x += x & -x
        return

    def sum(self, i):
        res = 0
        x = i + 1
        while x:
            res += self.bit[x - 1]
            x -= x & -x
        return res

    def interval_sum(self, i, j): # i <= x < j の区間
        return self.sum(j - 1) - self.sum(i - 1)


n = I()
s = list(S())
D = defaultdict(lambda:BIT(n))
for i in range(n):
    D[s[i]].add(i, 1)

q = I()
for j in range(q):
    qi, i, c = LS()
    i = int(i)
    if qi == '1':
        D[s[i - 1]].add(i, -1)
        D[c].add(i, 1)
        s[i - 1] = c
    else:
        l, r = i, c
        ret = 0
        for i in range(97, 123):
            if D[chr(i)].interval_sum(l - 1, int(r)):
                ret += 1
        print(ret)

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
q = int(input())
for _ in range(q):
    i,x,y = input().split()
    if (i == "1"):
        x = int(x)
        li = list(s)
        li[x-1] = y
        s = "".join(li)
        print(s)
    if (i == "2"):
        x = int(x)
        y = int(y)
        ans = s[x-1:y]
        st = set(ans)
        print(len(st))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
q = int(input())
for _ in range(q):
    i,x,y = input().split()
    if (i == "1"):
        x = int(x)
        li = list()
        for b in s:
            li.append(b)
        li[x-1] = y
        s = ""
        for b in li:
            s += b
        print(s)
    if (i == "2"):
        x = int(x)
        y = int(y)
        ans = s[x-1:y]
        st = set()
        for b in ans:
            st.add(b)
        print(len(st))

Submission status: Wrong Answer

Solution code:
n = int(input())
s = input()
q = int(input())
for _ in range(q):
    i,x,y = input().split()
    if (i == "1"):
        x = int(x)
        li = list()
        for b in s:
            li.append(b)
        li[x-1] = y
        s = ""
        for b in li:
            s += b
    if (i == "2"):
        x = int(x)
        y = int(y)
        ans = s[x-1:x-1+y]
        st = set()
        for b in ans:
            st.add(b)
        print(len(st))

Submission status: Wrong Answer

Solution code:
#####segfunc######
class SegTree:
    def segfunc(self, x, y):
        return max(x,y)

    def __init__(self, init_val):
        #set_val
        #####単位元######
        self.ide_ele = 0
        n = len(init_val)
        #num:n以上の最小の2のべき乗
        self.num =2**(n-1).bit_length()
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        #built
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        num = self.num
        k += num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
    def query(self, p, q):
        num = self.num 
        if q<=p:
            return self.ide_ele
        p += num-1
        q += num-2
        res=self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res,self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res,self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
        return res



N = int(input())

S = list(input())
ALPHAS = [[0] * (N+1) for i in range(26)]
alpha2num = lambda c: ord(c) - ord('a')
for i in range(N):
    ALPHAS[alpha2num(S[i])][i] = 1
for i,alpha in enumerate(ALPHAS):
    ALPHAS[i] = SegTree(alpha)
ALPHAS = tuple(ALPHAS)
Q = int(input())
for _ in range(Q):
    q,a,b = map(lambda c:c,input().split())
    if q == '2':
        l = int(a)-1
        r = int(b)
        ans = 0
        for i in range(26):
            ans += ALPHAS[i].query(l,r)
        print(ans)
    if q == '1':
        i = int(a)-1
        p_s = S[i-1]
        s = b
        S[i-1] = s
        ALPHAS[alpha2num(p_s)].update(i,0)
        ALPHAS[alpha2num(s)].update(i,1)

Submission status: Wrong Answer

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

n = int(input().rstrip('\n'))
s = input().rstrip('\n')
q = int(input().rstrip('\n'))
Q = [input().rstrip('\n').split() for _ in range(q)]

class SegTree():
    def __init__(self, n_):
        self.n = 1
        while self.n < n_:
            self.n *= 2
        self.tree = [float('inf') for _ in range(2 * self.n - 1)]
    def update(self, k, a):
        k += self.n - 1
        self.tree[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.tree[k] = min(self.tree[k * 2 + 1], self.tree[k * 2 + 2])
    def query(self, l, r):
        l += self.n - 1
        r += self.n - 2
        res = float('inf')
        while r-l>1:
            if l&1 == 0:
                res = min(res,self.tree[l])
            if r&1 == 1:
                res = min(res,self.tree[r])
                r -= 1
            l = l//2
            r = (r-1)//2
        if l == r:
            res = min(res,self.tree[l])
        else:
            res = min(min(res,self.tree[l]),self.tree[r])
        return res

d = { c: SegTree(n) for c in "abcdefghijklmnopqrstuvwxyz"}

for i, c in enumerate(s):
    d[c].update(i, 1)


for a, b, c in Q:
    if a == "1":
        b = int(b) - 1
        # c = c.rstrip('\n')
        d[s[b]].update(b, float('inf'))
        d[c].update(b, 1)
    else:
        res = 0
        b, c = int(b), int(c)
        for key in d:
            if d[key].query(b-1, c) == 1:
                res += 1
        print(res)

Submission status: Wrong Answer

Solution code:
import math

n = int(input())
s = input()
L = len(s)
S = [ord(i) - 97 for i in s]
q = int(input())
H = math.ceil(math.log(n) / math.log(2))
LH = 1 << H

def build_tree_for_letter(letter):
    tree = [False for _ in range(2<<H)]
    for i in range(1<<H):
        tree[i + (1<<H)] = True if i < L and s[i]==chr(97+letter) else False

    for i in range(H-1, -1, -1):
        for x in range(1<<i, 2<<i):
            tree[x] = any((tree[x<<1], tree[(x<<1)+1]))

    return tree

def build():
    trees = []
    for letter in range(26):
        trees.append(build_tree_for_letter(letter))

    return trees


def update(x, letter, positive=True):
    trees[letter][x] = (positive == True)
    while x > 1:
        x >>= 1
        trees[letter][x] = any((trees[letter][x << 1], trees[letter][(x << 1) + 1]))


def query(ll, rr):

    # print("query: ", l, r)
    total = 0
    for letter in range(26):
        l, r = ll + (1<<H), rr + (1<<H)
        is_letter = False
        while l < r:
            if l%(2) != 0:
                is_letter = any((is_letter, trees[letter][l]))
                l += 1
            l //= 2
            if r%(2) != 0:
                is_letter = any((is_letter, trees[letter][r-1]))
                r -= 1
            r //= 2
        total += is_letter
    return total



trees = build()

for i in range(q):
    a, b, c = input().split()
    b = int(b) - 1
    if int(a) == 1:
        c = ord(c) - 97
        update(b, S[b], positive=False)
        S[b] = c
        update(b, c, positive=True)
    else:
        c = int(c)
        print(query(b, c))

Submission status: Wrong Answer

Solution code:
bS = int(input())
S= input()
nQ = int(input())

query = []
for i in range(nQ):
  query.append(input().split())

for i in range(nQ):
  iQ = query[i]
  
  if iQ[0] == "1":
    S= S[:int(iQ[1])] + iQ[2] + S[int(iQ[1])+1:]
  else:
    sub = S[int(iQ[1])-1:int(iQ[2])]
    nChar = len(set([i for i in sub]))
    print(nChar)